萌新刚学Leafy， WA了三个点， 都是在第一个就输出了0

Juan_feng @ 2019-02-21 17:34:37

by Juan_feng @ 2019-02-21 17:34:53

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#define mp make_pair
#define POI pair<int,int>
#define maxn 2000010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, z;
int cnt,root;
int a[maxn], b[maxn], siz[maxn], val[maxn], fa[maxn], son[maxn][2], tag[maxn];
const double alp = 1.0-sqrt(2)/2, lim = (1.0-2*alp)/(1.0-alp), spl = alp/(1-alp);

int New() {
    ++cnt;
    return cnt;
}

void Clear(int x) {
    siz[x] = val[x] = fa[x] = son[x][0] = son[x][1] = 0;
}

void push_up(int x) { 
    if(son[x][0]) 
      siz[x] = siz[son[x][0]] + siz[son[x][1]];
}

void push_down(int x) { 
    if(son[x][0] && tag[x]) {
        tag[son[x][0]] ^= 1;
        tag[son[x][1]] ^= 1;
        swap(son[x][0], son[x][1]);
        tag[x] = 0;
    }
}

int build(int l, int r) { 
    int now = ++cnt;
    if(l == r) {
        siz[now] = 1;
        val[now] = l;
        return now;
    }
    int mid = (l+r) >> 1;
    son[now][0] = build(l, mid);
    son[now][1] = build(mid+1, r);
    push_up(now);
    return now;
}

int merge(int u, int v) {
    if(!u || !v)  return u+v;
    push_down(u), push_down(v);
    if(siz[u] >= siz[v] && siz[v] >= siz[u]*spl || siz[v] >= siz[u] && siz[u] >= siz[v]*spl) {
        int cur = New();
        son[cur][0] = u;
        son[cur][1] = v;
        push_up(cur);
        return cur;
    }
    if(siz[u] > siz[v]) {
        push_down(u);
        int ls = son[u][0], rs = son[u][1];
        Clear(u);
        if(siz[ls] >= (siz[ls]+siz[rs]+siz[v])*alp)  
          return merge(ls, merge(rs, v));
        push_down(rs);
        int lrs = son[rs][0], rrs = son[rs][1];
        Clear(rs);
        return merge(merge(ls, lrs), merge(rrs, v));
    }
    else {
        push_down(v);
        int ls = son[v][0], rs = son[v][1];
        Clear(v);
        if(siz[rs] >= (siz[ls]+siz[rs]+siz[u])*alp)
          return merge(merge(u, ls), rs);
        push_down(ls);
        int lls = son[ls][0], rls = son[ls][1];
        Clear(ls);
        return merge(merge(u, lls), merge(rls, rs));
    }
}

POI split(int now, int x) {
    if(!x)  return mp(0, now);
    if(!son[now][0])  return mp(now, 0);
    push_down(now);
    POI y; int ls = son[now][0], rs = son[now][1];
    Clear(now); 
    if(siz[ls] >= x) {
        y = split(ls, x);
        return mp(y.first, merge(y.second, rs));
    }
    else {
        y = split(rs, x-siz[ls]);
        return mp(merge(ls, y.first), y.second);
    }
}

void change(int l, int r) {
    POI y, z;
    y = split(root, l-1);
    z = split(y.second, r-l+1);
    tag[z.first] ^= 1;
    root = merge(y.first, merge(z.first, z.second));
}

void print(int now) {
    push_down(now);
    if(son[now][0]) 
      print(son[now][0]), print(son[now][1]);
    else 
      printf("%d ", val[now]);
}

int main() {
    scanf("%d%d", &n, &m);
    root = build(1, n);
    FOR(i, 1, m) {
        scanf("%d%d", &x, &y);
        change(x, y);
    }
    print(root);
}

by Juan_feng @ 2019-02-21 17:36:19

求助dalao呀>_<

by t162 @ 2019-02-21 17:36:23

去你的萌新

by shadowice1984 @ 2019-02-21 17:45:22

去你的萌新

by tiger0132 @ 2019-02-21 17:47:12

去你的萌新

by Juan_feng @ 2019-02-21 17:49:57

各位神仙帮忙看看呗， 调了一下午了QAQAQ

by Ebola @ 2019-02-21 18:13:57

去你的萌新

by RiverFun @ 2019-02-21 18:21:53

去你的萌新

by Juan_feng @ 2019-02-21 21:04:35

一群fAKe的dalaoQAQ， 小蒟蒻瑟瑟发抖QAQAQ

不过问题已经解决了， 没有手写内存池导致GG了