求助!

回复帖子

@xiayuyang300 2019-06-11 18:33 回复

splay本机测试第一个点时是对的,但是交上去显示WA 评测记录https://www.luogu.org/recordnew/show/19778198

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
struct node{
    int l,r,size,fa,son[2];
}t[maxn];
int cnt;
typedef long long ll;
struct Splay{
    int rt;
    inline void pushup(int x){t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+t[x].r-t[x].l;}
    inline int newnode(int l,int r){t[++cnt].fa=t[cnt].son[0]=t[cnt].son[1]=0;t[cnt].size=(t[cnt].r=r)-(t[cnt].l=l);return cnt;}
    void rotate(int x){
        int y=t[x].fa,z=t[y].fa,k=t[y].son[1]==x;
        t[x].fa=z;t[z].son[t[z].son[1]==y]=x;
        t[t[x].son[k^1]].fa=y;t[y].son[k]=t[x].son[k^1];
        t[x].son[k^1]=y;t[y].fa=x;
        pushup(y);pushup(x);
    }
    void splay(int x){
        while(t[x].fa){
            int y=t[x].fa,z=t[y].fa;
            if(z)
            (t[z].son[0]==y)^(t[y].son[0]==x)?rotate(x):rotate(y);
            rotate(x);
        }
        rt=x;
    }
    inline void init(int l,int r){rt=newnode(l,r);}
    int split(int x,ll k){
        k+=t[x].l;
        int y=newnode(k,t[x].r);
        t[x].r=k;
        if(t[x].son[1]==0){
            t[t[x].son[1]=y].fa=x;
        }
        else{
            int u=t[x].son[1];
            while(t[u].son[0])u=t[u].son[0];
            t[t[u].son[0]=y].fa=u;
            while(u!=x)pushup(u),u=t[u].fa;
        }
        splay(y);
        return y;
    }
    ll popkth(ll k){
        int u=rt;
        while(1){
            //printf("%d %d\n",u,t[u].size);
            if(t[t[u].son[0]].size>=k)u=t[u].son[0];
            else{
                k-=t[t[u].son[0]].size;
                if(k<=t[u].r-t[u].l){
                    if(k!=t[u].r-t[u].l)split(u,k);
                    if(k!=1)u=split(u,k-1);
                    break;
                }
                else{
                    k-=t[u].r-t[u].l;
                    u=t[u].son[1];
                }
            }
        }
        splay(u);
        t[t[u].son[0]].fa=t[t[u].son[1]].fa=0;
        if(!t[u].son[0])rt=t[u].son[1];
        else {
            int o=t[u].son[0];
            while(t[o].son[1])o=t[o].son[1];
            splay(o);
            pushup(rt=t[t[o].son[1]=t[u].son[1]].fa=o);
        }
        return t[u].l;
    }
    void pushback(ll k){
        int y=newnode(k,k+1);
        if(!rt)rt=y;
        else{
            int u=rt;
            while(t[u].son[1])u=t[u].son[1];
            splay(u);pushup(t[t[u].son[1]=y].fa=u);
        }
    }
}s[maxn];
int n,m,q;
int main(){
    //freopen("3960.in","r",stdin);
    //freopen("3960.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for(ll i=1;i<=n;i++)s[i].init((i-1)*m+1,i*m);
    s[0].init(m,m+1);
    for(ll i=2;i<=n;i++)s[0].pushback(i*m);
    int x,y;ll p;
    while(q--){
        scanf("%d%d",&x,&y);
        s[x].pushback(s[0].popkth(x));
        p=s[x].popkth(y);
        printf("%lld\n",p);
        s[0].pushback(p);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。