Sample Input
3 0 0 0 3 0 1 5 0 1 0 0 1 1 0 1 0 0
Sample Output
Case #1: 0 0 0 Case #2: 0 1 0 2
有0,1两个操作,0 x代表添加从x 到 x + i(带表第i次添加)的线段,每次添加时问被其覆盖的线段有多少。
1 x代表删除第i次添加的。
思路:每一次添加后,求出小于x的左节点个数x1,小于等于y的右节点个数x2。 x2- x1即可
改变单个节点,所以树状数组更加合适
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; #define N 200050 #define mod 258280327 int le[N],re[N],lr[N],rr[N]; int oper[N],Left[N],Right[N],id[N]; int c[N]; int tot; int lowbit(int x) { return x&-x; } void update(int *c,int n,int k,int v) { while(k <= n) { c[k] += v; k += lowbit(k); } } int query(int *c ,int k) { int ans = 0; while(k > 0) { ans += c[k]; k -= lowbit(k); } return ans; } int main() { //freopen("4.txt","r",stdin); int cas=1,L=1,l,ans,nul,nur,n,Q; while(scanf("%d",&n)!=EOF) { Q = nul = nur = 0; for(int i = 1; i <= n; i++) { scanf("%d%d",&oper[i],&l); if(oper[i] == 0) { id[++Q] = i; le[i] = l; re[i] = l+L; Left[nul++] = le[i]; Right[nur++] = re[i]; L++; } else { le[i] = l; } } printf("Case #%d:\n",cas++); memset(lr,0,sizeof(lr)); memset(rr,0,sizeof(rr)); sort(Left, Left + nul); nul = unique(Left, Left + nul) - Left; sort(Right, Right + nur); nur = unique(Right, Right + nur) - Right; for(int i = 1; i <= n; i++) { if(oper[i] == 0) { int x1 = lower_bound(Left,Left+nul,le[i]) - Left + 1; int x2 = lower_bound(Right,Right+nur,re[i]) - Right + 1; ans = query(rr,x2)-query(lr,x1-1); update(rr,nur,x2,1); update(lr,nul,x1,1); printf("%d\n",ans); } else { int v = id[le[i]]; int x1 = lower_bound(Left,Left+nul,le[v]) - Left + 1; int x2 = lower_bound(Right,Right+nur,re[v]) - Right + 1; update(lr,nul,x1,-1); update(rr,nur,x2,-1); } } } return 0; }