代码

// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>

const int MAXN=300000+5,MAXM=MAXN*5,p=19260817;
struct FHQTreap {
    int l,r,size,ran;
    long long s,e,cnt;
} t[MAXM],t2[MAXM];
int root[MAXN];
int ind=0,ind2=0,rt=0;

inline void update(int x) {
    t[x].size=t[t[x].l].size+t[t[x].r].size+1;
    t[x].cnt=t[t[x].l].cnt+t[t[x].r].cnt+t[x].e-t[x].s+1;
}

inline void update2(int x) {
    t2[x].size=t2[t2[x].l].size+t2[t2[x].r].size+1;
}

void split(int x, long long v, int &a, int &b) {
    if(!x) {
        a=0;
        b=0;
        return;
    }
    if(v<=t[t[x].l].cnt) {
        b=x;
        split(t[x].l,v,a,t[x].l);
    } else {
        a=x;
        v-=t[t[x].l].cnt+t[x].e-t[x].s+1;
        if(v<=0) {
            b=t[x].r;
            t[x].r=0;
        } else {
            split(t[x].r,v,t[x].r,b);
        }
    }
    update(x);
}

void splits(int x, int v, int &a, int &b) {
    if(!x) {
        a=0;
        b=0;
        return;
    }
    if(v<=t[t[x].l].size) {
        b=x;
        splits(t[x].l,v,a,t[x].l);
    } else {
        a=x;
        splits(t[x].r,v-t[t[x].l].size-1,t[x].r,b);
    }
    update(x);
}

int merge(int a, int b) {
    if(!a||!b) {
        return a+b;
    }
    if(t[a].ran<t[b].ran) {
        t[a].r=merge(t[a].r,b);
        update(a);
        return a;
    } else {
        t[b].l=merge(a,t[b].l);
        update(b);
        return b;
    }
}

inline int newnode(long long s, long long e) {
    int x=++ind;
    t[x].ran=rand();
    t[x].size=1;
    t[x].s=s;
    t[x].e=e;
    t[x].cnt=e-s+1;
    return x;
}

void split2(int x, int v, int &a, int &b) {
    if(!x) {
        a=0;
        b=0;
        return;
    }
    if(v<=t2[t2[x].l].size) {
        b=x;
        split2(t2[x].l,v,a,t2[x].l);
    } else {
        a=x;
        split2(t2[x].r,v-t2[t2[x].l].size-1,t2[x].r,b);
    }
    update2(x);
}

int merge2(int a, int b) {
    if(!a||!b) {
        return a+b;
    }
    if(t2[a].ran<t2[b].ran) {
        t2[a].r=merge2(t2[a].r,b);
        update2(a);
        return a;
    } else {
        t2[b].l=merge2(a,t2[b].l);
        update2(b);
        return b;
    }
}

inline int newnode2(long long s) {
    int x=++ind2;
    t2[x].ran=rand();
    t2[x].size=1;
    t2[x].s=s;
    return x;
}

long long solve1(int x, int y) {
    int a=0,b=0,c=0,v;
    long long ans;
    split(root[x],y,a,c);
    splits(a,t[a].size-1,a,b);
    v=y-t[a].cnt;
    ans=t[b].s+v-1;
    if(t[b].cnt==1) {
        root[x]=merge(a,c);
    } else {
        if(v==1) {
            t[b].s++;
            t[b].cnt--;
            root[x]=merge(merge(a,b),c);
        } else if(v==t[b].cnt) {
            t[b].e--;
            t[b].cnt--;
            root[x]=merge(merge(a,b),c);
        } else {
            root[x]=merge(a,newnode(t[b].s,t[b].s+v-2));
            root[x]=merge(root[x],newnode(t[b].s+v,t[b].e));
            root[x]=merge(root[x],c);
        }
    }
    a=b=c=0;
    split2(rt,x,a,c);
    split2(a,x-1,a,b);
    root[x]=merge(root[x],newnode(t2[b].s,t2[b].s));
    rt=merge2(merge2(a,c),newnode2(ans));
    return ans;
}

long long solve2(int x, int y) {
    int a=0,b=0,c=0;
    long long ans;
    split2(rt,x,a,c);
    split2(a,x-1,a,b);
    ans=t2[b].s;
    rt=merge2(merge2(a,c),b);
    return ans;
}

int main() {
    srand(p);
    int Q;
    long long N,M,i;
    scanf("%lld%lld%d",&N,&M,&Q);
    int x,y;
    for(i=1;i<=N;i++) {
        root[i]=newnode((i-1)*M+1,i*M-1);
        rt=merge2(rt,newnode2(i*M));
    }
    for(i=1;i<=Q;i++) {
        scanf("%d%d",&x,&y);
        if(y==M) {
            printf("%lld\n",solve2(x,y));
        } else {
            printf("%lld\n",solve1(x,y));
        }
    }
    return 0;
}

评测结果