萌新刚学 Splay,求助!!!(内附小数据)
查看原帖
萌新刚学 Splay,求助!!!(内附小数据)
372999
Light_Knight楼主2022/3/25 16:13

目前看来应该是标记下放的问题,可能出在 modifymodify(修改)函数里面吧 qwqqwq,但是一直没有调出来,希望哪位大佬帮忙看看,非常感谢!

#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
2022/3/25 16:13
加载中...