目前看来应该是标记下放的问题,可能出在 modify(修改)函数里面吧 qwq,但是一直没有调出来,希望哪位大佬帮忙看看,非常感谢!
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+10, INF = 1e9;
int rt, tot, a[N];
int fa[N], ch[N][2], siz[N];
int val[N], sum[N], mxs[N], mxl[N], mxr[N];
bool tag[N], rev[N];
#define ls ch[x][0]
#define rs ch[x][1]
inline bool dir(int x) {return ch[fa[x]][1] == x;}
inline void connect(int x, int f, int d) {fa[x] = f; ch[f][d] = x;}
inline void pushup(int x){
siz[x] = siz[ls]+1+siz[rs];
sum[x] = sum[ls]+val[x]+sum[rs];
mxs[x] = max(mxr[ls]+val[x]+mxl[rs], max(mxs[ls], mxs[rs]));
mxl[x] = max(mxl[ls], sum[ls]+val[x]+mxl[rs]);
mxr[x] = max(mxr[rs], sum[rs]+val[x]+mxr[ls]);
}
inline void pushdown(int x){
if(tag[x]){
tag[x] = rev[x] = 0; sum[x] = val[x]*siz[x];
if(val[x] >= 0) mxs[x] = mxl[x] = mxr[x] = sum[x];
else mxs[x] = val[x], mxl[x] = mxr[x] = 0;
tag[ls] = tag[rs] = 1; val[ls] = val[rs] = val[x];
}
if(rev[x]){
rev[x] = 0; swap(ls, rs); swap(mxl[x], mxr[x]);
rev[ls] ^= 1; rev[rs] ^= 1;
}
}
inline void rotate(int x){
int f = fa[x]; bool dx = dir(x), df = dir(f);
connect(ch[x][dx^1], f, dx);
connect(x, fa[f], df);
connect(f, x, dx^1);
pushup(f); pushup(x);
}
inline void splay(int x, int g){
for(int f; (f = fa[x]) != g; rotate(x))
if(fa[f] != g) rotate(dir(x) == dir(f) ? f : x);
if(!g) rt = x;
}
inline int build(int l, int r, int f){
if(l > r) return 0; int mid = (l+r)>>1;
int x = ++tot; fa[x] = f; val[x] = a[mid]; siz[x] = 1;
tag[x] = 1; pushdown(x);
ls = build(l, mid-1, x); rs = build(mid+1, r, x);
pushup(x); return x;
}
inline int getkth(int k){
for(int x = rt; ; ){
pushdown(x);
if(k <= siz[ls]) x = ls;
else if(k <= siz[ls]+1) return x;
else k -= siz[ls]+1, x = rs;
}
}
inline int split(int l, int r){
int pre = getkth(l), nxt = getkth(r+2);
splay(pre, 0); splay(nxt, pre);
return nxt;
}
inline void insert(int k, int t){
for(int i = 1; i <= t; i++) scanf("%d", &a[i]);
int x = split(k+1, k);
ls = build(1, t, x); fa[ls] = x;
pushup(x); pushup(fa[x]);
}
inline void remove(int l, int r){
int x = split(l, r);
ls = 0;
pushup(x); pushup(fa[x]);
}
inline void modify(int l, int r, int v){
int x = split(l, r);
tag[ls] = 1; val[ls] = v; pushdown(ls);
pushup(x); pushup(fa[x]);
}
inline void revers(int l, int r){
int x = split(l, r);
rev[ls] ^= 1; pushdown(ls);
pushup(x); pushup(fa[x]);
}
inline void getsum(int l, int r){
int x = split(l, r);
printf("%d\n", sum[ls]);
pushup(x); pushup(fa[x]);
}
inline void output(int x){
pushdown(x);
if(ls) output(ls);
if(val[x] > -INF && val[x] < INF) printf("%d ", val[x]);
if(rs) output(rs);
}
int main(){
int n, m; scanf("%d%d", &n, &m);
mxs[0] = a[0] = a[n+1] = -INF;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
rt = build(0, n+1, 0); char o[10];
for(int i = 1, x, y, z; i <= m; i++){
scanf("%s", o);
switch(o[2]){
case 'S': scanf("%d%d", &x, &y); insert(x, y); break;
case 'L': scanf("%d%d", &x, &y); remove(x, x+y-1); break;
case 'K': scanf("%d%d%d", &x, &y, &z); modify(x, x+y-1, z); break;
case 'V': scanf("%d%d", &x, &y); revers(x, x+y-1); break;
case 'T': scanf("%d%d", &x, &y); getsum(x, x+y-1); break;
case 'X': printf("%d\n", mxs[rt]); break;
}
// output(rt); printf("\n");
}
return 0;
}
附上 WA 掉的小数据:
输入:
5 5
7 8 6 6 5
MAKE-SAME 1 5 0
MAX-SUM
MAKE-SAME 1 2 -3
GET-SUM 1 5
我的输出:
0
0
正确输出:
0
-6