P3810 [Template] Three-dimensional partial order (flowers on Moshang)

topic background

This is a template question

You can use bitset, CDQ divide and conquer, K-DTree, etc. to solve the problem.

Title description

Yesn element, ione element has ai?, b i?, < span class="katex-mathml">ci? Three attributes, set up f(i)< span class="strut">fmeans satisfying aj?≤ai? andbj?≤bi? and < span class="strut">c j?≤c< span class="msupsub">i? j. span> span> span> span> span> span>< /span>< /span>

For d∈[0,< span class="mord mathit">n), ask for f(i)=d number< /span>

Input format

Two integers in the first line n, k , respectively indicate the number of elements and the maximum attribute value. span>

After n lines, three integers per lineai?, bi?< span class="vlist-r">, c< span class="mord mathit mtight">i?, each represents three attribute values. span> span>

div>

Output format

Outputn line, line d + 1Line Representationf(i) = di number. span> span>

input and output sample

Enter #1Copy

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Output#1Copy< /button>

3
1
3
0
1
0
1
0
0
1

Instructions/Tips

1≤n≤1 00000,1≤< span class="mord mathit">k≤200000 span> span>

< span class="mord">Board questions, the idea is similar to grouping. span> p>

span> span>

 1 // luogu-judger-enable-o2

 2 #include

 3 #define re register int

 4 #define lowbit(x) x&(-x)

 5 #define LL long long

 6 const  int maxn1=100000+5;

 7 const int maxn2=200000+5;

 8 using namespace std;

 9 int tree[maxn2];

 10 int cnt[maxn2];

 11 int n,k;

 12 inline int read()

 13 {

 14 int x=0,f=1;

 15 char ch=getchar();

 16 while(!isdigit(ch))

 17  {

 18 if(ch=='-') f= -1;

 19 ch=getchar();

 20 }

 21 while(isdigit(ch))

 22  {

 23 x=(x<<3)+ (x<<1)+ch-'0';

 24 ch=getchar();

 25 }

 26 return x*f;

 27 }

 28 inline void write(int x)

 29 {

 30 if(x<0)

 31  {

 32 putchar('-');

 33 x=-x;

 34 }

 35 if(x>9) write(x/10);

 36 putchar(x%10+'0');

 37 }

 38 struct node{

 39 int x,y,z,ans,w;

 40 };

 41 node no[maxn1],ed[maxn1];

 42 bool cmpx(const node &a,const node&b)

 43 {

 44 if(ax!=bx) return ax<bx;

 45 if(ay!=by) return ay<by;

 46 else return az<bz;

 47 }

 48 bool cmpy(const node &a,const node&b)

 49 {

 50 if(ay!=by) return ay<by;

 51 else return az<bz;

 52 }

 53 void add(int pos,int val)

 54 {

 55 while(pos<=k)

 56  {

 57 tree[pos]+=val;

 58 pos+=lowbit(pos);

 59 }

 60 }

 61 int Query(int pos)

 62 {

 63 int ans=0;

 64 while(pos)

 65  {

 66 ans+=tree[pos];

 67 pos-=lowbit(pos);

 68 }

 69 return ans;

 70 }

 71 void cdq(int l,int r)

 72 {

 73 if(l==r) return;

 74 int mid=(l+r)> >1;

 75  cdq(l,mid);

 76 cdq(mid+1,r);

 77 sort(no+l,no+mid+1,cmpy);

 78 sort(no+mid+1,no+ r+1,cmpy);

 79 int i=mid+1,j=l;

 80 for(;i<=r;i++ )

 81  {

 82 while(no[j].y< =no[i].y&&j<=mid)

 83  {

 84  add(no[j].z,no[j] .w);

 85 j++;}

 86 no[i].ans+=Query(no[i] .z);

 87 }

 88 for(i=l;i)

 89 add(no[i].z,-no[i ].w);

 90 }

 91 int cou;

 92 int main()

 93 {

 94 n=read();

 95 k=read();

 96 for(re i=1;i<=n;i++)

 97  {

 98 ed[i].x=read();

 99 ed[i].y=read();

100 ed[i].z=read();

101 }

102 sort(ed+1,ed+n+< span style="color: #800080;">1,cmpx);

103 int sum=0;

104 for(re i=1;i<=n;i++)

105  {

106 sum++;

107 if(ed[i].x! =ed[i+1].x||ed[i].y!=ed[i+1 ].y||ed[i].z!=ed[i+1] .z)

108         {

109             no[++cou]=ed[i];

110             no[cou].w=sum;

111             sum=0;

112         }

113     }

114     cdq(1,cou);

115     for(re i=1;i<=cou;i++)

116     cnt[no[i].ans+no[i].w-1]+=no[i].w;

117     for(re i=0;i)

118     {write(cnt[i]);

119     putchar(‘
‘);}

120     return 0;

121     }

View Code

这是一道模板题

可以使用bitset，CDQ分治，K-DTree等方式解决。

有 n 个元素，第 i个元素有 ai?、bi?、ci? 三个属性，设 f(i)f表示满足aj?≤ai? 且bj?≤bi? 且 cj?≤ci? 的 j的数量。

对于 d∈[0,n)，求 f(i)=d 的数量

第一行两个整数 n、k，分别表示元素数量和最大属性值。

之后 n 行，每行三个整数 ai?、bi?、ci?，分别表示三个属性值。

输出 n行，第 d + 1行表示 f(i) = d的 i 的数量。

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

3
1
3
0
1
0
1
0
0
1

输入 #1复制

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出 #1复制

3
1
3
0
1
0
1
0
0
1

1≤n≤100000,1≤k≤200000

       板子题，思想类似于归并排。

  1 // luogu-judger-enable-o2

  2 #include

  3 #define re register int

  4 #define lowbit(x) x&(-x)

  5 #define LL long long

  6 const int maxn1=100000+5;

  7 const int maxn2=200000+5;

  8 using namespace std;

  9 int tree[maxn2];

 10 int cnt[maxn2];

 11 int n,k;

 12 inline int read()

 13 {

 14     int x=0,f=1;

 15     char ch=getchar();

 16     while(!isdigit(ch))

 17     {

 18         if(ch==‘-‘) f=-1;

 19         ch=getchar();

 20     }

 21     while(isdigit(ch))

 22     {

 23         x=(x<<3)+(x<<1)+ch-‘0‘;

 24         ch=getchar();

 25     }

 26     return x*f;

 27 }

 28 inline void write(int x)

 29 {

 30     if(x<0)

 31     {

 32         putchar(‘-‘);

 33         x=-x; 

 34     }

 35     if(x>9) write(x/10);

 36     putchar(x%10+‘0‘);

 37 }

 38 struct node{

 39     int x,y,z,ans,w;

 40 };

 41 node no[maxn1],ed[maxn1];

 42 bool cmpx(const node &a,const node&b)

 43 {

 44     if(a.x!=b.x)  return a.x<b.x;

 45     if(a.y!=b.y)  return a.y<b.y;

 46     else return a.z<b.z;

 47 }

 48 bool cmpy(const node &a,const node&b)

 49 {

 50     if(a.y!=b.y)  return a.y<b.y;

 51     else return a.z<b.z;

 52 }

 53 void add(int pos,int val)

 54 {

 55     while(pos<=k)

 56     {

 57         tree[pos]+=val;

 58         pos+=lowbit(pos);

 59     }

 60 }

 61 int Query(int pos)

 62 {

 63     int ans=0;

 64     while(pos)

 65     {

 66         ans+=tree[pos];

 67         pos-=lowbit(pos);

 68     }

 69     return ans;

 70 }

 71 void cdq(int l,int r)

 72 {

 73     if(l==r) return;

 74     int mid=(l+r)>>1;

 75     cdq(l,mid);

 76     cdq(mid+1,r);

 77     sort(no+l,no+mid+1,cmpy);

 78     sort(no+mid+1,no+r+1,cmpy);

 79     int i=mid+1,j=l;

 80     for(;i<=r;i++)

 81     {

 82         while(no[j].y<=no[i].y&&j<=mid)

 83     {

 84         add(no[j].z,no[j].w);

 85         j++;}

 86         no[i].ans+=Query(no[i].z);

 87     }

 88     for(i=l;i)

 89     add(no[i].z,-no[i].w);

 90 }

 91 int cou;

 92 int main()

 93 {

 94     n=read();

 95     k=read();

 96     for(re i=1;i<=n;i++)

 97     {

 98         ed[i].x=read();

 99         ed[i].y=read();

100         ed[i].z=read();

101     }

102     sort(ed+1,ed+n+1,cmpx);

103     int sum=0;

104     for(re i=1;i<=n;i++)

105     {

106         sum++;

107         if(ed[i].x!=ed[i+1].x||ed[i].y!=ed[i+1].y||ed[i].z!=ed[i+1].z)

108         {

109             no[++cou]=ed[i];

110             no[cou].w=sum;

111             sum=0;

112         }

113     }

114     cdq(1,cou);

115     for(re i=1;i<=cou;i++)

116     cnt[no[i].ans+no[i].w-1]+=no[i].w;

117     for(re i=0;i)

118     {write(cnt[i]);

119     putchar(‘
‘);}

120     return 0;

121     }

View Code

  1 // luogu-judger-enable-o2

  2 #include

  3 #define re register int

  4 #define lowbit(x) x&(-x)

  5 #define LL long long

  6 const int maxn1=100000+5;

  7 const int maxn2=200000+5;

  8 using namespace std;

  9 int tree[maxn2];

 10 int cnt[maxn2];

 11 int n,k;

 12 inline int read()

 13 {

 14     int x=0,f=1;

 15     char ch=getchar();

 16     while(!isdigit(ch))

 17     {

 18         if(ch==‘-‘) f=-1;

 19         ch=getchar();

 20     }

 21     while(isdigit(ch))

 22     {

 23         x=(x<<3)+(x<<1)+ch-‘0‘;

 24         ch=getchar();

 25     }

 26     return x*f;

 27 }

 28 inline void write(int x)

 29 {

 30     if(x<0)

 31     {

 32         putchar(‘-‘);

 33         x=-x; 

 34     }

 35     if(x>9) write(x/10);

 36     putchar(x%10+‘0‘);

 37 }

 38 struct node{

 39     int x,y,z,ans,w;

 40 };

 41 node no[maxn1],ed[maxn1];

 42 bool cmpx(const node &a,const node&b)

 43 {

 44     if(a.x!=b.x)  return a.x<b.x;

 45     if(a.y!=b.y)  return a.y<b.y;

 46     else return a.z<b.z;

 47 }

 48 bool cmpy(const node &a,const node&b)

 49 {

 50     if(a.y!=b.y)  return a.y<b.y;

 51     else return a.z<b.z;

 52 }

 53 void add(int pos,int val)

 54 {

 55     while(pos<=k)

 56     {

 57         tree[pos]+=val;

 58         pos+=lowbit(pos);

 59     }

 60 }

 61 int Query(int pos)

 62 {

 63     int ans=0;

 64     while(pos)

 65     {

 66         ans+=tree[pos];

 67         pos-=lowbit(pos);

 68     }

 69     return ans;

 70 }

 71 void cdq(int l,int r)

 72 {

 73     if(l==r) return;

 74     int mid=(l+r)>>1;

 75     cdq(l,mid);

 76     cdq(mid+1,r);

 77     sort(no+l,no+mid+1,cmpy);

 78     sort(no+mid+1,no+r+1,cmpy);

 79     int i=mid+1,j=l;

 80     for(;i<=r;i++)

 81     {

 82         while(no[j].y<=no[i].y&&j<=mid)

 83     {

 84         add(no[j].z,no[j].w);

 85         j++;}

 86         no[i].ans+=Query(no[i].z);

 87     }

 88     for(i=l;i)

 89     add(no[i].z,-no[i].w);

 90 }

 91 int cou;

 92 int main()

 93 {

 94     n=read();

 95     k=read();

 96     for(re i=1;i<=n;i++)

 97     {

 98         ed[i].x=read();

 99         ed[i].y=read();

100         ed[i].z=read();

101     }

102     sort(ed+1,ed+n+1,cmpx);

103     int sum=0;

104     for(re i=1;i<=n;i++)

105     {

106         sum++;

107         if(ed[i].x!=ed[i+1].x||ed[i].y!=ed[i+1].y||ed[i].z!=ed[i+1].z)

108         {

109             no[++cou]=ed[i];

110             no[cou].w=sum;

111             sum=0;

112         }

113     }

114     cdq(1,cou);

115     for(re i=1;i<=cou;i++)

116     cnt[no[i].ans+no[i].w-1]+=no[i].w;

117     for(re i=0;i)

118     {write(cnt[i]);

119     putchar(‘
‘);}

120     return 0;

121     }

View Code

  1 // luogu-judger-enable-o2

  2 #include

  3 #define re register int

  4 #define lowbit(x) x&(-x)

  5 #define LL long long

  6 const int maxn1=100000+5;

  7 const int maxn2=200000+5;

  8 using namespace std;

  9 int tree[maxn2];

 10 int cnt[maxn2];

 11 int n,k;

 12 inline int read()

 13 {

 14     int x=0,f=1;

 15     char ch=getchar();

 16     while(!isdigit(ch))

 17     {

 18         if(ch==‘-‘) f=-1;

 19         ch=getchar();

 20     }

 21     while(isdigit(ch))

 22     {

 23         x=(x<<3)+(x<<1)+ch-‘0‘;

 24         ch=getchar();

 25     }

 26     return x*f;

 27 }

 28 inline void write(int x)

 29 {

 30     if(x<0)

 31     {

 32         putchar(‘-‘);

 33         x=-x; 

 34     }

 35     if(x>9) write(x/10);

 36     putchar(x%10+‘0‘);

 37 }

 38 struct node{

 39     int x,y,z,ans,w;

 40 };

 41 node no[maxn1],ed[maxn1];

 42 bool cmpx(const node &a,const node&b)

 43 {

 44     if(a.x!=b.x)  return a.x<b.x;

 45     if(a.y!=b.y)  return a.y<b.y;

 46     else return a.z<b.z;

 47 }

 48 bool cmpy(const node &a,const node&b)

 49 {

 50     if(a.y!=b.y)  return a.y<b.y;

 51     else return a.z<b.z;

 52 }

 53 void add(int pos,int val)

 54 {

 55     while(pos<=k)

 56     {

 57         tree[pos]+=val;

 58         pos+=lowbit(pos);

 59     }

 60 }

 61 int Query(int pos)

 62 {

 63     int ans=0;

 64     while(pos)

 65     {

 66         ans+=tree[pos];

 67         pos-=lowbit(pos);

 68     }

 69     return ans;

 70 }

 71 void cdq(int l,int r)

 72 {

 73     if(l==r) return;

 74     int mid=(l+r)>>1;

 75     cdq(l,mid);

 76     cdq(mid+1,r);

 77     sort(no+l,no+mid+1,cmpy);

 78     sort(no+mid+1,no+r+1,cmpy);

 79     int i=mid+1,j=l;

 80     for(;i<=r;i++)

 81     {

 82         while(no[j].y<=no[i].y&&j<=mid)

 83     {

 84         add(no[j].z,no[j].w);

 85         j++;}

 86         no[i].ans+=Query(no[i].z);

 87     }

 88     for(i=l;i)

 89     add(no[i].z,-no[i].w);

 90 }

 91 int cou;

 92 int main()

 93 {

 94     n=read();

 95     k=read();

 96     for(re i=1;i<=n;i++)

 97     {

 98         ed[i].x=read();

 99         ed[i].y=read();

100         ed[i].z=read();

101     }

102     sort(ed+1,ed+n+1,cmpx);

103     int sum=0;

104     for(re i=1;i<=n;i++)

105     {

106         sum++;

107         if(ed[i].x!=ed[i+1].x||ed[i].y!=ed[i+1].y||ed[i].z!=ed[i+1].z)

108         {

109             no[++cou]=ed[i];

110             no[cou].w=sum;

111             sum=0;

112         }

113     }

114     cdq(1,cou);

115     for(re i=1;i<=cou;i++)

116     cnt[no[i].ans+no[i].w-1]+=no[i].w;

117     for(re i=0;i)

118     {write(cnt[i]);

119     putchar(‘
‘);}

120     return 0;

121     }