| 记录编号 |
459746 |
评测结果 |
AAAAWWWWWWW |
| 题目名称 |
快速红包变换 |
最终得分 |
36 |
| 用户昵称 |
 rewine |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
1.497 s |
| 提交时间 |
2017-10-13 18:51:54 |
内存使用 |
23.39 MiB |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
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;}
#define MAXX 110000
#define lh(o) (o<<1)
#define rh(o) (o<<1|1)
#define lch l,mid,o<<1
#define rch mid+1,r,o<<1|1
const int inf = ~0u>>2;
int n,m,x,y,z;
char q[10];
struct Pii {int v,n;};
struct Node {
int sum,ladd,lset,lazymi,sema,lazyma,semi;
Pii minn,maxx;
} a[MAXX*5];
void reset(int o,int len,int v) {
a[o].ladd = 0;
a[o].sum = v * len;
a[o].lazymi = -1;
a[o].lazyma = inf;
// a[o].sema = -1;
//cerr<<a[o].sema<<"\n";
a[o].minn.v = a[o].maxx.v = v;
a[o].minn.n = a[o].maxx.n = len;
a[o].lset = v;
}
void Add(int o,int len,int v) {
if(a[o].lazymi != -1) a[o].lazymi += v;
if(a[o].lazyma != inf) a[o].lazyma += v;
a[o].sema += v;
a[o].semi += v;
a[o].sum += v * len;
a[o].minn.v += v;
a[o].maxx.v += v;
a[o].ladd += v;
}
void Push_mi(int o,int len,int z) {
a[o].sum -= a[o].maxx.n*(a[o].maxx.v-z);
a[o].maxx.v = z;
a[o].lazymi = z;
/*if (z a[o].minn.v) {
cerr<<"!!!!!!!!!!!!!!!!";
a[o].minn.v = z;
a[o].minn.n = len;
}*/
if(a[o].lset > z) reset(o,len,z);
// if(a[o].)
}
void Push_ma(int o,int len,int z) {
a[o].sum += a[o].minn.n*(z-a[o].minn.v);
a[o].minn.v = z;
a[o].lazyma = z;
/*if (z a[o].minn.v) {
cerr<<"!!!!!!!!!!!!!!!!";
a[o].minn.v = z;
a[o].minn.n = len;
}*/
if(a[o].lset < z) reset(o,len,z);
// if(a[o].)
}
Pii megma(Pii a,Pii b,int o = 0) {
if(a.v > b.v) {if(o) ::a[o].sema = max(::a[lh(o)].sema,::a[rh(o)].maxx.v); return a;}
if(a.v < b.v) {if(o) ::a[o].sema = max(::a[lh(o)].maxx.v,::a[rh(o)].sema); return b;}
if(o) ::a[o].sema = max(::a[lh(o)].sema,::a[rh(o)].sema);
return (Pii){a.v,a.n+b.n};
}
Pii megmi(Pii a,Pii b,int o = 0) {
if(a.v < b.v) {if(o) ::a[o].semi = min(::a[lh(o)].semi,::a[rh(o)].minn.v); return a;}
if(a.v > b.v) {if(o) ::a[o].semi = min(::a[lh(o)].minn.v,::a[rh(o)].semi); return b;}
if(o) ::a[o].semi = min(::a[lh(o)].semi,::a[rh(o)].semi);
return (Pii){a.v,a.n+b.n};
}
void up(int o) {
a[o].sum = a[lh(o)].sum + a[rh(o)].sum;
a[o].minn = megmi(a[lh(o)].minn,a[rh(o)].minn,o);
a[o].maxx = megma(a[lh(o)].maxx,a[rh(o)].maxx,o);
}
void down(int o,int len) {
if(a[o].lset != -1) {
reset(lh(o),len-len/2,a[o].lset);
reset(rh(o),len/2,a[o].lset);
a[o].lset = -1;
}
if(a[o].ladd) {
Add(lh(o),len-len/2,a[o].ladd);
Add(rh(o),len/2,a[o].ladd);
a[o].ladd = 0;
}
if(a[o].lazymi != -1) {
for (int i = 0; i <= 1; i++) {
int t = o<<1|i;
if(a[t].maxx.v > a[o].lazymi)
Push_mi(t,i?len/2:len-len/2,a[o].lazymi);
}
a[o].lazymi = -1;
}
// int ma = a[o].maxx.n;
// up(o);
if(a[o].lazyma != inf) {
for (int i = 0; i <= 1; i++) {
int t = o<<1|i;
if(a[t].minn.v < a[o].lazyma)
Push_ma(t,i?len/2:len-len/2,a[o].lazyma);
}
a[o].lazyma = inf;
}
up(o);
// if(a[o].maxx.n != ma) {
// cerr<<a[lh(o)].maxx.n<<" "<<a[rh(o)].maxx.n<<" "<<ma<<" "<<a[o].maxx.n<<"\n";
// }
}
Pii Qmax(int l,int r,int o) {
if(x <= l && r <= y) return a[o].maxx;
down(o,r-l+1);
int mid = l+r>>1;
Pii tmp = (Pii){0,0};
if(x <= mid) tmp = Qmax(lch);
if(y > mid) tmp = megma(tmp,Qmax(rch));
return tmp;
}
Pii Qmin(int l,int r,int o) {
if(x <= l && r <= y) return a[o].minn;
down(o,r-l+1);
int mid = (l+r)>>1;
Pii tmp = (Pii){inf,0};
if(x <= mid) tmp = Qmin(lch);
if(y > mid) tmp = megmi(tmp,Qmin(rch));
return tmp;
}
int Qsum(int l,int r,int o) {
if(x <= l && r <= y) return a[o].sum;
down(o,r-l+1);
int mid = l+r>>1, tmp = 0;
if(x <= mid) tmp = Qsum(lch);
if(y > mid) tmp += Qsum(rch);
return tmp;
}
void build(int l,int r,int o) {
a[o].lset = -1;
a[o].ladd = 0;
a[o].lazymi = -1;
a[o].lazyma = inf;
if(l == r) {
read(a[o].maxx.v);
a[o].minn.v = a[o].sum = a[o].maxx.v;
a[o].minn.n = a[o].maxx.n = 1;
a[o].sema = -1; a[o].semi = inf;
return;
}
int mid = l+r>>1;
build(lch);build(rch);
up(o);
}
void Cadd(int l,int r,int o) {
if(x <= l && r <= y) {
Add(o,r-l+1,z);
return;
}
down(o,r-l+1);
int mid = l+r>>1;
if(x <= mid) Cadd(lch);
if(y > mid) Cadd(rch);
up(o);
}
void Cchang(int l,int r,int o) {
if(x <= l && r <= y) {
reset(o,r-l+1,z);
return;
}
down(o,r-l+1);
int mid = l+r>>1;
if(x <= mid) Cchang(lch);
if(y > mid) Cchang(rch);
up(o);
}
void Cbmax(int l,int r,int o) {
if(l == r) {
a[o].sum = a[o].minn.v = a[o].maxx.v = max(a[o].sum,z);
return;
}
if(x <= l && r <= y) {
if(a[o].minn.v >= z) return;
if(a[o].maxx.v <= z) {
Cchang(l,r,o);
return;
}
if(a[o].semi > z) {
Push_ma(o,r-l+1,z);
return;
}
}
down(o,r-l+1);
int mid = l+r>>1;
if(x <= mid) Cbmax(lch);
if(y > mid) Cbmax(rch);
up(o);
}
void Cbmin(int l,int r,int o) {
if(l == r) {
a[o].sum = a[o].minn.v = a[o].maxx.v = min(a[o].maxx.v,z);
return;
}
if(x <= l && r <= y) {
if(a[o].maxx.v <= z) return;
if(a[o].minn.v >= z) {
Cchang(l,r,o);
return;
}
if(a[o].sema < z) {
// cerr<<z<<"\n";
Push_mi(o,r-l+1,z);
return;
}
}
down(o,r-l+1);
int mid = l+r>>1;
if(x <= mid) Cbmin(lch);
if(y > mid) Cbmin(rch);
up(o);
}
int tt;
int Query() { //tt++;
//if(tt==5092) cerr<<q;
if(q[1] == 's') return Qsum(1,n,1);
if(q[1] == 'w') return q[3]=='i'?Qmin(1,n,1).v:Qmax(1,n,1).v;
return q[3]=='i'?Qmin(1,n,1).n:Qmax(1,n,1).n;
}
int main() {
freopen("redbag.in","r",stdin);freopen("redbag.out","w",stdout);
read(n); build(1,n,1); read(m);
for (int i = 1; i <= m; i++) {
scanf("%s",q);read(x);read(y);
if(q[0] == 'C') {
read(z);
if(q[1] == 'a') Cadd(1,n,1);
else if(q[1] == 'c') Cchang(1,n,1);
else if(q[3] == 'a') Cbmax(1,n,1);
else Cbmin(1,n,1);
} else printf("%d\n",Query());
}
return 0;
}