HDU - 4973(세그먼트 트리 + 2점)
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.