题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5372
题意：进行n次操作，操作分两种，0和1，每一个0操作按出现顺序有一个编号（从1开始
0操作 0 x：询问[x, x+i]（i为该操作的编号）区间内有多少个完整的线段，并加入线段[x, x+i]（线段直接重叠不影响）
1操作 1 x：删除0操作中插入的编号为x的线段，（不影响其他线段，不会重复删除同一线段，删除的线段一定是已经插入的）
解：题目有一个重要的条件：后面插入的线段一定比前面的长。那么考虑现在要插入线段[x, y]，（-oo，x）有a个现存线段的左端点，（y，+oo）有b个现存线段的右端点，现存线段数为num个，则ans=num-a-b；用离散化+树状数组搞的话可以求出（-oo，y]内的右端点数c，有c=num-b；联立前式解得ans=c-a；
/*
* Problem: hdu5372 Segment Game
* Author: SHJWUDP
* Created Time: 2015/8/11 星期二 21:57:35
* File Name: 1006.cpp
* State: Accepted
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; struct Hash : vector<int> {
void prepare() {
sort(begin(), end());
erase(unique(begin(), end()), end());
}
int get(int x) {
return lower_bound(begin(), end(), x)-begin()+;
}
};
struct Fenwick {
int n;
vector<int> c;
void init(int n) {
this->n=n;
c.assign(n+, );
}
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
while(x<=n) {
c[x]+=v; x+=lowbit(x);
}
}
int getsum(int x) {
int res=;
while(x>) {
res+=c[x]; x-=lowbit(x);
}
return res;
}
} fwl, fwr; int n;
vector<pair<int, int> > arr;
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int now=;
while(~scanf("%d", &n)) {
arr.resize(n+);
vector<pair<int, int> > A;
Hash hash;
int tmpLen=;
for(int i=; i<=n; i++) {
scanf("%d%d", &arr[i].first, &arr[i].second);
if(arr[i].first==) {
A.push_back(make_pair(arr[i].second,
arr[i].second+(++tmpLen)));
hash.push_back(A.back().first);
hash.push_back(A.back().second);
}
}
hash.prepare();
fwl.init(hash.size()+);
fwr.init(hash.size()+);
int pos=;
printf("Case #%d:\n", ++now);
for(int i=; i<=n; i++) {
int a=arr[i].first;
int b=arr[i].second;
if(a==) {
int x=A[pos].first=hash.get(A[pos].first);
int y=A[pos].second=hash.get(A[pos].second);
pos++;
printf("%d\n", fwr.getsum(y)-fwl.getsum(x-));
fwl.add(x, );
fwr.add(y, );
} else {
int x=A[b-].first;
int y=A[b-].second;
fwl.add(x, -);
fwr.add(y, -);
}
}
}
return ;
}