题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5372

题意：给你n次操作，每次增加线段或者删除第i次增加操作中增加的线段，问你每次增加操作中，所增加的线段会覆盖多少条完整的线段。

解法：对于新插入的线段，查询有多少个线段左端点大于等于该线段的左端点。 再查询有多少个线段的右端点大于该线段右端点， 两者之差就是答案。用两个树状数组搞定。时间复杂度nlogn


#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+10;
int a[maxn],b[maxn],op[maxn],c[2][maxn];
vector<int>v;
int getid(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
inline lowbit(int x){
    return x&-x;
}
void add(int x, int v, int o){
    while(x<maxn){
        c[o][x]+=v;
        x+=lowbit(x);
    }
}
int query(int x, int o){
    int ret=0;
    while(x){
        ret += c[o][x];
        x-=lowbit(x);
    }
    return ret;
}

int main()
{
    int n,ks=0;
    while(~scanf("%d", &n))
    {
        int clk=0;
        for(int i=1; i<=n; i++){
            scanf("%d %d", &op[i], &a[i]);
            if(op[i]==0){
                b[i]=a[i]+(++clk);
                v.push_back(a[i]);
                v.push_back(b[i]);
            }
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        memset(c,0,sizeof(c));
        clk = 1;
        printf("Case #%d:\n", ++ks);
        for(int i=1; i<=n; i++){
            if(op[i]==0){
                int l=getid(a[i]),r=getid(b[i]);
                printf("%d\n", query(r,1)-query(l-1,0));
                a[clk]=l;
                b[clk++]=r;
                add(l,1,0);
                add(r,1,1);
            }
            else{
                add(a[a[i]], -1, 0);
                add(b[a[i]], -1, 1);
            }
        }
    }
    return 0;
}