对拍std通过的代码上去变成了RE

PBCWZCC @ 2019-08-18 19:23:02

// LuoguP3391 文艺RE树
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
template<class T>inline void read(T&X)
{
    X = 0;
    char symbol('\0'),ch(getchar());
    for(;ch<'0'||'9'<ch;(!(ch^'-'))?(symbol='\1'):(1),ch=getchar());
    for(;'0'<=ch&&ch<='9';X=(X<<3)+(X<<1)+(ch^48),ch=getchar());
    (symbol)?(X=-X):(1);
}

const int MAXN = 100003; 
int n, m; 
class SPLAYTREAY{
  public: 
    int rt; 
  private: 
    int fa[MAXN+3], ch[MAXN+3][2]; 
    int vals[MAXN+3], cnt[MAXN+3]; 
    int siz[MAXN+3]; 
    int is[MAXN+3]; 
    int tags[MAXN+3]; 
    int tot; 
    char islr(const int x)
    {
        return x == ch[fa[x]][1]; 
    }
    void pushup(const int x)
    {
        siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x]; 
    }
    void rotate(const int x)
    {
        int y = fa[x], z = fa[y]; 
        if(!y) return ; 
//      int b = islr(x), c = islr(y); 
//      char b = (islr(x) << 1) | islr(y);  
        char b = islr(x), c = islr(y); // 这种空间在这里没有必要节省 
//      int a = ch[x][(b ^ 2) >> 1]; 
        int a = ch[x][b ^ 1];  

        if(a) fa[a] = y; 
//      ch[y][(b & 2) >> 1] = a; 
        ch[y][b] = a; 
        fa[x] = z; 
//      if(z) ch[z][b & 1] = x; 
        if(z) ch[z][c] = x; 
        else rt = x; 
        fa[y] = x; 
//      ch[x][(b ^ 2) >> 1] = y; 
        ch[x][b ^ 1] = y; 

        pushup(y); 
        pushup(x); 
    }
    void pushdown(const int x)
    {
        if(tags[x])
        {
            tags[ch[x][0]] ^= 1; 
            tags[ch[x][1]] ^= 1; 
            swap(ch[x][0], ch[x][1]); 
            tags[x] = 0; 
        }
    }
    void update(const int x, const int aim)
    {
        if(fa[x] != aim) update(fa[x], aim); 
        pushdown(x); 
    }
    void splay(const int x, const int aim)
    {
        int y, z;       
//      update(x, aim); // 先别急着转，一转就大乱！ 
        y = fa[x]; 
        if(!y) return; 
        z = fa[y]; 
        for(; fa[x] != aim; y = fa[x], z = fa[y])
        {
            if(z != aim)
            {
                if(islr(x) != islr(y))
                {
                    rotate(x); 
                    rotate(x); 
                }
                else
                {
                    rotate(y); 
                    rotate(x); 
                }
            }
            else
            {
                rotate(x); 
            }
        }
    }
  public: 
    void build(int &p, const int pre, const int l, const int r) // 直接构造 
    {
//      if(!p)
//      {
//          p = ++tot; 
//          vals[p] = mid; 
//      }
//      p = ++tot; 
        int mid = (l + r) >> 1; 
        p = mid + 1; 
        is[p] = mid + 1; 
        vals[p] = mid; 
        fa[p] = pre; 
        cnt[p] = 1; 
//      tag[p] = 0; 
//      ++siz[p]; 
        if(l < mid) build(ch[p][0], p, l, mid-1); 
        if(mid < r) build(ch[p][1], p, mid+1, r); 
        pushup(p); 
    }

    int getKR(const int p, const int k)
    {
        pushdown(p); // 这个时候 
        if(siz[ch[p][0]] < k)
        {
            if(siz[ch[p][0]] + cnt[p] < k)
            {
                getKR(ch[p][1], k - siz[ch[p][0]] - cnt[p]); 
            }
            else
            {
                return p; 
            }
        }
        else
        {
            getKR(ch[p][0], k); 
        }
    }

    void split(const int l, const int r)
    {
        int x = getKR(rt, l - 1); 
        int y = getKR(rt, r + 1); 
        splay(x, 0); 
        splay(y, x); 
        tags[ch[y][0]] ^= 1; 
    }
    void conclude(const int p) 
    {
        if(tags[p]) pushdown(p); 
        if(ch[p][0])
        {
            conclude(ch[p][0]); 
        }
        if(0 < vals[p] && vals[p] <= n) printf("%d ", vals[p]); 
        if(ch[p][1])
        {
            conclude(ch[p][1]); 
        }
    }
}; 
SPLAYTREAY T; 
#ifdef WIN32
char fname[2][128]; 
FILE *fn; 
#endif
int main()
{
#ifdef WIN32
    fn = fopen("filename.txt", "r"); 
    fscanf(fn, "%s", &fname[0][0]); 
    fclose(fn); 
//  system(&fname[0][0]); 
    sprintf(&fname[1][0], "%s_7.out", &fname[0][0]); 
    freopen(&fname[0][0], "r", stdin); 
    freopen(&fname[1][0], "w", stdout); 
#endif
    read(n); 
    T.build(T.rt, 0, 0, n+1); 
    read(m); 
    int x, y; 
    for(; m--; )
    {
        read(x); 
        read(y); 
        T.split(x + 1, y + 1); // 因为前面多插了个 0 ！！ 
    }
    T.conclude(T.rt); 
    return 0; 
}

by PBCWZCC @ 2019-08-18 19:23:43

求助\mathfrak{QAQ}

by 小菜鸟 @ 2019-08-18 19:29:52

fhqtxdy

by swiftc @ 2019-08-18 19:43:42

@PBCWZCC

// LuoguP3391 文艺RE树
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
template<class T>inline void read(T&X)
{
    X = 0;
    char symbol('\0'),ch(getchar());
    for(;ch<'0'||'9'<ch;(!(ch^'-'))?(symbol='\1'):(1),ch=getchar());
    for(;'0'<=ch&&ch<='9';X=(X<<3)+(X<<1)+(ch^48),ch=getchar());
    (symbol)?(X=-X):(1);
}

const int MAXN = 100003;
int n, m;
class SPLAYTREAY{
public:
    int rt;
private:
    int fa[MAXN+3], ch[MAXN+3][2];
    int vals[MAXN+3], cnt[MAXN+3];
    int siz[MAXN+3];
    int is[MAXN+3];
    int tags[MAXN+3];
    int tot;
    char islr(const int x)
    {
        return x == ch[fa[x]][1];
    }
    void pushup(const int x)
    {
        siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
    }
    void rotate(const int x)
    {
        int y = fa[x], z = fa[y];
        if(!y) return ;
        //      int b = islr(x), c = islr(y);
        //      char b = (islr(x) << 1) | islr(y);
        char b = islr(x), c = islr(y); // 这种空间在这里没有必要节省
        //      int a = ch[x][(b ^ 2) >> 1];
        int a = ch[x][b ^ 1];

        if(a) fa[a] = y;
        //      ch[y][(b & 2) >> 1] = a;
        ch[y][b] = a;
        fa[x] = z;
        //      if(z) ch[z][b & 1] = x;
        if(z) ch[z][c] = x;
        else rt = x;
        fa[y] = x;
        //      ch[x][(b ^ 2) >> 1] = y;
        ch[x][b ^ 1] = y;

        pushup(y);
        pushup(x);
    }
    void pushdown(const int x)
    {
        if(tags[x])
        {
            tags[ch[x][0]] ^= 1;
            tags[ch[x][1]] ^= 1;
            swap(ch[x][0], ch[x][1]);
            tags[x] = 0;
        }
    }
    void update(const int x, const int aim)
    {
        if(fa[x] != aim) update(fa[x], aim);
        pushdown(x);
    }
    void splay(const int x, const int aim)
    {
        int y, z;
        //      update(x, aim); // 先别急着转，一转就大乱！
        y = fa[x];
        if(!y) return;
        z = fa[y];
        for(; fa[x] != aim; y = fa[x], z = fa[y])
        {
            if(z != aim)
            {
                if(islr(x) != islr(y))
                {
                    rotate(x);
                    rotate(x);
                }
                else
                {
                    rotate(y);
                    rotate(x);
                }
            }
            else
            {
                rotate(x);
            }
        }
    }
public:
    void build(int &p, const int pre, const int l, const int r) // 直接构造
    {
        //      if(!p)
        //      {
        //          p = ++tot;
        //          vals[p] = mid;
        //      }
        //      p = ++tot;
        int mid = (l + r) >> 1;
        p = mid + 1;
        is[p] = mid + 1;
        vals[p] = mid;
        fa[p] = pre;
        cnt[p] = 1;
        //      tag[p] = 0;
        //      ++siz[p];
        if(l < mid) build(ch[p][0], p, l, mid-1);
        if(mid < r) build(ch[p][1], p, mid+1, r);
        pushup(p);
    }

    int getKR(const int p, const int k)
    {
        pushdown(p); // 这个时候
        if(siz[ch[p][0]] < k)
        {
            if(siz[ch[p][0]] + cnt[p] < k)
            {
                return getKR(ch[p][1], k - siz[ch[p][0]] - cnt[p]);
            }
            else
            {
                return p;
            }
        }
        else
        {
            return getKR(ch[p][0], k);
        }
    }

    void split(const int l, const int r)
    {
        int x = getKR(rt, l - 1);
        int y = getKR(rt, r + 1);
        splay(x, 0);
        splay(y, x);
        tags[ch[y][0]] ^= 1;
    }
    void conclude(const int p)
    {
        if(tags[p]) pushdown(p);
        if(ch[p][0])
        {
            conclude(ch[p][0]);
        }
        if(0 < vals[p] && vals[p] <= n) printf("%d ", vals[p]);
        if(ch[p][1])
        {
            conclude(ch[p][1]);
        }
    }
};
SPLAYTREAY T;
#ifdef WIN32
char fname[2][128];
FILE *fn;
#endif
int main()
{
#ifdef WIN32
    fn = fopen("filename.txt", "r");
    fscanf(fn, "%s", &fname[0][0]);
    fclose(fn);
    //  system(&fname[0][0]);
    sprintf(&fname[1][0], "%s_7.out", &fname[0][0]);
    freopen(&fname[0][0], "r", stdin);
    freopen(&fname[1][0], "w", stdout);
#endif
    read(n);
    T.build(T.rt, 0, 0, n+1);
    read(m);
    int x, y;
    for(; m--; )
    {
        read(x);
        read(y);
        T.split(x + 1, y + 1); // 因为前面多插了个 0 ！！
    }
    T.conclude(T.rt);
    return 0;
}

您的getKR函数出了点小问题

by PBCWZCC @ 2019-08-18 20:20:21

@UIKIt 多谢！\mathfrak{OvO}

by PBCWZCC @ 2019-08-18 20:22:11

话说为啥改之前\mathrm{Luogu\ IDE}都能过。。。辛酸\mathfrak{RxR}