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感觉还是不错的。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5
  6 int tree[222222<<2],N,x,y;
  7 void update(int i,int j,int k){
  8     if(i==j){
  9         tree[k]+=y;
 10         return;
 11     }
 12     int mid=i+j>>1;
 13     if(x<=mid) update(i,mid,k<<1);
 14     else update(mid+1,j,k<<1|1);
 15     tree[k]=tree[k<<1]+tree[k<<1|1];
 16 }
 17 int query(int i,int j,int k){
 18     if(x<=i && j<=y){
 19         return tree[k];
 20     }
 21     int mid=i+j>>1,res=0;
 22     if(x<=mid) res+=query(i,mid,k<<1);
 23     if(y>mid) res+=query(mid+1,j,k<<1|1);
 24     return res;
 25 }
 26
 27 struct Query{
 28     int idx,type,anspos;
 29     int x,y;
 30     bool operator<(const Query &q)const{
 31         return x<q.x;
 32     }
 33 }que[111111],tmp[111111];
 34
 35 int ans[111111];
 36
 37 void cdq(int l,int r){
 38     if(l>=r) return;
 39     int mid=l+r>>1,i=l,j=mid+1;
 40     for(int k=l; k<=r; ++k){
 41         if(que[k].idx<=mid) tmp[i++]=que[k];
 42         else tmp[j++]=que[k];
 43     }
 44     for(int k=l; k<=r; ++k) que[k]=tmp[k];
 45
 46     for(i=mid+1,j=l; i<=r; ++i){
 47         if(que[i].type!=3) continue;
 48         for( ; j<=mid && que[j].x<=que[i].x; ++j){
 49             if(que[j].type==3) continue;
 50             x=que[j].y; y=(que[j].type==1) ? 1 : -1;
 51             update(0,N-1,1);
 52         }
 53         x=que[i].y; y=N-1;
 54         ans[que[i].anspos]+=query(0,N-1,1);
 55     }
 56     for(i=l; i<j; ++i){
 57         if(que[i].type==3) continue;
 58         x=que[i].y; y=(que[i].type==1) ? -1 : 1;
 59         update(0,N-1,1);
 60     }
 61     cdq(l,mid); cdq(mid+1,r);
 62 }
 63
 64 int segx[111111],segy[111111],sn;
 65 int point[222222],pn;
 66 int main(){
 67     char op;
 68     int n,a,b;
 69     while(~scanf("%d",&n)){
 70         int cnt=0;
 71         memset(ans,0,sizeof(ans));
 72         sn=0; pn=0;
 73         for(int i=0; i<n; ++i){
 74             scanf(" %c",&op);
 75             if(op==‘D‘){
 76                 scanf("%d%d",&a,&b);
 77                 segx[++sn]=a; segy[sn]=b;
 78                 point[pn++]=a; point[pn++]=b;
 79                 que[i].idx=i; que[i].type=1; que[i].x=a; que[i].y=b;
 80             }else if(op==‘C‘){
 81                 scanf("%d",&a);
 82                 que[i].idx=i; que[i].type=2; que[i].x=segx[a]; que[i].y=segy[a];
 83             }else{
 84                 scanf("%d%d",&a,&b);
 85                 point[pn++]=a; point[pn++]=b;
 86                 que[i].idx=i; que[i].type=3; que[i].x=a; que[i].y=b; que[i].anspos=++cnt;
 87             }
 88         }
 89
 90         sort(point,point+pn);
 91         pn=unique(point,point+pn)-point;
 92         for(N=1; N<pn; N<<=1);
 93
 94         for(int i=0; i<n; ++i){
 95             que[i].x=lower_bound(point,point+pn,que[i].x)-point;
 96             que[i].y=lower_bound(point,point+pn,que[i].y)-point;
 97         }
 98
 99         sort(que,que+n);
100         cdq(0,n-1);
101
102         for(int i=1; i<=cnt; ++i){
103             printf("%d\n",ans[i]);
104         }
105     }
106     return 0;
107 }
时间: 07-22

ACdream1157 Segments(CDQ分治 + 线段树)的相关文章

Codechef SEP14 QRECT cdq分治+线段树

题意 支持删除矩阵.插入矩阵.查询当前矩阵与之前有多少个矩阵相交 算相交的时候容斥一下:相交矩形数 = 总矩形数-X轴投影不相交的矩形数-Y轴投影不相交的矩形数-XY轴投影下都不相交的矩形数 最后一项cdq分治解决 不是我的程序--->http://wyfcyx.is-programmer.com/posts/190325.html

ACdream 1157 Segments CDQ分治

题目链接:https://vjudge.net/problem/ACdream-1157 题意: Problem Description 由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,

BZOJ 4311: 向量( 按时间分治 + 线段树 )

离线, 然后按时间分治, 每个向量都有出现时间[l, r], 直接插入时间线段树(一个向量只会影响O(logN)数量级的线段树节点). 在线段树每个节点弄出凸壳然后二分. 时间复杂度O(Nlog^2N) --------------------------------------------------------------------------- #include<cstdio> #include<cctype> #include<cstring> #includ

【BZOJ3730】震波 动态树分治+线段树

[BZOJ3730]震波 Description 在一片土地上有N个城市,通过N-1条无向边互相连接,形成一棵树的结构,相邻两个城市的距离为1,其中第i个城市的价值为value[i].不幸的是,这片土地常常发生地震,并且随着时代的发展,城市的价值也往往会发生变动.接下来你需要在线处理M次操作:0 x k 表示发生了一次地震,震中城市为x,影响范围为k,所有与x距离不超过k的城市都将受到影响,该次地震造成的经济损失为所有受影响城市的价值和.1 x y 表示第x个城市的价值变成了y.为了体现程序的在

bzoj2006 [ NOI2010 ] &amp;&amp; bzoj3784 --点分治+线段树+堆

bzoj2006: 定义一个四元组{x,l,r,w},表示左端点在x,右端点在[l,r]的超级和弦的最大美妙度在将w作为右端点时取到,w可以用前缀和+线段树/ST表求出. 对于每个i,我们将{i,i+L-1,i+R-1,w}放入一个大根堆中,每次取出美妙度最大的一个加到答案中,并将{i,l,w-1,x},{i,w+1,r,x}放入堆中. 这样就相当于将左端点在i.右端点在w的超级和弦去掉.做k次就可以了. 代码: 1 #include<iostream> 2 #include<cstdi

POJ 1436 Horizontally Visible Segments(线段树)

POJ 1436 Horizontally Visible Segments 题目链接 线段树处理染色问题,把线段排序,从左往右扫描处理出每个线段能看到的右边的线段,然后利用bitset维护枚举两个线段,找出另一个两个都有的线段 代码: #include <cstdio> #include <cstring> #include <algorithm> #include <bitset> #include <vector> using namesp

ACdream 1157 Segments(CDQ分治)

题目链接:http://acdream.info/problem?pid=1157 Problem Description 由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

HDU 5618:Jam&#39;s problem again(CDQ分治+树状数组处理三维偏序)

http://acm.hdu.edu.cn/showproblem.php?pid=5618 题意:-- 思路:和NEUOJ那题一样的.重新写了遍理解了一下,算作处理三维偏序的模板了. 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 #d

BZOJ1176---[Balkan2007]Mokia (CDQ分治 + 树状数组)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1176 CDQ第一题,warush了好久.. CDQ分治推荐论文: 1 <从<Cash>谈一类分治算法的应用> 陈丹琦 2 <浅谈数据结构题的几个非经典解法>  许昊然 关于CDQ分治,两种要求:①操作不相互影响  ②可以离线处理 题目描述是有问题的,,初始时 全部为0,不是s 题意:二维平面内,两种操作,1 x y v ,位于(x,y)的值加上v...2 x1,