| 记录编号 |
450463 |
评测结果 |
AAAAWWWWWWW |
| 题目名称 |
快速红包变换 |
最终得分 |
36 |
| 用户昵称 |
 Anonymity |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
1.536 s |
| 提交时间 |
2017-09-16 12:32:52 |
内存使用 |
21.29 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#define maxa 400005
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{ char c=getchar();int x=0,y=1;
while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
inline int m_max(int x,int y){return x>y?x:y;}
inline int m_min(int x,int y){return x<y?x:y;}
int sum[maxa],ma[maxa],mi[maxa],nsum[maxa],msum[maxa],cov[maxa],mase[maxa],mise[maxa],add[maxa],cmax[maxa],cmin[maxa],inf=0x7fffffff,n,m;
bool hc[maxa],hmax[maxa],hmin[maxa];
struct tree{int lc,rc;}tr[maxa];
inline void mt(int z)
{ int lch=z<<1,rch=lch|1;
sum[z]=sum[lch]+sum[rch];
if(ma[lch]>ma[rch]) msum[z]=msum[lch],ma[z]=ma[lch],mase[z]=m_max(mase[lch],ma[rch]);
else if(ma[lch]<ma[rch]) msum[z]=msum[rch],ma[z]=ma[rch],mase[z]=m_max(ma[lch],mase[rch]);
else msum[z]=msum[lch]+msum[rch],ma[z]=ma[lch],mase[z]=m_max(mase[lch],mase[rch]);
if(mi[lch]>mi[rch]) nsum[z]=nsum[rch],mi[z]=mi[rch],mise[z]=m_min(mi[lch],mise[rch]);
else if(mi[lch]<mi[rch]) nsum[z]=nsum[lch],mi[z]=mi[lch],mise[z]=m_min(mise[lch],mi[rch]);
else nsum[z]=nsum[lch]+nsum[rch],mi[z]=mi[lch],mise[z]=m_min(mise[lch],mise[rch]);
}
inline void change(int z,int o);
inline void sset(int z,int v){hc[z]=1;cov[z]=v;add[z]=0;ma[z]=mi[z]=v;sum[z]=(tr[z].rc-tr[z].lc+1)*v;msum[z]=tr[z].rc-tr[z].lc+1;nsum[z]=msum[z];}
inline void sadd(int z,int v){add[z]+=v;ma[z]+=v;mi[z]+=v;sum[z]+=(tr[z].rc-tr[z].lc+1)*v;}
inline void smax(int z,int v){if(!hmax[z]) cmax[z]=v,hmax[z]=1;else cmax[z]=m_max(cmax[z],v);change(z,1);}//1 max
inline void smin(int z,int v){if(!hmin[z]) cmin[z]=v,hmin[z]=1;else cmin[z]=m_min(cmin[z],v);change(z,0);}//0 min//hightlight
inline void dn(int z)
{ int lch=z<<1,rch=lch|1;
if(hc[z]){sset(lch,cov[z]);sset(rch,cov[z]);hc[z]=0;}
if(add[z]){sadd(lch,add[z]);sadd(rch,add[z]);add[z]=0;}
if(hmax[z]){smax(lch,cmax[z]);smax(rch,cmax[z]);hmax[z]=0;cmax[z]=-inf;}
if(hmin[z]){smin(lch,cmin[z]);smin(rch,cmin[z]);hmin[z]=0;cmin[z]=inf;}
}
inline void change(int z,int o)
{ //cout<<cmin[z]<<" "<<mase[z]<<" "<<tr[z].lc<<" "<<tr[z].rc<<endl;
if(o)
{ if(cmax[z]<=mi[z]){hmax[z]=0;return;}
if(cmax[z]>=mise[z]){if(tr[z].lc!=tr[z].rc) dn(z),mt(z);return;}
sum[z]+=(cmax[z]-mi[z])*nsum[z];mi[z]=cmax[z];
if(tr[z].lc==tr[z].rc) ma[z]=mi[z];
}
else
{ if(cmin[z]>=ma[z]){hmin[z]=0;return;}
if(cmin[z]<=mase[z]){if(tr[z].lc!=tr[z].rc) dn(z),mt(z);return;}
sum[z]-=(ma[z]-cmin[z])*msum[z];ma[z]=cmin[z];
if(tr[z].lc==tr[z].rc) mi[z]=ma[z];
}
}
void build(int x,int y,int z)
{ tr[z].lc=x;tr[z].rc=y;//mase[z]=-inf;mise[z]=inf;cmax[z]=-inf;cmin[z]=inf;
if(x==y){ma[z]=mi[z]=sum[z]=read();msum[z]=nsum[z]=1;mase[z]=-inf;mise[z]=inf;return;}
int mid=x+y>>1,lch=z<<1,rch=lch|1;
build(x,mid,lch);build(mid+1,y,rch);
mt(z);
}
inline void updata(int x,int y,int z,int v,int o)
{ if(tr[z].lc>=x&&tr[z].rc<=y){if(o) sset(z,v);else sadd(z,v);return;}
dn(z);
int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;
if(x<=mid) updata(x,y,lch,v,o);
if(mid<y) updata(x,y,rch,v,o);
mt(z);
}
inline void updata2(int x,int y,int z,int v,int o)
{ if(tr[z].lc>=x&&tr[z].rc<=y)
{ //cout<<"this->"<<tr[z].lc<<" "<<tr[z].rc<<" "<<o<<endl;
if(o){smax(z,v);return;}
else{smin(z,v);return;}
}
dn(z);
int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;
if(x<=mid) updata2(x,y,lch,v,o);
if(mid<y) updata2(x,y,rch,v,o);
mt(z);
}
inline int querysum(int x,int y,int z)
{ if(tr[z].lc>=x&&tr[z].rc<=y) return sum[z];
dn(z);
int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1,tmp=0;
if(x<=mid) tmp+=querysum(x,y,lch);
if(mid<y) tmp+=querysum(x,y,rch);
return tmp;
}
inline int query1(int x,int y,int z,int o)
{ if(tr[z].lc>=x&&tr[z].rc<=y){if(o) return ma[z];else return mi[z];}
dn(z);
int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1,tmp;
if(o) tmp=-inf;else tmp=inf;
if(o)
{ if(x<=mid) tmp=max(tmp,query1(x,y,lch,o));
if(mid<y) tmp=max(tmp,query1(x,y,rch,o));
}
else
{ if(x<=mid) tmp=min(tmp,query1(x,y,lch,o));
if(mid<y) tmp=min(tmp,query1(x,y,rch,o));
}
return tmp;
}
inline int query2(int x,int y,int z,int o)
{ if(!z) return 0;
if(tr[z].lc==x&&tr[z].rc==y)
{ //cout<<"this->"<<tr[z].lc<<" "<<tr[z].rc<<endl;
//cout<<"this->"<<nsum[z]<<endl;
if(o) return msum[z];
else return nsum[z];
}
dn(z);
int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;
if(y<=mid) return query2(x,y,lch,o);
else if(x>mid) return query2(x,y,rch,o);
else
{ int t1=query1(x,mid,lch,o),t2=query1(mid+1,y,rch,o);
if(o)
{ if(t1>t2) return query2(x,mid,lch,o);
else if(t1<t2) return query2(mid+1,y,rch,o);
else return query2(x,mid,lch,o)+query2(mid+1,y,rch,o);
}
else
{ if(t1<t2) return query2(x,mid,lch,o);
else if(t1>t2) return query2(mid+1,y,rch,o);
else return query2(x,mid,lch,o)+query2(mid+1,y,rch,o);
}
}
}
int main()
{ freopen("redbag.in","r",stdin);
freopen("redbag.out","w",stdout);
n=read();
build(1,n,1);
char ord[15];int x,y,z;
m=read();
for(int i=1;i<=m;++i)
{ scanf("%s",ord);x=read();y=read();
if(ord[0]=='C')
{ z=read();
if(ord[3]=='d') updata(x,y,1,z,0);
if(ord[3]=='a'&&ord[2]=='h') updata(x,y,1,z,1);
if(ord[3]=='a'&&ord[2]=='m') updata2(x,y,1,z,1);
if(ord[3]=='i'&&ord[2]=='m') updata2(x,y,1,z,0);
}
else
{ if(ord[1]=='s') printf("%d\n",querysum(x,y,1));
if(ord[1]=='w'&&ord[3]=='a') printf("%d\n",query1(x,y,1,1));
if(ord[1]=='w'&&ord[3]=='i') printf("%d\n",query1(x,y,1,0));
if(ord[1]=='n'&&ord[3]=='a') printf("%d\n",query2(x,y,1,1));
if(ord[1]=='n'&&ord[3]=='i') printf("%d\n",query2(x,y,1,0));
}
}
return 0;
}