HDU - 4973(세그먼트 트리 + 2점)

4165 단어
#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; }

좋은 웹페이지 즐겨찾기