震惊!蒟蒻竟跪地求dalao帮助

P3391 【模板】文艺平衡树

Cgod @ 2018-02-21 21:38:54

RT

本地测试秒出解,洛谷上TLE

#include<iostream>
#include<cstdio>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define gt getchar()
#define rg register
using namespace std;
const int N=5e4+5;
int f[N],ch[N][2],lz[N],root,s[N],cnt,val[N],n,m;
inline int in()
{
    int k=0,p=1;
    char ch=gt;
    while((ch>'9'||ch<'0')&&ch!='-')ch=gt;
    if(ch=='-')p=-1,ch=gt;
    while(ch>='0'&&ch<='9')k=(k<<3)+(k<<1)+(ch^48),ch=gt;
    return k*p;
}
inline void clear(int x){ch[x][0]=ch[x][1]=f[x]=lz[x]=0;}
inline int get(int x){return ch[f[x]][1]==x;}
inline void maintain(int x){s[x]=s[lc]+s[rc]+1;}
inline void update(int x)
{
    if(!x)return;
    if(lz[x])
    {
        lz[lc]^=1,lz[rc]^=1,lz[x]^=1;
        swap(lc,rc);
    }
    return;
}
inline void rotate(int x)
{
    update(f[x]);update(x);
    int fa=f[x],gr=f[fa],p=get(x);
    ch[fa][p]=ch[x][p^1];f[ch[fa][p]]=fa;
    ch[x][p^1]=fa;f[fa]=x;f[x]=gr;
    if(gr)
    {
        int d=ch[gr][1]==fa;
        ch[gr][d]=x;
    }
    maintain(fa);maintain(x);
}
inline void splay(int x,int mu)
{
    for(int fa;(fa=f[x])!=mu;rotate(x))
        if(f[fa]!=mu)
            rotate(get(x)==get(fa)?fa:x);
    if(!mu)root=x;maintain(x);
}
int init(int l,int r,int fa)
{
    int x=++cnt,mid=(l+r)>>1;
    f[x]=fa,val[x]=mid;
    if(l<mid)lc=init(l,mid-1,x);
    if(r>mid)rc=init(mid+1,r,x);
    maintain(x);
}
inline int kth(int k,int x)
{
    update(x);
    int d=s[lc];
    if(k==d+1)return x;
    if(k<=d)return kth(k,lc);
    return kth(k-d-1,rc);
}
void print(int x)
{
    if(x)
    {
        update(x);
        print(lc);
        if(val[x]>=1&&val[x]<=n)printf("%d ",val[x]);
        print(rc);
    }
}
int main()
{
    n=in();
    root=init(0,n+1,0);
    m=in();
    while(m--)
    {
        int l=in(),r=in();
        l=kth(l,root);r=kth(r+2,root);
        splay(l,0),splay(r,l);
        lz[ch[r][0]]^=1;
    }
    print(root);
    return 0;
}

by Cgod @ 2018-02-21 21:51:10

@Flashhu


by 夏色祭 @ 2018-02-21 21:53:54

@cx233666 那你就在luoguIDE上调试吧。。。还有我只是只菜鸡。。


by Cgod @ 2018-02-21 21:55:34

。。。


by λᴉʍ @ 2018-02-21 22:03:30

WA


by Cgod @ 2018-02-21 22:04:57

%%%@xzz_233 巨佬


by FlashHu @ 2018-02-21 22:10:01

LuoguIDE上手动断点,发现到第一次kth时就死掉了


by FlashHu @ 2018-02-21 22:11:32

init没有返回值?!


by FlashHu @ 2018-02-21 22:15:26

tmp.cpp:60:1: warning: no return statement in function returning non-void [-Wreturn-type] ——Emacs编译信息,应该就这个问题吧


by Cgod @ 2018-02-21 22:16:22

%%%@Flashhu 解决了

还是HTJ大佬最好了


by Cgod @ 2018-02-21 22:16:49

Emacs怎么过的。。。


上一页 | 下一页