| 记录编号 |
425148 |
评测结果 |
AAAAAAAAAAT |
| 题目名称 |
快速红包变换 |
最终得分 |
90 |
| 用户昵称 |
 MloVtry |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
2.333 s |
| 提交时间 |
2017-07-14 18:43:14 |
内存使用 |
11.38 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#define inf 1<<30
using namespace std;
int the_a[100010];
int n,m;
struct node
{
int sum,lazy,covy;
int maxn,minn;
int maxnum,minnum;
}tree[4*100010];
void down(int i,int l,int r)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(tree[i].covy!=-1)
{
tree[lson].covy=tree[i].covy;
tree[lson].lazy=0;
tree[lson].sum=(mid-l+1)*tree[i].covy;
tree[lson].maxn=tree[lson].minn=tree[i].covy;
tree[lson].maxnum=tree[lson].minnum=(mid-l+1);
mid++;
tree[rson].covy=tree[i].covy;
tree[rson].lazy=0;
tree[rson].sum=(r-mid+1)*tree[i].covy;
tree[rson].maxn=tree[rson].minn=tree[i].covy;
tree[rson].maxnum=tree[rson].minnum=(r-mid+1);
tree[i].covy=-1;
}
mid=(l+r)>>1;
if(tree[i].lazy!=0)
{
tree[lson].sum+=tree[i].lazy*(mid-l+1);
tree[lson].lazy+=tree[i].lazy;
tree[lson].minn+=tree[i].lazy;
tree[lson].maxn+=tree[i].lazy;
mid++;
tree[rson].sum+=tree[i].lazy*(r-mid+1);
tree[rson].lazy+=tree[i].lazy;
tree[rson].minn+=tree[i].lazy;
tree[rson].maxn+=tree[i].lazy;
tree[i].lazy=0;
}
}
void up(int i)
{
int lson=i<<1,rson=lson|1;
tree[i].sum=tree[lson].sum+tree[rson].sum;
if(tree[lson].maxn>tree[rson].maxn)
{
tree[i].maxn=tree[lson].maxn;
tree[i].maxnum=tree[lson].maxnum;
}
else
{
if(tree[lson].maxn<tree[rson].maxn)
{
tree[i].maxn=tree[rson].maxn;
tree[i].maxnum=tree[rson].maxnum;
}
else
{
tree[i].maxn=tree[lson].maxn;
tree[i].maxnum=tree[lson].maxnum+tree[rson].maxnum;
}
}
if(tree[lson].minn<tree[rson].minn)
{
tree[i].minn=tree[lson].minn;
tree[i].minnum=tree[lson].minnum;
}
else
{
if(tree[rson].minn<tree[lson].minn)
{
tree[i].minn=tree[rson].minn;
tree[i].minnum=tree[rson].minnum;
}
else
{
tree[i].minn=tree[lson].minn;
tree[i].minnum=tree[lson].minnum+tree[rson].minnum;
}
}
}
void buid(int now,int l,int r)
{
int lson=now<<1,rson=lson|1,mid=(l+r)>>1;
tree[now].lazy=0;
tree[now].covy=-1;
tree[now].maxnum=0;
tree[now].minnum=0;
tree[now].maxn=0;
tree[now].minn=0;
if(l==r)
{
tree[now].sum=the_a[l];
tree[now].maxn=the_a[l];
tree[now].minn=the_a[l];
tree[now].maxnum=1;
tree[now].minnum=1;
return;
}
buid(lson,l,mid);
mid++;
buid(rson,mid,r);
up(now);
}
void add(int i,int l,int r,int u,int v,int what)//Cadd
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return;
if(u<=l&&v>=r)
{
tree[i].sum+=(r-l+1)*what;
tree[i].minn+=what;
tree[i].maxn+=what;
tree[i].lazy+=what;
return;
}
down(i,l,r);
add(lson,l,mid,u,min(mid,v),what);
mid++;
add(rson,mid,r,max(u,mid),v,what);
up(i);
}
int ask(int i,int l,int r,int u,int v)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(l>v||r<u) return 0;
if(u<=l&&r<=v)
{
return tree[i].sum;
}
down(i,l,r);
int re=0;
re+=ask(lson,l,mid,u,min(v,mid));
mid++;
re+=ask(rson,mid,r,max(mid,u),v);
up(i);
return re;
}
void change(int i,int l,int r,int u,int v,int what)//Cchange
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(l>v||r<u) return ;
if(u<=l&&r<=v)
{
tree[i].lazy=0;
tree[i].covy=what;
tree[i].sum=(r-l+1)*what;
tree[i].minn=tree[i].maxn=what;
tree[i].maxnum=tree[i].minnum=(r-l+1);
return;
}
down(i,l,r);
change(lson,l,mid,u,min(v,mid),what);
mid++;
change(rson,mid,r,max(u,mid),v,what);
up(i);
}
int ask_max(int i,int l,int r,int u,int v)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return -1;
if(u<=l&&v>=r)
{
return tree[i].maxn;
}
int re=-1;
down(i,l,r);
re=max(re,ask_max(lson,l,mid,u,min(mid,v)));
mid++;
re=max(re,ask_max(rson,mid,r,max(u,mid),v));
up(i);
return re;
}
int ask_min(int i,int l,int r,int u,int v)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return inf;
if(u<=l&&v>=r)
{
return tree[i].minn;
}
int re=inf;
down(i,l,r);
re=min(re,ask_min(lson,l,mid,u,min(mid,v)));
mid++;
re=min(re,ask_min(rson,mid,r,max(u,mid),v));
up(i);
return re;
}
int ask_maxn(int i,int l,int r,int u,int v,int what)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return 0;
if(u<=l&&v>=r)
{
if(tree[i].maxn==what)
{
return tree[i].maxnum;
}
else return 0;
}
int re=0;
re+=ask_maxn(lson,l,mid,u,min(mid,v),what);
mid++;
re+=ask_maxn(rson,mid,r,max(u,mid),v,what);
return re;
}
int ask_minn(int i,int l,int r,int u,int v,int what)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return 0;
if(u<=l&&v>=r)
{
if(tree[i].minn==what)
{
return tree[i].minnum;
}
else return 0;
}
int re=0;
re+=ask_minn(lson,l,mid,u,min(mid,v),what);
mid++;
re+=ask_minn(rson,mid,r,max(u,mid),v,what);
return re;
}
void cbmax(int i,int l,int r,int u,int v,int what)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return;
if(u<=l&&v>=r)
{
if(tree[i].minn>=what) return;
if(tree[i].maxn<=what)
{
change(1,1,n,u,v,what);
return;
}
down(i,l,r);
cbmax(lson,l,mid,l,mid,what);
mid++;
cbmax(rson,mid,r,mid,r,what);
up(i);
return;
}
down(i,l,r);
cbmax(lson,l,mid,u,min(mid,v),what);
mid++;
cbmax(rson,mid,r,max(u,mid),v,what);
up(i);
}
void cbmin(int i,int l,int r,int u,int v,int what)
{
int lson=i<<1,rson=lson|1,mid=(l+r)>>1;
if(r<u||l>v) return;
if(u<=l&&v>=r)
{
if(tree[i].maxn<=what) return;
if(tree[i].minn>=what)
{
change(1,1,n,u,v,what);
return;
}
down(i,l,r);
cbmin(lson,l,mid,l,mid,what);
mid++;
cbmin(rson,mid,r,mid,r,what);
up(i);
return;
}
down(i,l,r);
cbmin(lson,l,mid,u,min(mid,v),what);
mid++;
cbmin(rson,mid,r,max(u,mid),v,what);
up(i);
}
int read() //读入优化
{
int out=0,flag=1;
char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57)
{
out=out*10+c-48;
c=getchar();
}
return out*flag;
}
int main()
{
freopen("redbag.in","r",stdin);
freopen("redbag.out","w",stdout);
n=read();
for(int i=1;i<=n;++i) the_a[i]=read();
buid(1,1,n);
m=read();
for(int i=1;i<=m;++i)
{
char cz[10];
int u,v,a;
scanf("%s",cz+1);
if(cz[1]=='C')
{
u=read();
v=read();
a=read();
if(cz[2]=='a')//Cadd
{
add(1,1,n,u,v,a);
}
if(cz[2]=='c')//Cchange
{
change(1,1,n,u,v,a);
}
if(cz[5]=='x'&&cz[2]=='b')
{
cbmax(1,1,n,u,v,a);
}
if(cz[5]=='n'&&cz[2]=='b')
{
cbmin(1,1,n,u,v,a);
}
}
if(cz[1]=='Q')
{
u=read();
v=read();
if(cz[2]=='s') printf("%d\n",ask(1,1,n,u,v));
if(cz[2]=='w')
{
if(cz[5]=='x') printf("%d\n",ask_max(1,1,n,u,v));
if(cz[5]=='n') printf("%d\n",ask_min(1,1,n,u,v));
}
if(cz[2]=='n')
{
if(cz[5]=='x')
{
int zz=ask_max(1,1,n,u,v);
printf("%d\n",ask_maxn(1,1,n,u,v,zz));
}
if(cz[5]=='n')
{
int zz=ask_min(1,1,n,u,v);
printf("%d\n",ask_minn(1,1,n,u,v,zz));
}
}
}
}
return 0;
}