在本地过了,在洛谷上却是0分

P3391 【模板】文艺平衡树

lightmain @ 2020-05-25 23:38:39

文艺平衡树模板题,改了几个小时,在本地过了,在洛谷上却是0分;我以前的AC代码能过

求助

#include <cstdio>
#include <algorithm>
#include <cstring>
#define pr printf
#define F(i, j, k) for(register int i = j, kkllkl = k; i <= kkllkl; ++i)
#define G(i, j, k) for(register int i = j, kkllkl = k; i >= kkllkl; --i)
#define clr(a, v) memset((a), v, sizeof(a))
using namespace std;
typedef long long ll;

#define isd(x) (('0' <= (x) && (x) <= '9') || (x) == '-')
int rd() {
    int ans = 0, sign = 1; char c = getchar();
    while(!isd(c)) c = getchar();
    if(c == '-') sign = -1, c = getchar();
    while(isd(c)) ans = (ans << 3) + (ans << 1) + c - '0', c = getchar();
    return sign == 1 ? ans : -ans;
}

/* --------------------------CSYZ1921------------------------- */

const int N = 100005, INF = 0x3f3f3f3f;
int n, m;
struct Splay {
    #define ls (ch[u][0])
    #define rs (ch[u][1])
    int fa[N], ch[N][2], val[N], cnt[N], sz[N], tot, root;
    bool mrk[N];
    void build() {
        tot = 0;
    }
    #define isw(x) ((x) == ch[fa[x]][1])

    void resz(int u) {
        sz[u] = cnt[u];
        if(ls) sz[u] += sz[ls];
        if(rs) sz[u] += sz[rs];
    }

    void pd(int u) {
        if(mrk[u]) {
            mrk[u] = false;
            swap(ls, rs);
            if(ls) mrk[ls] ^= true;
            if(rs) mrk[rs] ^= true;
        }
    }

    void rotate(int u) {
        int f = fa[u], g = fa[f];
        int fs = isw(f), us = isw(u), ch2 = ch[u][us ^ 1];
        fa[f] = u;  ch[u][us ^ 1] = f;
        ch[f][us] = ch2; if(ch2) fa[ch2] = f;
        if(g) ch[g][fs] = u; fa[u] = g;
        resz(f); resz(u);
    }

    void splay(int u, int t = 0) {
        for(int v; (v = fa[u]) != t && (v = fa[u]); rotate(u))
            if(fa[v] && fa[v] != t)
                rotate(sz[u] == sz[v] ? v : u);
        if(t == 0) root = u;
    }

    void create(int u, int f, int x) {
        if(f) ch[f][x > val[f]] = u, fa[u] = f;
        else root = u;
        cnt[u] = sz[u] = 1;
        val[u] = x;
    }

    void insert(int x) {
        if(root == 0) {
            create(++tot, root, x);
            return ;
        }
        int u = root;
        while(1) {  
            ++sz[u];
            int v = ch[u][x > val[u]];
            if(!v) {
                create(++tot, u, x);
                splay(tot);
                return ;
            } else u = v;
        }
    }

    int kth(int k) {
        int u = root;
        while(u) {
            pd(u);
            int lsz = ls ? sz[ls] : 0;
            int l = lsz + 1;
            if(k < l) {
                u = ls;
            } else if(l == k) {
                return u;
            } else {
                u = rs;
                k -= l;
            }
        }
    }

    int Swap(int l, int r) {
        int L = kth(l);
        int R = kth(r + 2);
        splay(L); splay(R, L);
        mrk[ch[R][0]] ^= true;
    }

    void dfs(int u) {
        pd(u);
        if(ls) dfs(ls);
        if(1 <= val[u] && val[u] <= n) pr("%d ", val[u]);
        if(rs) dfs(rs);
    }
} sp;

int main() {
    // freopen("P3391_1.in", "r", stdin);
    // freopen("P3391_1_2.out", "w", stdout);
    n = rd(); m = rd();
    sp.insert(-INF);
    sp.insert(INF);
    F(i, 1, n)
        sp.insert(i);
    F(i, 1, m) {
        int l = rd(), r = rd();
        if(l < r) sp.Swap(l, r);
    }
    sp.dfs(sp.root);
    return 0;
}

/*

5 3
1 3
1 3
1 4

*/

by zhanghengrui @ 2020-05-26 11:38:58

@lightmain 我让你把 Swap 函数的返回值类型改成 void ……

亲测能过


by lightmain @ 2020-05-26 11:40:16

@zhanghengrui 感谢


by lightmain @ 2020-05-26 11:42:28

@zhanghengrui @zhanghengrui 但是这是为什么呢。。?这是Linux的特点吗,没有写return的int返回值函数会导致RE和WA?


by zhanghengrui @ 2020-05-26 11:44:25

@lightmain

https://zh.cppreference.com/w/cpp/language/return

控制流出有返回值的函数(除了 main)的结尾而不经过 return 语句是未定义行为。

未定义行为,换句话说就是编译器想干什么都行,和平台无关


上一页 |