首页 > 代码库 > 【ACdream】1157 Segments cdq分治
【ACdream】1157 Segments cdq分治
Segments
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被线段Y完全包含即LY <= LX
<= RX <= RY)
给出N，接下来N行，每行是3种类型之一
Input
多组数据，每组数据N
接下来N行，每行是三种操作之一(1 <= N <= 10^5)
Output
对于每个Q操作，输出一行，答案
Sample Input
6D 1 100D 3 8D 4 10Q 3 8C 1Q 3 8
Sample Output
21
Hint
注意，删除第i条增加的线段，不是说第i行，而是说第i次增加。
比如
D 1 10
Q 1 10
D 2 3
D 3 4
Q 5 6
D 5 6
C 2是删除D 2 3
C 4是删除D 5 6
Source
dream
Manager
题解：
CDQ分治流程如下：
1.将整个操作序列分为两个长度相等的部分（分）
2.递归处理前一部分的子问题（治1）
3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）
4.递归处理后一部分子问题（治3）
cdq入门练习当中
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 5e5+10, M = 1e3+20,inf = 2e9;int L[N],R[N],ans[N];struct ss{ int l,r,t,qid,type; ss(){} ss(int a,int b,int c,int d,int e) : l(a),r(b),t(c),qid(d),type(e){} bool operator < (const ss &j) const { if(l==j.l) return t < j.t; else return l < j.l; }}a[N],t[N];int C[N];int san[N],n;void add(int x,int c) { for(int i = x; i <= 4*n; i += i&(-i)) { C[i] += c; }}int sum(int x) { int ret = 0; for(int i = x; i; i -= i&(-i)) ret += C[i]; return ret;}void cdq(int ll,int rr) { if(ll == rr) return ; //cout<<ll<<" "<<rr<<endl; for(int i = ll; i <= rr; ++i) { if(a[i].t <= mid && a[i].type!=0) add(a[i].r,a[i].type); else if(a[i].t > mid && a[i].type==0) { ans[a[i].qid] += sum(4*n)-sum(a[i].r-1); } } for(int i = ll; i <= rr; ++i) { if(a[i].t <= mid && a[i].type!=0) { add(a[i].r,-a[i].type); } } int L1 = ll, R1 = mid+1; for(int i = ll; i <= rr; ++i) { if(a[i].t <= mid) t[L1++] = a[i]; else t[R1++] = a[i]; } for(int i = ll; i <= rr; ++i) a[i] = t[i]; cdq(ll,mid),cdq(mid+1,rr);}char ch[10];int x,y;int main() { while(scanf("%d",&n)!=EOF) { scanf("%d",&n); for(int i = 0; i <= 4*n; ++i) C[i] = 0; int cnt = 0; int qcnt = 0;int scnt = 0; for(int i = 1; i <= n; ++i) { scanf("%s",ch); if(ch[0] == ‘D‘) { scanf("%d%d",&x,&y); L[++cnt] = x; R[cnt] = y; san[++scnt] = x; san[++scnt] = y; a[i] = ss(x,y,i,0,1); } else if(ch[0] == ‘C‘) { scanf("%d",&x); a[i] = ss(L[x],R[x],i,0,-1); } else if(ch[0] == ‘Q‘) { scanf("%d%d",&x,&y); san[++scnt] = x; san[++scnt] = y; a[i] = ss(x,y,i,++qcnt,0); } } sort(san+1,san+scnt+1); int SC = unique(san+1,san+1+scnt) - san - 1; for(int i = 1; i <= n; ++i) { a[i].l = lower_bound(san+1,san+SC+1,a[i].l) - san; a[i].r = lower_bound(san+1,san+SC+1,a[i].r) - san; } sort(a+1,a+n+1); for(int i = 1; i <= qcnt; ++i) ans[i] = 0; cdq(1,n); for(int i = 1; i <= qcnt; ++i) printf("%d\n",ans[i]); } return 0;}
【ACdream】1157 Segments cdq分治
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。