Cptraser/ 三月 20, 2019/ 2019.3/ 0 comments

题面传送门
第一维time,第二维x,第三维y
然后CDQ分治+树状数组求偏序。

#include <bits/stdc++.h>
using namespace std;

inline char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
inline void read(int &x){char c;for(;(c=tc())<48||c>57;);for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');}

const int Maxn=1e6+5;

int N,M,Ans[Maxn];
int A[Maxn*10],Mx,x,y,c,Cnt,pl,pr;
struct Plant{int Opt,x,y,id,w;}Q[Maxn];

void Add(int x,int y){for(;x<=Mx;x+=x&-x)A[x]+=y;}
int Query(int x){int res=0;for(;x;x-=x&-x)res+=A[x];return res;}

int Cmp(Plant x,Plant y){return x.x<y.x || (x.x==y.x&&x.y<y.y);}
int Cop(Plant x,Plant y){return x.id<y.id;}

void CDQ(int L,int R){
    if(L>=R)return ;
    int Mid=L+R>>1;CDQ(L,Mid),CDQ(Mid+1,R);
    sort(Q+L,Q+Mid+1,Cmp),sort(Q+Mid+1,Q+R+1,Cmp);
    int p=L,q=Mid+1;
    for(;q<=R;++q){
        for(;p<=Mid&&Q[p].x<=Q[q].x;++p)
            if(!Q[p].Opt)Add(Q[p].y,Q[p].w);
        if(Q[q].Opt==1)Q[q].w+=Query(Q[q].y);
    }
    for(int i=L;i<p;i++)if(!Q[i].Opt)Add(Q[i].y,-Q[i].w);
}

int main()
{
    int Opt;read(Opt),read(Mx),Mx++;
    while(read(Opt),Opt!=3){
        if(Opt==1){
            read(x),read(y),read(c);
            ++x,++y;
            Q[++Cnt]=(Plant){0,x,y,Cnt,c};
        }
        if(Opt==2){
            read(x),read(y),read(pl),read(pr);
            ++x,++y,++pl,++pr;
            Q[++Cnt]=(Plant){1,pl,pr,Cnt,0};
            Q[++Cnt]=(Plant){1,x-1,y-1,Cnt,0};
            Q[++Cnt]=(Plant){1,pl,y-1,Cnt,0};
            Q[++Cnt]=(Plant){1,x-1,pr,Cnt,0};
        }
    }
    CDQ(1,Cnt);sort(Q+1,Q+Cnt+1,Cop);
    for(int i=1;i<=Cnt;i++)if(Q[i].Opt==1){
        printf("%d\n",Q[i].w+Q[i+1].w-Q[i+2].w-Q[i+3].w),i+=3;
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*