首页 > 代码库 > 2014-2015 Codeforces Trainings Season 2 Episode 7 G Gophers --线段树
2014-2015 Codeforces Trainings Season 2 Episode 7 G Gophers --线段树
题意： 有n个地鼠，m个CD碟，每个CD碟有一个影响范围，范围内的地鼠都会被吵到，每次有一个操作就是移动CD碟，然后求每次被影响的地鼠有多少只。
解法： 线段树做。我们只关注地鼠有没有被吵到就可以了，之前我还去把所有可能移到的位置都存下来离散化一下，然后维护也维护错了。一堆bug，真是想多了。
线段树维护两个值： cntS[rt]表示该段被多少个区间所覆盖， NOG[rt]表示此区间内没有被影响到的地鼠有多少个。
那么我们更新到区间，然后直接pushup即可， 因为更新到区间的时候已经可以确定NOG[rt]了：
如果 l == r ： 说明是叶子节点， 那么如果cntS[rt] > 0，NOG[rt]就为0，否则为1
否则，如果cntS[rt] = 0 , 那么 NOG[rt] = NOG[2*rt]+NOG[2*rt+1], 否则说明这段被区间覆盖，NOG[rt] = 0.
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;#define N 501007int NOG[4*N],cntS[4*N];struct Shift{ int L1,R1,L2,R2;}sf[510009];int x[510009],b[2510009];int seg[510009][2];void pushup(int l,int r,int rt){ if(l == r) { if(cntS[rt]) NOG[rt] = 0; else NOG[rt] = 1; return; } if(!cntS[rt]) NOG[rt] = NOG[rt<<1] + NOG[rt<<1|1]; else NOG[rt] = 0;}void build(int l,int r,int rt){ cntS[rt] = 0; if(l == r) { NOG[rt] = 1; return; } int mid = (l+r)/2; build(l,mid,2*rt); build(mid+1,r,2*rt+1); pushup(l,r,rt);}void update(int l,int r,int aa,int bb,int val,int rt){ if(aa <= l && bb >= r) { cntS[rt] += val; pushup(l,r,rt); return; } int mid = (l+r)/2; if(aa <= mid) update(l,mid,aa,bb,val,2*rt); if(bb > mid) update(mid+1,r,aa,bb,val,2*rt+1); pushup(l,r,rt);}int main(){ int n,m,d,l,i,j,val,p,r; while(scanf("%d%d%d%d",&n,&m,&d,&l)!=EOF) { x[1] = 0; for(i=2;i<=n;i++) scanf("%d",&x[i]); for(i=1;i<=m;i++) { scanf("%d",&val); seg[i][0] = max(0,val-l); seg[i][1] = min(1000000000,val+l); } for(i=1;i<=d;i++) { scanf("%d%d",&p,&r); sf[i].L1 = max(0,p-l); sf[i].R1 = min(1000000000,p+l); sf[i].L2 = max(0,r-l); sf[i].R2 = min(1000000000,r+l); } build(1,n,1); for(i=1;i<=m;i++) { int L = lower_bound(x+1,x+n+1,seg[i][0])-x; int R = upper_bound(x+1,x+n+1,seg[i][1])-x; R--; update(1,n,L,R,1,1); } printf("%d\n",n-NOG[1]); for(i=1;i<=d;i++) { int L1 = lower_bound(x+1,x+n+1,sf[i].L1)-x; int R1 = upper_bound(x+1,x+n+1,sf[i].R1)-x-1; int L2 = lower_bound(x+1,x+n+1,sf[i].L2)-x; int R2 = upper_bound(x+1,x+n+1,sf[i].R2)-x-1; update(1,n,L1,R1,-1,1); update(1,n,L2,R2,1,1); printf("%d\n",n-NOG[1]); } } return 0;}
2014-2015 Codeforces Trainings Season 2 Episode 7 G Gophers --线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。