陈丹琦分治~~~其实一些数据小的时候可以用二维或者多维树状数组做的，而数据大的时候就无力的题目，都可以用陈丹琦分治解决。
题目：由3钟类型操作：
1）D L R(1 <= L <= R <= 1000000000) 增加一条线段[L,R]
2）C i (1-base) 删除第i条增加的线段，保证每条插入线段最多插入一次，且这次删除操作一定合法
3) Q L R(1 <= L <= R <= 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段，线段X被线段Y完全包含即LY <= LX
<= RX <= RY)
给出N，接下来N行，每行是3种类型之一
由于 L R 比较大，直接是不行的，于是我们可以利用CDQ分治把二维变成一维，然后离散化。树状数组查询。
对于询问 L R 只需要 知道 小于等于L 且大于等于R的有多少个就可以了。这里我是把线段左端点进行CDQ分治，然后每次查询大于R数目。
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+;
struct Node
{
int idx,l,r,delt;
int kind;
bool operator < (const Node &rhs)const
{
return l < rhs.l ;
}
}node[maxn];
int ans[maxn],del[maxn];
//-------------BIT--------- //此处树状数组反向写的，用于查询 大于等于x的数有多少个
inline int lowbit (int x)
{
return x & -x;
}
int arr[maxn],MAX;
void add (int x,int d)
{
while (x)
{
arr[x] += d;
x -= lowbit(x);
}
}
int sum(int x)
{
int ans = ;
while (x <= MAX)
{
ans += arr[x];
x += lowbit(x);
}
return ans;
}
//--------------离散化-----
int vec[maxn],vec_idx;
int hash_(int x)
{
return lower_bound(vec,vec+vec_idx,x) - vec + ;
}
//------------------------
void CDQ(int l,int r)
{
if (l == r)
return;
int mid = (l + r) >> ;
CDQ(l,mid);
CDQ(mid+,r);
int j = l;
for (int i = mid+; i <= r; i++)
{
if (node[i].kind == )
{
for ( ;j <= mid && node[j].l <= node[i].l; j++)
{
if (node[j].kind == )
{
add(hash_(node[j].r),node[j].delt);
}
}
ans[node[i].idx] += sum(hash_(node[i].r));
}
}
for (int i = l; i < j; i++)
if ( node[i].kind == )
add(hash_(node[i].r),-node[i].delt);
inplace_merge(node+l,node+mid+,node+r+);
}
int vis[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n;
while (~scanf ("%d",&n))
{
int cnt = ;
vec_idx = ;
memset(arr,,sizeof(arr));
memset(ans,,sizeof(ans));
memset(vis,,sizeof(vis));
vector<int>vv;
for (int i = ; i <= n; i++)
{
char op[];
scanf ("%s",op);
if (op[] == 'D')
{
scanf ("%d%d",&node[i].l,&node[i].r);
node[i].kind = ;
node[i].idx = i;
node[i].delt = ;
vec[vec_idx++] = node[i].r;
vv.push_back(i);
}
if (op[] == 'Q')
{
scanf ("%d%d",&node[i].l,&node[i].r);
node[i].kind = ;
node[i].idx = i;
vec[vec_idx++] = node[i].r;
vis[i] = ;
}
if (op[] == 'C')
{
int tmp;
scanf ("%d",&tmp);
node[i].kind = ;
node[i].l = node[vv[tmp-]].l;
node[i].r = node[vv[tmp-]].r;
node[i].delt = -; // 对于删除的边类型与增加的相同但是，操作的时候是-1
node[i].idx = i;
}
}
sort(vec,vec+vec_idx);
vec_idx = unique(vec,vec+vec_idx) - vec;
MAX = vec_idx + ;
CDQ(,n);
for (int i = ; i <= n; i++)
{
if (vis[i])
printf("%d\n",ans[i]);
}
}
return ;
}