| 记录编号 |
425151 |
评测结果 |
AAAAAAAAAAW |
| 题目名称 |
2153.快速红包变换 |
最终得分 |
90 |
| 用户昵称 |
 Wei |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.857 s |
| 提交时间 |
2017-07-14 18:45:49 |
内存使用 |
13.02 MiB |
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#define MAXX 110010
#define R register
using namespace std;
const int inf = ~0u>>2;
int n,m,x,y,z;
char s[10];
struct pll{int v,n;};
struct shu{
int sum,ladd,lset;
pll minn,maxx;
}tree[MAXX*5];
/*
void read(int &x) {
char c;
bool flag = 0;
while((c=getchar())<'0'||c>'9') flag |= (c=='-');
x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
if(flag) x = -x;
}
*/
void read(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
void put(int x)
{
int num = 0; char c[15];
while(x) c[++num] = (x%10)+48, x /= 10;
while(num) putchar(c[num--]);
putchar('\n');
}
void rset(int o,int len,int v) {
tree[o].ladd=0;
tree[o].sum=v*len;
tree[o].minn.v=tree[o].maxx.v=v;
tree[o].minn.n=tree[o].maxx.n=len;
tree[o].lset=v;
}
void add(int o,int len,int v) {
tree[o].sum+=v*len;
tree[o].minn.v+=v;
tree[o].maxx.v+=v;
tree[o].ladd+=v;
}
pll big(pll a,pll b) {
if(a.v>b.v) return a;
if(a.v<b.v) return b;
return (pll){a.v,a.n+b.n};
}
pll small(pll a,pll b){
if(a.v<b.v) return a;
if(a.v>b.v) return b;
return (pll){a.v,a.n+b.n};
}
void push_up(int o) {
R int lc=o<<1,rc=o<<1|1;
tree[o].sum=tree[lc].sum+tree[rc].sum;
tree[o].minn=small(tree[lc].minn,tree[rc].minn);
tree[o].maxx=big(tree[lc].maxx,tree[rc].maxx);
}
void push_down(int o,int len) {
if(tree[o].lset!=-1) {
rset(o<<1,len-len/2,tree[o].lset);
rset(o<<1|1,len/2,tree[o].lset);
tree[o].lset=-1;
}
if(tree[o].ladd) {
add(o<<1,len-len/2,tree[o].ladd);
add(o<<1|1,len/2,tree[o].ladd);
tree[o].ladd=0;
}
}
pll Qmax(int l,int r,int o) {
if(x<=l&&r<=y) return tree[o].maxx;
push_down(o,r-l+1);
int mid=l+r>>1;
R pll ans=(pll){0,0};
if(x<=mid) ans=big(Qmax(l,mid,o<<1),ans);
if(y>mid) ans=big(ans,Qmax(mid+1,r,o<<1|1));
return ans;
}
pll Qmin(int l,int r,int o) {
if(x<=l&&r<=y) return tree[o].minn;
push_down(o,r-l+1);
R int mid=(l+r)>>1;
pll ans=(pll){inf,0};
if(x<=mid) ans=small(Qmin(l,mid,o<<1),ans);
if(y>mid) ans=small(ans,Qmin(mid+1,r,o<<1|1));
return ans;
}
int Qsum(int l,int r,int o) {
if(x<=l&& r<=y) return tree[o].sum;
push_down(o,r-l+1);
R int mid=l+r>>1,ans=0;
if(x<=mid) ans= Qsum(l,mid,o<<1);
if(y>mid) ans+= Qsum(mid+1,r,o<<1|1);
return ans;
}
void build(int l,int r,int o) {
tree[o].lset=-1; tree[o].ladd=0;
if(l==r) {
read(tree[o].sum);
//scanf("%d",&tree[o].sum);
tree[o].minn.v=tree[o].maxx.v=tree[o].sum;
tree[o].minn.n=tree[o].maxx.n=1;
// printf("%d %d %d %d %d\n",a[o].sum,a[o].ladd,a[o].lset,a[o].maxx.v,a[o].maxx.n);
// printf("tree[%d].sum=%d\n",o,a[o].sum);
return;
}
R int mid=l+r>>1;
build(l,mid,o<<1);build(mid+1,r,o<<1|1);
push_up(o);
}
void Cadd(int l,int r,int o) {
if(x<=l&&r<=y) {
add(o,r-l+1,z);
return;
}
push_down(o,r-l+1);
R int mid=l+r>>1;
if(x<=mid) Cadd(l,mid,o<<1);
if(y>mid) Cadd(mid+1,r,o<<1|1);
push_up(o);
}
void Cchange(int l,int r,int o) {
if(x<=l&&r<=y) {
rset(o,r-l+1,z);
// printf("this is change tree[%d].sum=%d z=%d\n",o,a[o].sum,z);
return;
}
push_down(o,r-l+1);
R int mid=l+r>>1;
if(x<=mid) Cchange(l,mid,o<<1);
if(y>mid) Cchange(mid+1,r,o<<1|1);
push_up(o);
}
void Cbmax(int l,int r,int o) {
if(l==r) {
tree[o].sum=tree[o].minn.v=tree[o].maxx.v=max(tree[o].sum,z);
return;
}
if(x<=l&&r<=y) {
if(tree[o].minn.v>=z) return;
if(tree[o].maxx.v<=z) {
Cchange(l,r,o);
return;
}
}
push_down(o,r-l+1);
R int mid=l+r>>1;
if(x<=mid) Cbmax(l,mid,o<<1);
if(y>mid) Cbmax(mid+1,r,o<<1|1);
push_up(o);
}
void Cbmin(int l,int r,int o) {
// printf("l=%d r=%d z=%d\n",l,r,z);
if(l==r) {
tree[o].sum=tree[o].minn.v=tree[o].maxx.v=min(tree[o].sum,z);
// printf("tree[%d].sum=%d z=%d\n",o,a[o].sum,z);
return;
}
//printf("tree[%d].sum=%d\n",o,tree[o].sum);
if(x<=l&&r<=y) {
if(tree[o].maxx.v<=z) return;
if(tree[o].minn.v>=z) {
// printf("change\n");
Cchange(l,r,o);
return;
}
}
push_down(o,r-l+1);
R int mid=l+r>>1;
if(x<=mid) Cbmin(l,mid,o<<1);
if(y>mid) Cbmin(mid+1,r,o<<1|1);
push_up(o);
}
int main() {
freopen("redbag.in","r",stdin);
freopen("redbag.out","w",stdout);
// scanf("%d",&n);
read(n);
build(1,n,1);
scanf("%d",&m);
for (int i=1;i<=m;i++) {
scanf("%s",s);
// scanf("%d%d",&x,&y);
read(x);read(y);
if(s[0]=='C') {
scanf("%d",&z);
if(s[1]=='a') Cadd(1,n,1);
else if(s[1]=='c') Cchange(1,n,1);
else if(s[3]=='a') Cbmax(1,n,1);
else Cbmin(1,n,1);
}
else {
if(s[1]=='s') printf("%d\n",Qsum(1,n,1));
else if(s[1]=='w') {
if(s[3]=='a') printf("%d\n",Qmax(1,n,1).v);
else printf("%d\n",Qmin(1,n,1).v);
}
else {
if(s[3]=='a') printf("%d\n",Qmax(1,n,1).n);
else printf("%d\n",Qmin(1,n,1).n);
}
}
}
return 0;
}
/*
10
7 4 4 0 8 1 1 9 3 3
10
Cbmin 2 10 3
Qsum 2 7
Cbmax 2 8 5
Cbmin 2 4 5
Qsum 9 10
Cadd 3 6 9
Cbmin 10 10 7
Qnmax 7 7
Qnmax 4 5
Cadd 4 9 2
*/