Sample Input
3
0 0
0 3
0 1
5
0 1
0 0
1 1
0 1
0 0
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
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;
}