ACdream1157 Segments（CDQ分治 + 线段树）

题目这么说的：

进行如下3种类型操作：
1）D L R(1 <= L <= R <= 1000000000) 增加一条线段[L,R]
2）C i (1-base) 删除第i条增加的线段，保证每条插入线段最多插入一次，且这次删除操作一定合法
3) Q L R(1 <= L <= R <= 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段，线段X被线段Y完全包含即LY <= LX <= RX <= RY)

初学CDQ分治是看了Balkan OI 2007 Mokia那题的解法。两题类似，这题做法也不难想出：

每次对操作的区间进行分治时，统计左半边更新操作对右半边查询操作的影响，影响的前提是更新操作的L小于等于查询操作的L且R要大于等于查询的R，这个通过一开始把L按从小到大排序，分治时便可从大到小遍历，同时用线段树维护R出现次数即可。

其实我一开始看错题，以为询问的是有几条线段包含在给定区间里面，写完后发现才样例过不了。。不过改一下就好了，然后1A感觉还是不错的。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int tree[<<],N,x,y;

 void update(int i,int j,int k){

     if(i==j){

         tree[k]+=y;

         return;

     }

     int mid=i+j>>;

     if(x<=mid) update(i,mid,k<<);

     else update(mid+,j,k<<|);

     tree[k]=tree[k<<]+tree[k<<|];

 }

 int query(int i,int j,int k){

     if(x<=i && j<=y){

         return tree[k];

     }

     int mid=i+j>>,res=;

     if(x<=mid) res+=query(i,mid,k<<);

     if(y>mid) res+=query(mid+,j,k<<|);

     return res;

 }

 struct Query{

     int idx,type,anspos;

     int x,y;

     bool operator<(const Query &q)const{

         return x<q.x;

     }

 }que[],tmp[];

 int ans[];

 void cdq(int l,int r){

     if(l>=r) return;

     int mid=l+r>>,i=l,j=mid+;

     for(int k=l; k<=r; ++k){

         if(que[k].idx<=mid) tmp[i++]=que[k];

         else tmp[j++]=que[k];

     }

     for(int k=l; k<=r; ++k) que[k]=tmp[k];

     for(i=mid+,j=l; i<=r; ++i){

         if(que[i].type!=) continue;

         for( ; j<=mid && que[j].x<=que[i].x; ++j){

             if(que[j].type==) continue;

             x=que[j].y; y=(que[j].type==) ?  : -;

             update(,N-,);

         }

         x=que[i].y; y=N-;

         ans[que[i].anspos]+=query(,N-,);

     }

     for(i=l; i<j; ++i){

         if(que[i].type==) continue;

         x=que[i].y; y=(que[i].type==) ? - : ;

         update(,N-,);

     }

     cdq(l,mid); cdq(mid+,r);

 }

 int segx[],segy[],sn;

 int point[],pn;

 int main(){

     char op;

     int n,a,b;

     while(~scanf("%d",&n)){

         int cnt=;

         memset(ans,,sizeof(ans));

         sn=; pn=;

         for(int i=; i<n; ++i){

             scanf(" %c",&op);

             if(op=='D'){

                 scanf("%d%d",&a,&b);

                 segx[++sn]=a; segy[sn]=b;

                 point[pn++]=a; point[pn++]=b;

                 que[i].idx=i; que[i].type=; que[i].x=a; que[i].y=b;

             }else if(op=='C'){

                 scanf("%d",&a);

                 que[i].idx=i; que[i].type=; que[i].x=segx[a]; que[i].y=segy[a];

             }else{

                 scanf("%d%d",&a,&b);

                 point[pn++]=a; point[pn++]=b;

                 que[i].idx=i; que[i].type=; que[i].x=a; que[i].y=b; que[i].anspos=++cnt;

             }

         }

         sort(point,point+pn);

         pn=unique(point,point+pn)-point;

         for(N=; N<pn; N<<=);

         for(int i=; i<n; ++i){

             que[i].x=lower_bound(point,point+pn,que[i].x)-point;

             que[i].y=lower_bound(point,point+pn,que[i].y)-point;

         }

         sort(que,que+n);

         cdq(,n-);

         for(int i=; i<=cnt; ++i){

             printf("%d\n",ans[i]);

         }

     }

     return ;

 }

巴特西

ACdream1157 Segments（CDQ分治 + 线段树）

最新文章

热门文章