既见君子

同济医学生的起落落落落人生记录

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;
}


评论
热度(2)
©既见君子
Powered by LOFTER