题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5372
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ll long long
const int maxn =2e5+5;
const int mod=1e9+7;
ll powmod(ll x,ll y) {ll t;for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod;return t;}
ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y); }
///树状数组的结构
int l[maxn],r[maxn];///统计左端点和右端点的数量。
/*
题目大意：n次操作，每次操作有两种，
一种是添加线段，线段的长度就是添加操作的序号，额外输入一个左端点，
一种是删除第几次添加操作的线段。这道题比较绕人，特别考验逻辑，
首先观察到残忍的数据范围开到九次方，离散化处理没跑了。
先分析下，如何统计完整的区间段，我们模拟一下，
如果查询a到b范围内的线段数量，
分类下，如果一个线段c-d，关系是这样：c-d-a-b，
那么明显不计数，c-a-d-b也不计数，a-c-d-b计数，
a-c-b-d不计数，a-b-c-d不计数。只要统计b区间的右端点，和a区间的左端点数量就行了，
不难发现所有的情况这种算法都符合要求。下面就是离散化的过程，把询问都存储起来，
把每个左端点和右端点，都离散映射成大小序号关系。
至于删除操作的存在，我们要额外存储添加操作的集合，
单射就可以 ，因为序号就是区间的长度。
*/int lowbit(int x)
{return x&-x;
}
int sum(int x,int mark)
{int ret=0;for(;x>0;x-=lowbit(x)){if(mark) ret+=r[x];else ret+=l[x];}return ret;
}
void add(int x,int d,int mark)
{for(;x<maxn;x+=lowbit(x)){if(mark) r[x]+=d;else l[x]+=d;}
}
int op[maxn],s[maxn];///询问集合和区间端点集合。
int L[maxn],cntL,R[maxn],cntR;///存储左右的边
int q[maxn],Q;///添加的边的集合int n;
void init()
{Q=cntR=cntL=0;for(int i=1;i<=n;i++){scanf("%d%d",&op[i],&s[i]);if(op[i]==0){q[++Q]=s[i];///s[i]是左端点或者编号R[cntR++] = s[i]+Q;L[cntL++] = s[i];}}sort(L,L+cntL);cntL=unique(L,L+cntL)-L;sort(R,R+cntR);cntR=unique(R,R+cntR)-R;memset(l,0,sizeof(l));memset(r,0,sizeof(r));///初始化树状数组
}void solve()
{int cnt=0;for(int i=1;i<=n;i++){if(op[i]){int v=q[s[i]];int p=lower_bound(L,L+cntL,v)-L+1;int q=lower_bound(R,R+cntR,v+s[i])-R+1;add(p,-1,0);add(q,-1,1);}else{int lb=q[++cnt],rb=lb+cnt;int p=lower_bound(L,L+cntL,lb)-L+1;int q=lower_bound(R,R+cntR,rb)-R+1;int ans=sum(q,1)-sum(p-1,0);///答案存储add(p,1,0);add(q,1,1);printf("%d\n",ans);}}
}int main()
{int ca=1;while(scanf("%d",&n)!=EOF){init();///初始化printf("Case #%d:\n",ca++);solve();}return 0;
}