HDU-4973(線分ツリー+二分)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int maxn = 51000;
int a[maxn];
long long Pow(int x,int y){ return a[y]; }
LL POW(int x,int y){LL ans=1; for(int i=1;i<=y;i++) ans*=x; return ans;}

LL MAX[maxn<<2],col[maxn<<2],sum[maxn<<2];
void pushup(int rt){
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int l,int r,int rt){
col[rt]=0;
if(l==r){
     MAX[rt]=sum[rt]=1;
     return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}

void pushdown(int rt){
if(col[rt]){
      col[rt<<1]+=col[rt];
      col[rt<<1|1]+=col[rt];
      sum[rt<<1]=Pow(2,col[rt])*sum[rt<<1];
      sum[rt<<1|1]=Pow(2,col[rt])*sum[rt<<1|1];
      MAX[rt<<1]=Pow(2,col[rt])*MAX[rt<<1];
      MAX[rt<<1|1]=Pow(2,col[rt])*MAX[rt<<1|1];
      col[rt]=0;
}
}

void update_point(int l,int r,int rt,int posi,int addv){
if(l==r){
      sum[rt]+=addv;
      MAX[rt]+=addv;
      return ;
}
pushdown(rt);
int m=(l+r)>>1;
if(posi<=m) update_point(lson,posi,addv);
else        update_point(rson,posi,addv);
pushup(rt);
}
void update(int l,int r,int rt,int mul,int ql,int qr){
if(ql<=l&&r<=qr){
      sum[rt]*=2;
      MAX[rt]*=2;
      col[rt]+=mul;
      return ;
}
pushdown(rt);
int m=(l+r)>>1;
if(ql<=m) update(lson,mul,ql,qr);
if(qr> m) update(rson,mul,ql,qr);
pushup(rt);
}
LL query_sum(int l,int r,int rt,int ql,int qr){
if(ql<=l&&r<=qr){
        return sum[rt];
}
pushdown(rt);
int m=(l+r)>>1;
LL res=0;
if(ql<=m) res+=query_sum(lson,ql,qr);
if(qr> m) res+=query_sum(rson,ql,qr);
return res;
}
LL query_max(int l,int r,int rt,int ql,int qr){
if(ql<=l&&r<=qr){
        return MAX[rt];
}
pushdown(rt);
int m=(l+r)>>1;
LL res=0;
if(ql<=m) res=max(res,query_max(lson,ql,qr));
if(qr> m) res=max(res,query_max(rson,ql,qr));
return res;
}
int n;
int find(LL goal){
int x=1,y=n;
while(x<y){
      int m=x+(y-x)/2;
      if(query_sum(1,n,1,1,m)>=goal) y=m;
      else x=m+1;
}
return x;
}
int main()
{
    for(int i=1;i<=60;i++) a[i]=POW(2,i);
    int Q;
    int T;
    int kase=1;
    scanf("%d",&T);
    while(T--){
          scanf("%d %d",&n,&Q);
          printf("Case #%d:
",kase++);
          build(1,n,1);
          while(Q--){
              char cmd[10];
              LL x,y;
              scanf("%s %I64d %I64d",cmd,&x,&y);
              int posix = find(x),posiy = find(y);
              if(cmd[0] == 'D'){
                     if(posix == posiy){
                            update_point(1,n,1,posix,y-x+1);
                     }
                     else{
                         LL limx = query_sum(1,n,1,1,posix);
                         LL limy = posiy==1 ? 0 : query_sum(1,n,1,1,posiy-1);
                         if(limx-x+1) update_point(1,n,1,posix,limx-x+1);
                         if(y-limy)   update_point(1,n,1,posiy,y-limy);

                         if(posix+1<=posiy-1){
                            int mul=1;
                            update(1,n,1,mul,posix+1,posiy-1);
                         }
                     }
              }
              else {
                   if(posix == posiy){
                            printf("%I64d
",y-x+1);
                     }
                     else{
                         LL max_=0;
                         LL limx = query_sum(1,n,1,1,posix);
                         max_=max(max_,limx-x+1);
                         LL limy = posiy==1 ? 0 : query_sum(1,n,1,1,posiy-1);
                         max_=max(max_,y-limy);
                         if(posix+1<=posiy-1){
                            max_=max(max_,query_max(1,n,1,posix+1,posiy-1));
                         }
                         printf("%I64d
",max_);
                     }
              }
          }
    }
    return 0;
}