请各位大佬帮我看看这两份代码有什么区别？？？

zhy12138 @ 2018-08-18 19:07:40

by zhy12138 @ 2018-08-18 19:08:08

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
inline int read()
{
    int kkk=0,x=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            x=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
        kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
    return kkk*x;
}
struct sb
{
    int son[2],fa,value,size,mark,cnt;
}tree[100001];
int n,m,root,tot;
inline int up(int bj)
{
    tree[bj].size=tree[tree[bj].son[0]].size+tree[tree[bj].son[1]].size+tree[bj].cnt;
}
inline int down(int bj)
{
    if(tree[bj].mark)
    {
        tree[tree[bj].son[0]].mark^=1;
        tree[tree[bj].son[1]].mark^=1;
        tree[bj].mark=0;
        swap(tree[bj].son[0],tree[bj].son[1]);
    }
}
inline int rotate(int x)
{
    int y=tree[x].fa;
    int z=tree[y].fa;
    int check=(tree[y].son[1]==x);
    tree[z].son[tree[z].son[1]==y]=x;
    tree[x].fa=z;
    tree[y].son[check]=tree[x].son[check^1];
    tree[tree[x].son[check^1]].fa=y;
    tree[x].son[check^1]=y;
    tree[y].fa=x;
    up(y),up(x);
}
inline int splay(int x,int goal)
{
    while(tree[x].fa!=goal)
    {
        int y=tree[x].fa;
        int z=tree[y].fa;
        if(z!=goal)
            (tree[z].son[0]==y)^(tree[y].son[0]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0)
        root=x;
}
inline int insert(int x)
{
    int u=root,ff=0;
    while(u!=0 && tree[u].value!=x)
    {
        ff=u;
        u=tree[u].son[x>tree[u].value];
    }
    if(u!=0)
        ++tree[u].cnt;
    else
    {
        u=++tot;
        if(ff!=0)
            tree[ff].son[x>tree[ff].value]=u;
        tree[u].value=x;
        tree[u].son[0]=tree[u].son[1]=0;
        tree[u].size=1;
        tree[u].cnt=1;
        tree[u].fa=ff;
        tree[u].mark=0;
    }
    splay(u,0);
}
inline int kth(int x)
{
    int u=root;
    if(tree[u].size<x)
        return 0;
    while(1)
    {
        down(u);
        int y=tree[u].son[0];
        if(tree[y].size+1<x)
            x-=(tree[y].size+1),u=tree[u].son[1];
        else
            if(tree[y].size>=x)
                u=tree[u].son[0];
            else
                return tree[u].value;
    }
}
int out(int bj)
{
    down(bj);
    if(tree[bj].son[0])
        out(tree[bj].son[0]);
    if(tree[bj].value>=2 && tree[bj].value<=n+1)
        printf("%d ",tree[bj].value-1);
    if(tree[bj].son[1])
        out(tree[bj].son[1]);
}
inline int work(int l,int r)
{
    l=kth(l),r=kth(r+2);
    splay(l,0),splay(r,l);
    tree[tree[tree[root].son[1]].son[0]].mark^=1;
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n+2;++i)
        insert(i);
    for(register int i=1;i<=m;++i)
    {
        int l=read(),r=read();
        work(l,r);
    }
    out(root);
    return 0;
}

这是AC的代码

by zhy12138 @ 2018-08-18 19:09:07

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
inline int read()
{
    int kkk=0;
    char c=getchar();
    int px=1;
    while(c<'0' | c>'9')
    {
        if(c=='-')
            px=-1;
        c=getchar();
    }
    while(c>='0' & c<='9')
        kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
    return kkk*px;
}
int tot,root,n,m;
struct sb
{
    int son[2],fa,size,value,F;
}tree[100001];
inline int up(int bj)
{
    tree[bj].size=tree[tree[bj].son[0]].size+tree[tree[bj].son[1]].size+1;
}
inline int down(int bj)
{
    if(tree[bj].F)
    {
        tree[tree[bj].son[0]].F^=1;
        tree[tree[bj].son[1]].F^=1;
        tree[bj].F=0;
        swap(tree[bj].son[0],tree[bj].son[1]);
    }
}
inline int rotate(int x)
{
    int y=tree[x].fa;
    int z=tree[y].fa;
    int check=(tree[y].son[1]==x);
    tree[z].son[tree[z].son[1]==y]=x;
    tree[x].fa=z;
    tree[y].son[check]=tree[x].son[check^1];
    tree[tree[x].son[check^1]].fa=y;
    tree[x].son[check^1]=y;
    tree[y].fa=x;
    up(y),up(x);
}
inline int splay(int x,int goal)
{
    while(tree[x].fa!=goal)
    {
        int y=tree[x].fa,z=tree[y].fa;
        if(z!=goal)
            (tree[y].son[0]==x)^(tree[z].son[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0)
        root=x;
}
inline int insert(int x)
{
    int u=root,fa=0;
    while(u)
    {
        fa=u;
        u=tree[u].son[x>tree[u].value];
    }
    u=++tot;
    if(fa)
        tree[fa].son[x>tree[fa].value]=u;
    tree[u].value=x;
    tree[u].son[0]=tree[u].son[1]=0;
    tree[u].size=1;
    tree[u].fa=fa;
    tree[u].F=0;
    splay(u,0);
}
inline int numk(int x)
{
    int u=root;
    if(tree[u].size<x)
        return 0;
    while(1)
    {
        down(u);
        int y=tree[u].son[0];
        if(tree[y].size+1<x)
            x-=(tree[y].size+1),u=tree[u].son[1];
        else
            if(tree[y].size>=x)
                u=y;
            else
                return tree[u].value;
    }
}
int out(int bj)
{
    down(bj);
    if(tree[bj].son[0])
        out(tree[bj].son[0]);
    if(tree[bj].value>=2 & tree[bj].value<=n+1)
        printf("%d ",tree[bj].value-1);
    if(tree[bj].son[1])
        out(tree[bj].son[1]);
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n+2;++i)
        insert(i);
    for(register int i=1;i<=m;++i)
    {
        int l=read(),r=read();
        int al=numk(l),ar=numk(r+2);
        splay(al,0),splay(ar,al);
        tree[tree[tree[root].son[1]].son[0]].F^=1;
    }
    out(root);
    return 0;
}

这是T了后3个点的代码