P3810 【模板】三维偏序(陌上花开)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 using namespace std;
  5 const int maxn=1e7+10;
  6 int ans[maxn];
  7 int f[maxn];
  8 int n,k;
  9 int c[maxn];
 10 int same[maxn];
 11 struct node
 12 {
 13     int  a,b,c;
 14     int  w;
 15 }way[maxn];
 16 struct XX
 17 {
 18     
 19 int lowbit(int  x)
 20 {
 21     return x&(-x);
 22 }
 23 void add(int  x,int  w)
 24 {
 25     for(;x<=k;x+=lowbit(x)) 
 26     {
 27         c[x]+=w;
 28     }
 29 }
 30 int sum(int  x)
 31 {
 32     int  res=0;
 33     for(;x;x-=lowbit(x))
 34     {
 35         res+=c[x];
 36     }
 37     return res;
 38 }
 39 }XX;
 40 bool cmp1(node a,node b)
 41 {
 42     if(a.a!=b.a)
 43     {
 44         return a.a<b.a;
 45     }
 46     if(a.b!=b.b)
 47     {
 48         return a.b<b.b;
 49     }
 50     return a.c<b.c;
 51 }
 52 
 53 bool cmp2(node a,node b)
 54 {
 55     if(a.b!=b.b)
 56     {
 57         return a.b<b.b;
 58     }
 59     if(a.c!=b.c)
 60     {
 61         return a.c<b.c;
 62     }
 63     return a.a<b.a;
 64 }
 65 void  CDQ(int  l,int  r)
 66 {
 67     if(l==r)
 68     {
 69         return ;
 70     }
 71     int  mid=(l+r)>>1;
 72     CDQ(l,mid);
 73     CDQ(mid+1,r);
 74     sort(way+l,way+1+r,cmp2);
 75     for(int i=l;i<=r;i++)
 76     {
 77         if(way[i].a<=mid)
 78         {
 79             XX.add(way[i].c,1);
 80         }
 81         else
 82         {
 83             ans[way[i].w]+=XX.sum(way[i].c);
 84         }
 85     }
 86     for(int i=l;i<=r;i++)
 87     {
 88         if(way[i].a<=mid)
 89         {
 90             XX.add(way[i].c,-1);
 91         }
 92     }
 93 }
 94     
 95 int main()
 96 {
 97     scanf("%d%d",&n,&k);
 98     for(int i=1;i<=n;i++)
 99     {
100         scanf("%d%d%d",&way[i].a,&way[i].b,&way[i].c);
101         way[i].w=i;
102     }
103     sort(way+1,way+1+n,cmp1);
104     int i=1;
105     while(i<=n)
106     {
107         int j=i+1;
108         while(j<=n&&way[i].a==way[j].a&&way[i].b==way[j].b&&way[i].c==way[j].c)
109         {
110             j++;
111         }
112         while(i<j)
113         {
114             same[way[i++].w]=way[j-1].w;
115         }
116     }
117     for(int i=1;i<=n;i++)
118     {
119         way[i].a=i;
120     }
121     CDQ(1,n);
122     for(int i=1;i<=n;i++)
123     {
124         f[ans[same[way[i].w]]]++;
125     }
126     for(int i=0;i<n;i++)
127     {
128         printf("%d\n",f[i]);
129     }
130     return 0;
131 }

 

上一篇:2021-2022学年英语周报九年级第19期答案及试题


下一篇:CF2B The least round way(贪心+动规)