CDQ分治

发布时间:2017-6-25 21:45:18 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"CDQ分治 ",主要涉及到CDQ分治 方面的内容,对于CDQ分治 感兴趣的同学可以参考一下。

要求可以计算前面的操作对后面询问的贡献

BZOJ1176

#include <cstdio>#include <algorithm>using namespace std;  int tr[2000001],p,ans[10001],s,q,opt,n,que;    struct data1{      int po,x,y,num,v,opt;  }a[200001],tmp[200001];  struct data{      int num,po;  }yt[200001];    int mycomp(const data&a,const data&b){      return(a.num<b.num);  }  int lowbit(int po){      return(po&(-po));  }  int query(int po){      int ret=0;      for (;po;po-=lowbit(po)) ret+=tr[po];      return(ret);  }    void add(int po,int num){      for (;po<=p;po+=lowbit(po)) tr[po]+=num;  }  void solve(int l,int r){      if (l==r) return;      int mid=(l+r)>>1;      solve(l,mid);solve(mid+1,r);      int po=l;      for (int i=mid+1;i<=r;i++)        if (a[i].opt==2){          while (po<=mid&&a[po].x<=a[i].x){            if (a[po].opt==1) add(a[po].y,a[po].num);          po++;            }        ans[a[i].po]+=query(a[i].y)*a[i].v;          }    for (int i=l;i<po;i++)      if (a[i].opt==1) add(a[i].y,-a[i].num);        int po1=l,po2=mid+1,po3=l;    while (po1<=mid&&po2<=r){      if (a[po1].x<a[po2].x) tmp[po3++]=a[po1++];else tmp[po3++]=a[po2++];    }       while (po1<=mid) tmp[po3++]=a[po1++];    while (po2<=r) tmp[po3++]=a[po2++];    for (int i=l;i<=r;i++) a[i]=tmp[i];  }  int main(){      scanf("%d%d",&s,&q);      while (scanf("%d",&opt),opt!=3){      if (opt==1){          n++;          a[n].opt=1;          scanf("%d%d%d",&a[n].x,&yt[n].num,&a[n].num);          yt[n].po=n;      }else{          int t1,t2,t3,t4;        scanf("%d%d%d%d",&t1,&t2,&t3,&t4);        que++;        a[++n].po=que;a[n].v=1;a[n].x=t3;yt[n].num=t4;yt[n].po=n;a[n].opt=2;        a[++n].po=que;a[n].v=-1;a[n].x=t1-1;yt[n].num=t4;yt[n].po=n;a[n].opt=2;        a[++n].po=que;a[n].v=-1;a[n].x=t3;yt[n].num=t2-1;yt[n].po=n;a[n].opt=2;        a[++n].po=que;a[n].v=1;a[n].x=t1-1;yt[n].num=t2-1;yt[n].po=n;a[n].opt=2;      }    }        sort(yt+1,yt+n+1,mycomp);    yt[0].num=-1e9;    p=0;    for (int i=1;i<=n;i++){      if (yt[i].num!=yt[i-1].num) p++;      a[yt[i].po].y=p;        }        solve(1,n);        for (int i=1;i<=que;i++) printf("%d\n",ans[i]);  }

上一篇:[C#] 了解过入口函数 Main() 吗?带你用批处理玩转 Main 函数
下一篇:basic use of sidekiq (2)

相关文章

关键词: CDQ分治

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。