首页 > 代码库 > BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]

BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]

传送门


 

刚才我还在郁闷网上怎么没人用$CDQ$分治做

突然发现根本没有时间序....

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=3e6+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<0||c>9){if(c==-)f=-1; c=getchar();}    while(c>=0&&c<=9){x=x*10+c-0; c=getchar();}    return x*f;}int n,Q,c[N],mp[N];int m,qid;struct Operation{    int x,y,v,id;    int qid,op;    Operation():op(0){}    Operation(int x,int y,int v,int id,int qid,int op):        x(x),y(y),v(v),id(id),qid(qid),op(op){}    bool operator <(const Operation &r)const{        return x==r.x?op<r.op:x<r.x;    }}a[N];void devideQuery(){    int x1=read()-1,y1=read()-1,x2=read(),y2=read();    mp[++mp[0]]=y1;mp[++mp[0]]=y2;    qid++;    m++;a[m]=Operation(x2,y2,1,m,qid,1);    m++;a[m]=Operation(x1,y2,-1,m,qid,1);    m++;a[m]=Operation(x2,y1,-1,m,qid,1);    m++;a[m]=Operation(x1,y1,1,m,qid,1);}void iniMP(){    sort(mp+1,mp+1+mp[0]);    int p=0;    mp[++p]=mp[1];    for(int i=2;i<=mp[0];i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i];    mp[0]=p;}int Bin(int v){    int l=1,r=mp[0];    while(l<=r){        int mid=(l+r)>>1;        if(v==mp[mid]) return mid;        else if(v<mp[mid]) r=mid-1;        else l=mid+1;    }    return 0;}inline int lowbit(int x){return x&-x;}void add(int p,int v){for(;p<=n;p+=lowbit(p)) c[p]+=v;}int sum(int p){    int re=0;    for(;p;p-=lowbit(p)) re+=c[p];    return re;}int ans[N];void solve(){    for(int i=1;i<=m;i++){        if(!a[i].op) add(a[i].y,1);        else ans[a[i].qid]+=a[i].v*sum(a[i].y);    }    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);}int main(){    freopen("in","r",stdin);    n=read();Q=read();    for(int i=1;i<=n;i++) a[++m].x=read(),mp[++mp[0]]=a[m].y=read();    for(int i=1;i<=Q;i++) devideQuery();    iniMP();    for(int i=1;i<=m;i++) a[i].y=Bin(a[i].y);    sort(a+1,a+1+m);    solve();}

 

BZOJ 1935: [Shoi2007]Tree 园丁的烦恼 [树状数组 离线 离散化]