BZOJ 3262 陌上花开
这是一道传说中的cdq裸题
还是理解了比较久，不过还是蛮好玩儿的，第一次写所以代码非常丑，排序非常多- -不管啦
本来交上去T了，非常无耻的开了O2还是过不了，然后发现是我在分治的每一层都清空了树状数组- -太蠢了。
//某tangyuhao亲切的吐槽了cdq不仅有分治还有提出了插头dp这么变态的东西，让我只好++ym
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define __O2 __attribute__((optimize("O2")))
using namespace std;
const int INF = 200000+5;
struct node{
int x,y,z,t,ans;
void print(){
printf("x:%d y:%d z:%d t:%d ans:%d\n",x,y,z,t,ans);
}
bool operator ==(const node &a)const{
if(x!=a.x) return false;
if(y!=a.y) return false;
if(z!=a.z) return false;
return true;
}
} Qr[2*INF];
int s[2*INF],ans[INF];
int b[2*INF],k,n;
#define lowbit(i) i&(-i)
__O2 void put(int val,int x){
for(int i=x;i<=k;i+=lowbit(i))
b[i]+=val;
}
__O2 bool cmps(node a,node b){
if(a.x==b.x){
if(a.y==b.y) return a.z<b.z;
else return a.y<b.y;
}
return a.x<b.x;
}
__O2 bool cmpx(node a,node b){
if(a.x==b.x) return a.t<b.t;
return a.x<b.x;
}
__O2 bool cmpt(node a,node b){
return a.t<b.t;
}
__O2 bool cmpy(node a,node b){
if(a.y==b.y) return a.t<b.t;
return a.y<b.y;
}
__O2 int query(int x){
int ret=0;
for(int i=x;i;i-=lowbit(i))
ret+=b[i];
return ret;
}
__O2 void solve(int L,int R){
if(L>=R) return ;
bool flag[2];
flag[0]=flag[1]=0;
for(int i=L;i<=R;++i)
flag[Qr[i].t>n]=true;
if(flag[0]^flag[1]) return ;
int mid=(L+R)>>1;
solve(L,mid);
solve(mid+1,R);
sort(Qr+L,Qr+mid+1,cmpx);
sort(Qr+mid+1,Qr+R+1,cmpx);
int l=L-1,r=mid;
while(l<=mid&&r<R){
r++;
if(Qr[r].t<=n) continue;
while(Qr[l+1].x<=Qr[r].x&&l<mid){
l++;
if(Qr[l].t>n) continue;
put(1,Qr[l].z);
}
int tmp=query(Qr[r].z);
Qr[r].ans+=tmp;
}
for(int i=L;i<=l;++i){
if(Qr[i].t>n) continue;
put(-1,Qr[i].z);
}
}
__O2 int main(){
freopen("flower.in","r",stdin);
freopen("flower.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&Qr[i].x,&Qr[i].y,&Qr[i].z),Qr[i].t=i;
Qr[i+n]=Qr[i];
Qr[i+n].t=n+1;
Qr[i].ans=Qr[i+n].ans=0;
}
sort(Qr+1,Qr+2*n+1,cmpy);
solve(1,2*n);
sort(Qr+1,Qr+2*n+1,cmps);
for(int i=2;i<=2*n;++i)
if(Qr[i]==Qr[i-1]) Qr[i].ans=max(Qr[i].ans,Qr[i-1].ans);
for(int i=2*n-1;i>=1;--i)
if(Qr[i]==Qr[i+1]) Qr[i].ans=max(Qr[i].ans,Qr[i+1].ans);
sort(Qr+1,Qr+2*n+1,cmpt);
for(int i=1;i<=n;++i)
ans[Qr[i].ans-1]++;
for(int i=0;i<n;++i)
printf("%d\n",ans[i]);
return 0;
}