| 记录编号 |
446022 |
评测结果 |
AAAAAAAAAAT |
| 题目名称 |
快速红包变换 |
最终得分 |
90 |
| 用户昵称 |
 swttc |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
1.901 s |
| 提交时间 |
2017-09-07 14:46:47 |
内存使用 |
11.38 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#define mid (l+r>>1)
#define ls (o<<1)
#define rs ((o<<1)+1)
using namespace std;
int n,m,av[100010],sum[400010],ad[400010],ch[400010];
struct treemax
{
int maxx,cmx;
bool operator < (const treemax & b) const{
return maxx<b.maxx;
}
bool operator > (const treemax & b) const{
return maxx>b.maxx;
}
bool operator != (const treemax & b) const{
return maxx!=b.maxx;
}
}tmx[400010];
struct treemin
{
int minn,cmn;
bool operator > (const treemin & b) const{
return minn>b.minn;
}
bool operator < (const treemin & b) const{
return minn<b.minn;
}
bool operator != (const treemin & b) const{
return minn!=b.minn;
}
}tmn[400010];
void buildt(int l,int r,int o)
{
if(l==r){
sum[o]=av[l];
tmx[o].maxx=av[l];
tmn[o].minn=av[l];
tmx[o].cmx=1;
tmn[o].cmn=1;
return;
}
buildt(l,mid,ls);
buildt(mid+1,r,rs);
if(tmx[ls]!=tmx[rs]) tmx[o]=max(tmx[ls],tmx[rs]);
else{
tmx[o]=tmx[ls];
tmx[o].cmx+=tmx[rs].cmx;
}
if(tmn[ls]!=tmn[rs]) tmn[o]=min(tmn[ls],tmn[rs]);
else{
tmn[o]=tmn[ls];
tmn[o].cmn+=tmn[rs].cmn;
}
sum[o]=sum[ls]+sum[rs];
return;
}
void pushdown(int l,int r,int o)
{
if(ch[o]+1){
tmx[ls].maxx=ch[o];
tmx[rs].maxx=ch[o];
tmn[ls].minn=ch[o];
tmn[rs].minn=ch[o];
sum[ls]=(mid-l+1)*ch[o];
sum[rs]=(r-mid)*ch[o];
tmx[ls].cmx=mid-l+1;
tmx[rs].cmx=r-mid;
tmn[ls].cmn=mid-l+1;
tmn[rs].cmn=r-mid;
ch[ls]=ch[o];
ch[rs]=ch[o];
ad[ls]=0;
ad[rs]=0;
ch[o]=-1;
}
if(ad[o]){
tmx[ls].maxx+=ad[o];
tmx[rs].maxx+=ad[o];
tmn[ls].minn+=ad[o];
tmn[rs].minn+=ad[o];
sum[ls]+=(mid-l+1)*ad[o];
sum[rs]+=(r-mid)*ad[o];
ad[ls]+=ad[o];
ad[rs]+=ad[o];
ad[o]=0;
}
return;
}
treemax qmx(int l,int r,int o,int ll,int rr)
{
treemax temp;
temp.maxx=-2*(1e9);
temp.cmx=0;
if(l>=ll&&r<=rr){
return tmx[o];
}
pushdown(l,r,o);
if(mid>=ll){
treemax tempp=qmx(l,mid,ls,ll,rr);
if(temp<tempp) temp=tempp;
else if(!(temp!=tempp)) temp.cmx+=tempp.cmx;
}
if(mid<rr){
treemax tempp=qmx(mid+1,r,rs,ll,rr);
if(temp<tempp) temp=tempp;
else if(!(temp!=tempp)) temp.cmx+=tempp.cmx;
}
return temp;
}
treemin qmn(int l,int r,int o,int ll,int rr)
{
treemin temp;
temp.minn=2*(1e9);
temp.cmn=0;
if(l>=ll&&r<=rr){
return tmn[o];
}
pushdown(l,r,o);
if(mid>=ll){
treemin tempp=qmn(l,mid,ls,ll,rr);
if(temp>tempp) temp=tempp;
else if(!(temp!=tempp)) temp.cmn+=tempp.cmn;
}
if(mid<rr){
treemin tempp=qmn(mid+1,r,rs,ll,rr);
if(temp>tempp) temp=tempp;
else if(!(temp!=tempp)) temp.cmn+=tempp.cmn;
}
return temp;
}
int qsm(int l,int r,int o,int ll,int rr)
{
int temp=0;
if(l>=ll&&r<=rr){
return sum[o];
}
pushdown(l,r,o);
if(mid>=ll) temp+=qsm(l,mid,ls,ll,rr);
if(mid<rr) temp+=qsm(mid+1,r,rs,ll,rr);
return temp;
}
void cbmax(int l,int r,int o,int ll,int rr,int x)
{
if(l>=ll&&r<=rr){
if(tmx[o].maxx<=x){
tmx[o].maxx=x;
tmn[o].minn=x;
tmx[o].cmx=r-l+1;
tmn[o].cmn=r-l+1;
sum[o]=(r-l+1)*x;
ch[o]=x;
ad[o]=0;
return;
}
if(tmn[o].minn>=x) return;
if(l==r) return;
}
pushdown(l,r,o);
if(mid>=ll) cbmax(l,mid,ls,ll,rr,x);
if(mid<rr) cbmax(mid+1,r,rs,ll,rr,x);
if(tmx[ls]!=tmx[rs]) tmx[o]=max(tmx[ls],tmx[rs]);
else{
tmx[o]=tmx[ls];
tmx[o].cmx+=tmx[rs].cmx;
}
if(tmn[ls]!=tmn[rs]) tmn[o]=min(tmn[ls],tmn[rs]);
else{
tmn[o]=tmn[ls];
tmn[o].cmn+=tmn[rs].cmn;
}
sum[o]=sum[ls]+sum[rs];
return;
}
void cbmin(int l,int r,int o,int ll,int rr,int x)
{
if(l>=ll&&r<=rr){
if(tmn[o].minn>=x){
tmx[o].maxx=x;
tmn[o].minn=x;
tmx[o].cmx=r-l+1;
tmn[o].cmn=r-l+1;
sum[o]=(r-l+1)*x;
ch[o]=x;
ad[o]=0;
return;
}
if(tmx[o].maxx<=x) return;
if(l==r) return;
}
pushdown(l,r,o);
if(mid>=ll) cbmin(l,mid,ls,ll,rr,x);
if(mid<rr) cbmin(mid+1,r,rs,ll,rr,x);
if(tmx[ls]!=tmx[rs]) tmx[o]=max(tmx[ls],tmx[rs]);
else{
tmx[o]=tmx[ls];
tmx[o].cmx+=tmx[rs].cmx;
}
if(tmn[ls]!=tmn[rs]) tmn[o]=min(tmn[ls],tmn[rs]);
else{
tmn[o]=tmn[ls];
tmn[o].cmn+=tmn[rs].cmn;
}
sum[o]=sum[ls]+sum[rs];
return;
}
void cchange(int l,int r,int o,int ll,int rr,int x)
{
if(l>=ll&&r<=rr){
tmx[o].maxx=x;
tmn[o].minn=x;
tmx[o].cmx=r-l+1;
tmn[o].cmn=r-l+1;
sum[o]=(r-l+1)*x;
ch[o]=x;
ad[o]=0;
return;
}
pushdown(l,r,o);
if(mid>=ll) cchange(l,mid,ls,ll,rr,x);
if(mid<rr) cchange(mid+1,r,rs,ll,rr,x);
if(tmx[ls]!=tmx[rs]) tmx[o]=max(tmx[ls],tmx[rs]);
else{
tmx[o]=tmx[ls];
tmx[o].cmx+=tmx[rs].cmx;
}
if(tmn[ls]!=tmn[rs]) tmn[o]=min(tmn[ls],tmn[rs]);
else{
tmn[o]=tmn[ls];
tmn[o].cmn+=tmn[rs].cmn;
}
sum[o]=sum[ls]+sum[rs];
return;
}
void cadd(int l,int r,int o,int ll,int rr,int x)
{
if(l>=ll&&r<=rr){
tmx[o].maxx+=x;
tmn[o].minn+=x;
sum[o]+=(r-l+1)*x;
ad[o]+=x;
return;
}
pushdown(l,r,o);
if(mid>=ll) cadd(l,mid,ls,ll,rr,x);
if(mid<rr) cadd(mid+1,r,rs,ll,rr,x);
if(tmx[ls]!=tmx[rs]) tmx[o]=max(tmx[ls],tmx[rs]);
else{
tmx[o]=tmx[ls];
tmx[o].cmx+=tmx[rs].cmx;
}
if(tmn[ls]!=tmn[rs]) tmn[o]=min(tmn[ls],tmn[rs]);
else{
tmn[o]=tmn[ls];
tmn[o].cmn+=tmn[rs].cmn;
}
sum[o]=sum[ls]+sum[rs];
return;
}
int main()
{
freopen("redbag.in","r",stdin);
freopen("redbag.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&av[i]);
memset(ch,-1,sizeof(ch));
buildt(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
char c[100];
scanf("%s",c);
if(c[0]=='C'){
int w,y,q;
scanf("%d%d%d",&w,&y,&q);
if(c[1]=='b'){
if(c[3]=='a') cbmax(1,n,1,w,y,q);
else cbmin(1,n,1,w,y,q);
}
else if(c[1]=='a') cadd(1,n,1,w,y,q);
else cchange(1,n,1,w,y,q);
}
else{
int y,q;
scanf("%d%d",&y,&q);
if(c[1]=='s') printf("%d\n",qsm(1,n,1,y,q));
else{
if(c[1]=='w'){
if(c[3]=='a'){
treemax temp=qmx(1,n,1,y,q);
printf("%d\n",temp.maxx);
}
else{
treemin temp=qmn(1,n,1,y,q);
printf("%d\n",temp.minn);
}
}
else{
if(c[3]=='a'){
treemax temp=qmx(1,n,1,y,q);
printf("%d\n",temp.cmx);
}
else{
treemin temp=qmn(1,n,1,y,q);
printf("%d\n",temp.cmn);
}
}
}
}
}
return 0;
}