求救大佬

P3391 【模板】文艺平衡树

陌尘缘_怜 @ 2019-04-07 23:38:48

程序被样例卡了。 由于在第三次修改操作时死循环,经调试目前初步确定问题出在kth()中。虽本人先学过treap,又对照了大佬的程序,但还是无法找出问题所在,特此求救。

debug没删,大佬可以试一下,谢谢

#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
int n,m;

int ch[100005][2],fa[100005],v[100005];
int s[100005],c[100005],lazy[100005];int rt=0,cned=0;

int chk(int x) {return ch[fa[x]][1]==x;}
void pushup(int x) {s[x]=s[ch[x][0]]+s[ch[x][1]]+c[x];} 
void pushdown(int x)
{
    if(lazy[x])
    {
        swap(ch[x][0],ch[x][1]);
        lazy[ch[x][0]]^=1;lazy[ch[x][1]]^=1;
        lazy[x]=0;
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[x][k^1]=y;fa[y]=x;
    ch[y][k]=w;fa[w]=y;
    ch[z][chk(y)]=x;fa[x]=z;
    pushup(y);pushup(x);//顺序要注意 
}
void splay(int x,int goal=0)
{
    while(fa[x]!=goal)
    {
        int y=fa[x],z=fa[y];
        if(z!=goal)
            if(chk(x)==chk(y)) rotate(y);
            else rotate(x);
        rotate(x);
    }
    if(!goal) rt=x;
}
void insert(int k)
{
    int x=rt,y=0;
    while(x and v[x]!=k)
        y=x,x=ch[x][k>v[x]];
    if(x) c[x]++;
    else 
    {
        x=++cned;
        ch[y][k>v[y]]=x;
        ch[x][0]=ch[x][1]=0;
        fa[x]=y;v[x]=k;
        s[x]=c[x]=1;
    } 
    splay(x);
}
int kth(int k)
{
    int x=rt;
    while(x)
    {//此处卡循环 
        pushdown(x);//printf("***");
        if(k>s[ch[x][0]] and k<=s[ch[x][0]]+c[x]) return x;
        else if(k<=s[ch[x][0]]) x=ch[x][0];
             else k-=s[ch[x][0]]+c[x],x=ch[x][1];
    }
    return x;
}int cnt=0;
void revise(int l,int r)
{
    int x=kth(l);//printf("@@%d\n",++cnt);
    int y=kth(r+2);
    //printf("##%d %d %d \n",cnt,x,y);
    splay(x);splay(y,x);
    lazy[ch[y][0]]^=1;
}
void output(int x)
{
    pushdown(x);
    if(ch[x][0]) output(ch[x][0]);
    if(v[x]>2 and v[x]<n+2) printf("%d ",v[x]-1);
    if(ch[x][1]) output(ch[x][1]);
}
int main()
{
    scanf("%d%d",&n,&m);int l,r;
    for(int i=1;i<=n+2;i++) insert(i);
    while(m--)
    {
        scanf("%d%d",&l,&r);
        revise(l,r);
    } 
    output(rt);
    return 0;
} 

by sleepyNick @ 2019-04-07 23:45:16

kth那边确定不是or而是end?


by sleepyNick @ 2019-04-07 23:46:06

额好像没错


by 陌尘缘_怜 @ 2019-04-08 14:24:58

发现将rotate中顺序改了之后不卡循环了 但输出为 4 3 2 5

void rotate(int x)
{
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[z][chk(y)]=x;fa[x]=z;
    ch[y][k]=w;fa[w]=y;
    ch[x][k^1]=y;fa[y]=x;
    pushup(y);pushup(x);//顺序要注意 
}

by 陌尘缘_怜 @ 2019-04-08 15:43:29

已过,顺便为新人分享一下经验

rotate中z与x的关系一定要放在第一位,因为需要查询chk(y)


|