bzoj 3262 陌上花开

题目大意：

有

对于

先按照x排序记录一下顺序

然后cdq分治

在分治里面先分治左右两端

然后统计完左右两端的答案后

区间内按照b值排序

将x<=区间中点x的三元组的z加入树状数组

将x>区间中点x的三元组的z在树状数组中查询

同时对于所有相同的元素，它的答案都为最后一个的答案

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #define inf 2139062143
10 #define ll long long
11 #define MAXN 100100
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
17     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 int n,k,c[MAXN*2],to[MAXN],ans[MAXN],Ans[MAXN];
21 int lowbit(int x) {return x&(-x);}
22 void add(int x,int val) {for(int i=x;i<=k;i+=lowbit(i)) c[i]+=val;}
23 int query(int x) {int res=0;for(int i=x;i;i-=lowbit(i)) res+=c[i];return res;}
24 struct data 
25 {
26     int x,y,z,pos,Pos;
27     bool operator != (const data &a) const
28     {
29         return x!=a.x||y!=a.y||z!=a.z;
30     }
31 }g[MAXN];
32 bool cmp1(data a,data b) {return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);}
33 bool cmp2(data a,data b) {return a.y<b.y||(a.y==b.y&&a.Pos<b.Pos);}
34 void cdq(int l,int r)
35 {
36     if(l==r) return ;
37     int mid=(l+r)>>1;
38     data m=g[mid];
39     cdq(l,mid);cdq(mid+1,r);
40     sort(g+l,g+r+1,cmp2);
41     for(int i=l;i<=r;i++)
42     {
43         if(g[i].Pos<=m.Pos) add(g[i].z,1);
44         else ans[g[i].pos]+=query(g[i].z);
45     }
46     for(int i=l;i<=r;i++) if(g[i].Pos<=m.Pos) add(g[i].z,-1);
47 }
48 int main()
49 {
50     n=read(),k=read();
51     for(int i=1;i<=n;i++)
52         g[i].pos=i,g[i].x=read(),g[i].y=read(),g[i].z=read();
53     sort(g+1,g+n+1,cmp1);
54     int tmp=1;g[n+1].x=k+1;
55     for(int i=1;i<=n;i++)
56     {
57         g[i].Pos=i;
58         if(g[i]!=g[i+1])
59         {
60             for(int j=tmp;j<=i;j++) to[g[j].pos]=g[i].pos;
61             tmp=i+1;
62         }
63     }
64     cdq(1,n);
65     for(int i=1;i<=n;i++) Ans[ans[to[i]]]++;
66     for(int i=0;i<n;i++) printf("%d
",Ans[i]);
67 }

View Code

orz 一道三位偏序的原题 luogu p3810 【模板】三维偏序