首页 > 代码库 > ACDream - Crayon
ACDream - Crayon
题目:
Description
There are only one case in each input file, the first line is a integer N (N ≤ 1,000,00) denoted the total operations executed by Mary.
Then following N lines, each line is one of the folling operations.
- D L R : draw a segment [L, R], 1 ≤ L ≤ R ≤ 1,000,000,000.
- C I : clear the ith added segment. It’s guaranteed that the every added segment will be cleared only once.
- Q L R : query the number of segment sharing at least a common point with interval [L, R]. 1 ≤ L ≤ R ≤ 1,000,000,000.
Input
n
Then following n operations ...
Output
For each query, print the result on a single line ...
Sample Input
6D 1 3D 2 4Q 2 3D 2 4C 2Q 2 3
Sample Output
22
题意:给出三种操作:①画一条占据[L,R]区间的线段,②去掉前面画的第i条线段(保证合法),③查询一条占据区间[L,R]的线段与前面多少条线段至少有一个公共点。对于③操作,输出结果。
区间范围[1,1000000000],操作最多100000次。
区间很大,但是操作相对比较少,所以可以先对坐标离散化,然后缩小了范围以后再对数据操作。
怎样去统计有多少条线段覆盖了某一段?这里用的方法是统计线段的两个端点,用树状数组来记录。这里需要开两个树状数组,一个用来记录左端点,一个用来记录右端点,然后每一次求某一段[L,R]有多少条线段经过的话,我们可以先求出有多少条线段的左端点在R的左边,这里只要求前段和就可以了,然后我们再求一下有多少线段的右端点在L的左边,同样求一次和,然后相减就可以得到结果了。
为什么可以这样做?首先是因为线段有两个端点,然后两次求和都直接排除了R右边的无关线段,而在L左边的线段的两个端点都在L的左边,所以就会先算了一次,然后再被减回去。
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #define lowbit(x) (x & (-x)) 7 #define MAX 100201 8 #define LL long long 9 using namespace std;10 11 typedef struct{12 LL l,r,k;13 char ch;14 }Seg;15 Seg s[MAX];16 LL l[MAX<<1],r[MAX<<1];17 vector<LL> d;18 LL tot,no,N[MAX];19 20 void add(LL p[],LL x,LL e){21 for(;x<=tot;x+=lowbit(x)) p[x]+=e;22 }23 24 LL query(LL p[],LL x){25 LL ans=0;26 for(;x>0;x-=lowbit(x)) ans+=p[x];27 return ans;28 }29 30 int main()31 {32 LL n,loc,ans;33 //freopen("data.txt","r",stdin);34 ios::sync_with_stdio(false);35 while(cin>>n){36 d.clear();37 d.push_back(-(1<<30));38 memset(l,0,sizeof(l));39 memset(r,0,sizeof(r));40 no=0;41 for(LL i=0;i<n;i++){42 cin>>s[i].ch;43 if(s[i].ch==‘C‘){44 cin>>s[i].k;45 }else{46 cin>>s[i].l>>s[i].r;47 if(s[i].ch==‘D‘) N[++no]=i;48 d.push_back(s[i].l);49 d.push_back(s[i].r);50 }51 }52 sort(d.begin(),d.end());53 d.erase(unique(d.begin(),d.end()),d.end());54 tot = (LL)d.size()-1;55 for(LL i=0;i<n;i++){56 if(s[i].ch==‘D‘){57 loc = lower_bound(d.begin(),d.end(),s[i].l) - d.begin();58 add(l,loc,1);59 loc = lower_bound(d.begin(),d.end(),s[i].r) - d.begin();60 add(r,loc,1);61 }else if(s[i].ch==‘C‘){62 LL& e = N[s[i].k];63 loc = lower_bound(d.begin(),d.end(),s[e].l) - d.begin();64 add(l,loc,-1);65 loc = lower_bound(d.begin(),d.end(),s[e].r) - d.begin();66 add(r,loc,-1);67 68 }else{69 loc = lower_bound(d.begin(),d.end(),s[i].r) - d.begin();70 ans = query(l,loc);71 loc = lower_bound(d.begin(),d.end(),s[i].l) - d.begin();72 ans-= query(r,loc-1);73 cout<<ans<<endl;74 }75 }76 //cout<<endl;77 }78 return 0;79 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。