hdu 5372 離散化加樹狀數組

注意離散化的時候是對左右端點一起離散化的，是以maxn要開成2倍的~

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=+;
struct node{
    int op,l,r;
}a[maxn];
int c1[maxn<<],c2[maxn<<];
int lowbit(int x){
    return x&(-x);
}
void update(int n,int num,int *c){
    while(n<maxn*){
        c[n]+=num;n+=lowbit(n);
    }
}
int query(int n,int *c){
    int ans=;
    while(n>){
        ans+=c[n];n-=lowbit(n);
    }
    return ans;
}
int n,op,l,r;int cas;
int b[maxn<<];int opt[maxn<<];
vector<int>vec;
int main(){
    cas=;
    while(scanf("%d",&n)!=EOF){
        int num=;vec.clear();int cnt=;
        memset(c1,,sizeof(c1));
        memset(c2,,sizeof(c2));
        for(int i=;i<=n;i++){
            scanf("%d%d",&op,&l);
            if(op==){
                r=l+num;opt[num]=i;num++;
                b[cnt++]=l;b[cnt++]=r;
            }
            a[i].op=op;a[i].l=l;a[i].r=r;
        }
        sort(b,b+cnt);
        cnt=unique(b,b+cnt)-b;
    //  cout<<"sz = "<<cnt<<endl;
    //  for(int i=0;i<cnt;i++){
    //      cout<<"i = "<<i<<" b [i] = "<<b[i]<<endl;
    //  }
    //  int now=lower_bound(b,b+cnt,5)-b+1;
    //  cout<<" now = "<<now<<endl;*/
        int num1;int num2;
        printf("Case #%d:\n",cas++);
        for(int i=;i<=n;i++){
            if(a[i].op==){
                l=lower_bound(b,b+cnt,a[i].l)-b+;
                r=lower_bound(b,b+cnt,a[i].r)-b+;
                num1=query(l-,c1);
                num2=query(r,c2);
                //cout<<" l= "<<l<<" r= "<<r<<endl;
                //cout<<" num1=  "<<num1<<" num2= "<<num2<<endl;  
                printf("%d\n",num2-num1);
                update(l,,c1);
            /*  cout<<" update check "<<endl;
                for(int i=1;i<=cnt;i++){
                    cout<<" i = "<<i<<" cnt= "<<c1[i]<<endl;  
                }*/
                update(r,,c2);
            }
            else{
                l=opt[a[i].l];int j=l;
            //  cout<<" (((( l= "<<l<<endl;
            //  cout<<" ======  "<<a[l].l<<" a[r].r = "<<a[l].r<<endl;
            //  system("pause");
                l=lower_bound(b,b+cnt,a[j].l)-b+;
                r=lower_bound(b,b+cnt,a[j].r)-b+;
                //system("pause");
                update(l,-,c1);
                update(r,-,c2);
            }
        }
    }
}