萌新求助

回复帖子

@maomao 2019-04-03 15:53 回复

列队Splay做法卡到了90points,再怎么优化常数啊

#include<bits/stdc++.h>
#define C const int 
#define R register int
#define M(i) memset(i,0,sizeof i)
#define ll long long
#define FRE(a) freopen(a".in","r",stdin)
#define De printf("OK\n")

using namespace std;

inline int read()
{
    int x=0;char s;
    while((s=getchar())<'0'||s>'9');
    do{x=x*10+(s^48);}while((s=getchar())>='0'&&s<='9');
    return x;
}
inline void outit(ll num)
{
    if(num>=10)outit(num/10);
    putchar(num%10+'0');
}
C M=3000010;
int n,m;
int ch[M][2],fa[M],now;
ll data[M][2],siz[M],cnt[M];
struct Splay
{
    int root;
    void up(int id){siz[id]=cnt[id]+siz[ch[id][0]]+siz[ch[id][1]];}
    void rotate(int x){
        int y=fa[x],z=fa[y],k=(x==ch[y][0]);
        if(z)ch[z][y==ch[z][1]]=x;
        fa[x]=z;fa[y]=x;ch[y][k^1]=ch[x][k];
        fa[ch[x][k]]=y;ch[x][k]=y;
        up(y);up(x);
    }
    void splay(int x,int goal=0){
        while(fa[x]^goal)
        {
            int y=fa[x],z=fa[y];
            if(z^goal)
                (x==ch[y][0])^(y==ch[z][0])?rotate(x):rotate(y);
            rotate(x);
        }
        if(!goal)root=x;
    }
    int Add(ll l,ll r){
        int x=++now;
        data[x][0]=l;data[x][1]=r;
        siz[x]=cnt[x]=r-l+1;up(x);
        return x;
    }
    void build(ll l,ll r){
        int x=Add(l,r);root=x;
        ch[x][0]=Add(0,0);ch[x][1]=Add(0,0);
        fa[ch[x][0]]=fa[ch[x][1]]=x;
        up(x);
    }
    int K_th(ll pos){
        int u=root;
        while(233)
        {
            if(pos<=siz[ch[u][0]])u=ch[u][0];
            else if(pos<=siz[ch[u][0]]+cnt[u])return u;
            else pos-=siz[ch[u][0]]+cnt[u],u=ch[u][1];
        }
    }
    int next(int k,bool flag){
        splay(k);int u=ch[root][flag];
        while(ch[u][flag^1])u=ch[u][flag^1];
        return u;
    }
    //0-last,1-next
    void insert(ll num){
        int Next=K_th(siz[root]),Last=next(Next,0);
        splay(Last);splay(Next,Last);
        ch[Next][0]=Add(num,num);fa[ch[Next][0]]=Next;
        splay(Next);
    }
    ll work(ll pos){
        int now=K_th(pos+1),Next=next(now,1),Last=next(now,0);
        splay(Last);splay(Next,root);
        int x=ch[Next][0];
        pos=pos-(siz[root]-siz[ch[root][1]]-1)+(data[x][0]-1);
        now=Next;ch[now][0]=0;
        if(data[x][1]>pos)
            ch[now][0]=Add(pos+1,data[x][1]),fa[ch[now][0]]=now,now=ch[now][0];
        if(data[x][0]<pos)
            ch[now][0]=Add(data[x][0],pos-1),fa[ch[now][0]]=now,now=ch[now][0];
        //up(ch[now][0]);up(now);up(fa[now]);
        splay(now);
        return pos;
    }
    //第x行的第y个
    void print(int now){
        if(ch[now][0])print(ch[now][0]);
        printf("(%lld,%lld) ",data[now][0],data[now][1]);
        if(ch[now][1])print(ch[now][1]);
    }
}T[M];
void Print(){
    printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
    for(R i=0;i<=n;++i)
    {
        T[i].print(T[i].root);
        printf("\n");
    }
    printf("~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();int q=read();
    T[0].build(1LL*m,1LL*m);
    for(R i=2;i<=n;++i)T[0].insert(1LL*m*i);
    for(R i=0;i<n;++i)T[i+1].build(1+1LL*i*m,1LL*(i+1)*m-1);//[l,r]
    int x,y;ll ans;
    while(q--)
    {
        //Print();
        x=read();y=read();
        T[x].insert(T[0].work(x));
        //printf("%lld\n",ans=T[x].work(y));
        outit(ans=T[x].work(y));putchar('\n');
        T[0].insert(ans);
    }
    return 0;
}
@shadowice1984 2019-04-03 16:00 回复 举报

rotate的时候仅仅update父亲不update自己

然后splay的时候额外update一下自己就行了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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