c# 动态数组—–“动态”数组。NOIP2017 列队。

实在在大多数干活中我们能由此前处理来确定我们的数组有多深,这样咱们就得声明相应大小的数组了。我倍感这种“动态”数组就足足我为此了。比如自己而处理excel中数量,数据发生m行*n列,这样自己虽得透过读取excel来确定m和n的轻重,然后再次声称m行n列的二维数组,这样就可以处理了啊。

https://www.luogu.org/problemnew/show/P3960

澳门网上娱乐 1

 

澳门网上娱乐 2澳门网上娱乐 3

p<=500 50分 模拟

每个人之出队只会潜移默化时行及最后一列

p<=500,有用之实行就发生500实行

所以就保障这p行和末段一排列的音信

下一场模拟

岁月复杂度:O(p*(n+m))

空中复杂度:O(p*m+n)

 

澳门网上娱乐 4澳门网上娱乐 5

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 501
#define M 50001

typedef long long LL;

LL pos[N][M],last[M];

struct node
{
    int x,y;
}e[N];

int h[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int main()
{
    int n,m,q;
    read(n); read(m); read(q);
    for(int i=1;i<=q;++i) 
    {
        read(e[i].x);
        read(e[i].y);
        h[i]=e[i].x;
    }
    sort(h+1,h+q+1);
    int tot=unique(h+1,h+q+1)-h-1;
    LL t;
    for(int i=1;i<=tot;++i)
    {
        t=(LL)(h[i]-1)*m;
        for(int j=1;j<=m;++j) pos[i][j]=++t;
    }
    for(int i=1;i<=n;++i) last[i]=last[i-1]+m;
    int nx;
    LL ans;
    for(int i=1;i<=q;++i)
    {
        nx=lower_bound(h+1,h+tot+1,e[i].x)-h;
        if(e[i].y==m) ans=last[h[nx]];
        else ans=pos[nx][e[i].y];
        cout<<ans<<'\n';
        if(e[i].y!=m)
        {
            for(int j=e[i].y;j<m-1;++j) pos[nx][j]=pos[nx][j+1];
            pos[nx][m-1]=last[h[nx]];
        }
        for(int j=h[nx];j<n;++j) last[j]=last[j+1];
        last[n]=ans;
    }
}

View Code

 

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace ConsoleApplication1array
 8 {
 9     class Program
10     {
11         static void Main(string[] args)
12         {
13             //Random r = new Random();
14             Console.WriteLine("请输入二维数组的行数:");
15             int i = int.Parse(Console.ReadLine()); //3; //r.Next() % 10 + 10;
16             Console.WriteLine("请输入二维数组的列数:");
17             int m = int.Parse(Console.ReadLine ());//4;
18             int[,] array1 = new int[i,m];
19             for (int fi = 0; fi < i;fi++ )
20             {
21                 for (int fj = 0; fj < m; fj++)
22                 {
23                     array1[fi, fj] = fi + fj;
24                     Console.Write("{0}\t ",array1[fi, fj]);
25                 }
26                 Console.WriteLine();
27 
28             }
29             //foreach (int  arr in array1)
30             //{
31                 
32             //    Console.WriteLine(arr);
33             //    Console.WriteLine();
34             //}
35             //for (int j = 0; j < i; j++)
36             //{
37             //    array1[j] = j;//r.Next(0,10);
38             //    Console.WriteLine(array1[j]);
39             //    Console.WriteLine();
40             //}
41             Console.ReadKey();
42         }
43     }
44 }

x=1

x=1,全部的操作才关乎第一履与终极一排

故数据结构分别维护第一行A和结尾一列B

历次的出队一定给查询A中之第k单元素

然后B中最终插入一个屡

当A饱受不足k个要素时,到B中翻第k-|A|个元素

 

c#“动态数组”

30分 线段树

A中因第i个数的价当下标

B中以第i个数被插入到B中的逐一作下标,另用a数组存它的价值

澳门网上娱乐 6澳门网上娱乐 7

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

int n;

int sum[N<<2];

LL a[N<<1];
int sum2[N<<3];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void build(int k,int l,int r)
{
    sum[k]=r-l+1;
    if(l==r)  return; 
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

int query(int k,int l,int r,int pos)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(pos<=sum[k<<1]) return query(k<<1,l,mid,pos);
    return query(k<<1|1,mid+1,r,pos-sum[k<<1]);
}

void change(int k,int l,int r,int pos)
{
    if(l==r)
    {
        sum[k]=0;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) change(k<<1,l,mid,pos);
    else change(k<<1|1,mid+1,r,pos);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}

void build2(int k,int l,int r)
{
    if(l==r) 
    {
        if(l<=n) sum2[k]=1;
        return;
    }
    int mid=l+r>>1;
    build2(k<<1,l,mid);
    build2(k<<1|1,mid+1,r);
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
}

int query2(int k,int l,int r,int pos)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(pos<=sum2[k<<1]) return query2(k<<1,l,mid,pos);
    return query2(k<<1|1,mid+1,r,pos-sum2[k<<1]);
}

void change2(int k,int l,int r,int pos,int w)
{
    if(l==r)
    {
        sum2[k]=w;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) change2(k<<1,l,mid,pos,w);
    else change2(k<<1|1,mid+1,r,pos,w);
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
}

int main()
{
    int m,q;
    read(n); read(m); read(q);
    build(1,1,m-1);
    int i=1; LL j=m;
    for(;i<=n;j+=m,++i) a[i]=j;
    build2(1,1,n+q);
    int x,y;  LL ans; 
    for(int i=1;i<=q;++i)
    {
        read(x); read(y);
        if(y<=sum[1])
        {
            ans=query(1,1,m-1,y);
            cout<<ans<<'\n';
            change(1,1,m-1,ans);
            change2(1,1,n+q,n+i,1);
            a[n+i]=ans;
        }
        else
        {
            y-=sum[1];
            y=query2(1,1,n+q,y);
            cout<<a[y]<<'\n';
            change2(1,1,n+q,y,0);
            change2(1,1,n+q,n+i,1);
            a[n+i]=a[y];
        }
    }
}

View Code

 

 澳门网上娱乐 8

30分 树状数组

另外一样种求解方式,下面100分叉线段树方法为斯类似

星星独树状数组,树状数组c1维护第1实践,树状数组c2一个保护最后1列

0 1
分别代表这位置来无发生反复

这么虽可采用树桩数组查询第k个数

在树状数组外次分叉即可

从而少独vector
记录后上加进树状数组中之数

始于树状数组是充满之,即c1来第一履的所有数,c2出最终一列的所有数

(x,y)出队

如果y=m,那么到c2中找第1个元素t

若t<=n
输出m*x,c2的末尾加入t

要不
到相应的vector中寻觅第 t-n-1(下标从0开始)个出口, 

输出的价插入到c2的最终

如果y!=m,到c1中找第y个元素t

若t<=m-1
输出t

否则到相应的vector中追寻第t-m(下标从0开始)个出口

输出的值插入到c2的末梢

 

 

澳门网上娱乐 9澳门网上娱乐 10

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

#define N 300001

using namespace std;

typedef long long LL;

#define lowbit(x) x&-x

int n,m,q,mx;

int c1[N<<1],c2[N<<1];
int siz_c1,siz_c2;

vector<LL>V[2];

int l,r,mid,tmp;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void add(int *c,int x,int w)
{
    while(x<=mx)
    {
        c[x]+=w;
        x+=lowbit(x);
    }
}

int ask(int *c,int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

LL work2(int x,LL y)
{
    l=1; r=mx;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(c2,mid)>=x) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    add(c2,tmp,-1);
    LL ans=tmp<=n ? (LL)tmp*m : V[1][tmp-n-1];
    add(c2,++siz_c2,1);
    V[1].push_back(y ? y : ans);
    return ans;
}

LL work1(int x,int y)
{
    l=1; r=mx;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(c1,mid)>=y) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    add(c1,tmp,-1);
    LL ans=tmp<m ? tmp : V[0][tmp-m];
    add(c1,++siz_c1,1);
    V[0].push_back(work2(x,ans));
    return ans;
}

int main()
{
    read(n); read(m); read(q);
    mx=max(m,n)+q;
    for(int i=1;i<m;++i) add(c1,i,1);
    for(int i=1;i<=n;++i) add(c2,i,1);
    siz_c1=m-1; siz_c2=n;
    int x,y; 
    for(int i=1;i<=q;++i)
    {
        read(x); read(y);
        if(y==m) cout<<work2(x,0)<<'\n';
        else cout<<work1(x,y)<<'\n';
    }
}

View Code

 

 

 

30分 splay

率先尽splay0,最后一排splay1

裸地splay删除、查询k值、添加 

查询(x,y)

要是y==m,splay1中找到第1单,输出,删除,加到最后当

不然,splay0中找到第y独,输出,从splay0中除去,加至splay1中;找到splay1中第1单,删除,加至splay0中

 

澳门网上娱乐 11澳门网上娱乐 12

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 300001

typedef long long LL;

LL a[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))  { x=x*10+c-'0'; c=getchar(); }    
}

struct SPLAY
{
    int root,tot;
    int fa[N<<1],ch[N<<1][2];
    int siz[N<<1];
    LL num[N<<1];

    void build(int l,int r,int f,LL *a)
    {
        if(l>r) return;
        int mid=l+r>>1;
        fa[mid]=f;
        ch[f][mid>f]=mid;
        num[mid]=a[mid];
        siz[mid]=1;
        build(l,mid-1,mid,a);
        build(mid+1,r,mid,a);
        siz[mid]=siz[ch[mid][0]]+siz[ch[mid][1]]+1;
    }

    void update(int x)
    {
        siz[x]=1;
        if(ch[x][0]) siz[x]+=siz[ch[x][0]];
        if(ch[x][1]) siz[x]+=siz[ch[x][1]];
    }

    bool getson(int x)
    {
        return ch[fa[x]][1]==x;
    }

    void rotate(int x)
    {
        int y=fa[x],z=fa[y],k=getson(x);
        if(y!=root) ch[z][ch[z][1]==y]=x;
        ch[y][k]=ch[x][k^1]; ch[x][k^1]=y;
        fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
        update(y);
    }

    void splay(int x)
    {
        for(int f;f=fa[x];rotate(x))
            if(fa[f]) rotate(getson(x)==getson(f) ? f : x);
        update(x);
        root=x;
    }

    void insert_last(LL x)
    {
        if(!root)
        {
            root=++tot;
            num[tot]=x;
            siz[tot]=1;
            return;
        }
        int now=root;
        while(ch[now][1]) now=ch[now][1];
        ch[now][1]=++tot;
        fa[tot]=now;
        num[tot]=x;
        siz[tot]=1;
        splay(tot);
    }

    int find_kth(int x)
    {
        int now=root;
        while(1)
        {
            if(siz[ch[now][0]]+1==x) return now;
            if(ch[now][0] && siz[ch[now][0]]>=x)
            {
                now=ch[now][0];
                continue;
            }
            x-=siz[ch[now][0]]+1;
            now=ch[now][1];
        }
    }

    int getpre()
    {
        int now=ch[root][0];
        while(ch[now][1]) now=ch[now][1];
        return now;
    }

    void del()
    {
        if(!ch[root][0] && !ch[root][1])
        {
            root=0;
            return;
        }
        if(!ch[root][0])
        {
            root=ch[root][1];
            fa[root]=0;
            return;
        }
        if(!ch[root][1])
        {
            root=ch[root][0];
            fa[root]=0;
            return;
        }
        int pre=getpre();
        int tmp=root;
        splay(pre);
        ch[root][1]=ch[tmp][1];
        fa[ch[root][1]]=root;
        update(root);
    }

}Splay[2];

int main()
{
    int n,m,q;
    read(n); 
    read(m); 
    read(q);
    int i; LL j;
    for(i=1;i<m;++i)  
        a[i]=i;
    Splay[0].build(1,m-1,0,a);
    Splay[0].tot=m-1;
    Splay[0].root=m>>1;
    for(i=1,j=m;i<=n;++i,j+=m) 
        a[i]=j;
    Splay[1].build(1,n,0,a);
    Splay[1].tot=n;
    Splay[1].root=n+1>>1; 
    int x,y; int id0,id1;
    for(i=1;i<=q;++i)
    {
        read(x);
        read(y);
        if(y==m)
        {
            id0=Splay[1].find_kth(1);
            Splay[1].splay(id0);
            Splay[1].del();
            Splay[1].insert_last(Splay[0].num[id0]);
            cout<<Splay[1].num[id0];
            continue;
        }
        id0=Splay[0].find_kth(y);
        Splay[0].splay(id0);
        Splay[0].del();
        Splay[1].insert_last(Splay[0].num[id0]);
        id1=Splay[1].find_kth(x);
        Splay[1].splay(id1);
        Splay[1].del();
        Splay[0].insert_last(Splay[1].num[id1]);
        cout<<Splay[0].num[id0]<<'\n';
    }    
}

View Code

 

 

满分做法

 

和x=1的做法类似

咱们只有待为此n个数据结构Ai维护每一行的前m-1只

重复就此一个数据结构B维护最后一排即可

只顾所选数据结构的空间问题

各级一样赖询问(x,y)

若果y不是最后一排列,就由Ax中找到第y单要素,记为ans,输出ans,Ax中删去ans,

管B中的第x个要素插到Ax的末段当,把ans插到B的末尾给

假设y是最终一排,在B中找到第y个元素,记为ans,输出ans,B中删去ans

把ans插入到B的最终一个

 

100分 线段树

 

于各级一样履维护一个丝段树

强烈不克提前都开满,所以动态开节点 

 

线段树区间维护的轻重固定,所以动态删除和动态增长非是生方便

故而不直接执行删除操作,不在线段落树上添加

启我们默认维护前n行m-1排列的线树中所有节点都是满之

护最后一排列的线条树啊是充满的

 

删去操作:

用sum[k]笔录下k包含的当即段距离删除的反复的个数

如此查询时,当前距离数的个数
为区间大小-sum[k]

设若要查的数<=区间大小-sum[k]
到左孩子翻

再不,查的一再减去 区里面大小-sum[k]
,到右手孩子翻

 

长操作:

让开n+1个vector,存储动态增长到对诺线段树里的频繁

 

询问操作:

如果y=m,

比方维护最后一排的线条树是第n+1发

查询第n+1颗线段树里第x只值pos

若pos<=n,输出 pos*m,

不然输出第n+1个vector里第pos-n-1(下标从0开始)个因素

输出的价插入到最后一列的线段树的结尾

如果y!=m

暨第x颗线段树里查询第y个数pos

若pos<=m-1,输出(x-1)*m+pos,

不然输出第x只vector里
第pos-m(下标从0开始)个元素

输出的价值插入到终极一排线段树的末尾

 

澳门网上娱乐 13澳门网上娱乐 14

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

int n,m,q,mx;

int tot;
int root[N+1],lc[N*20],rc[N*20];
int sum[N*20];

int pos;

vector<LL>V[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int query(int k,int l,int r,int w)
{
    if(l==r) return l;
    int mid=l+r>>1,tmp=mid-l+1-sum[lc[k]];
    if(w<=tmp) return query(lc[k],l,mid,w);
    return query(rc[k],mid+1,r,w-tmp);
}

void change(int &k,int l,int r)
{
    if(!k) k=++tot;
    sum[k]++;
    if(l==r) return;
    int mid=l+r>>1;
    if(pos<=mid) change(lc[k],l,mid);
    else change(rc[k],mid+1,r);
}

LL work0(int x,LL y)
{
    pos=query(root[n+1],1,mx,x);
    change(root[n+1],1,mx);
    LL ans=pos<=n ? (LL)pos*m : V[n+1][pos-n-1];
    V[n+1].push_back(y ? y : ans);
    return ans;
}

LL work1(int x,int y)
{
    pos=query(root[x],1,mx,y);
    change(root[x],1,mx);
    LL ans=pos<m ? (LL)(x-1)*m+pos : V[x][pos-m];
    V[x].push_back(work0(x,ans));
    return ans;
}

int main()
{
    read(n); read(m); read(q);
    mx=max(n,m)+q;
    int x,y;
    while(q--)
    {
        read(x); read(y);
        if(y==m) cout<<work0(x,0)<<'\n';
        else cout<<work1(x,y)<<'\n';
    }
}

View Code

 

100瓜分 树状数组

树状数组不能够动态开节点

30分树状数组做法遭到,树状数组的用意是查询k值

当这边我们还是只是所以树状数组查询k值

 

我们无存储没有离队了的因素,因为懂得了她同样开始于第i执第j排列后就是好得出它的编号是(i-1)*m+j

比方会离队的因素至多单纯发生q个

因而对每一行的前m-1列和末段一列都从头一个vector
Ai,B,记录本行或最后一排上上的号码

 

每次询问的(x,y)是第j单冒出在第x尽的频繁但及
这次询问前对第x实行进行的打听有关

默认原来队列中的数是第1暨m个出现于同行业的勤

那便可读入所有数据,离线处理

假若我们能够处理发生各一个询问(x,y)应该是第几独冒出在第x行之屡屡,记否pre[i]

接下来按照输入顺序枚举每一个了解(x,y)

若y!=m,2个操作:

1、第x行第pre[i]个数出队,到终极一排的尾声一个岗位,即vector
B中进入第x实施第pre[i]个数

2、第x履最终补充上最后一排的第x个数,即vector Ax
中在 最后一排列的第x个数

若y==m,

末了一排的第x独数出队,到最终一列末尾,vector
B中投入最后一排列第x个数

 

什么获取
最后一列的第x个数?

树状数组维护最后一排,每查询同一蹩脚(x,y),标记一次x

对树状数组中查看及的第x独数h,意呢凡第h个冒出于终极一列的一再

若h<=n,则为h*m

若h>m,那就是vector B
中第h-n-1(下标从0开始)个元素

 

怎样取得第x推行第pre[i]只冒出的再三?

若pre[i]<m,就是(x-1)*m+pre[i]

若pre[i]>=m,就是vector Ax 中
第pre[i]-m(下标从0开始)个冒出的屡屡

 

什么获取第i单询问(x,y)的pre[i]?

枚举每一样实践,

于树状数组中第二私分来第y个数在哪个岗位

拍卖一个,树状数组中删一个

处理终结一行之后,再将前剔除的且加回来供下一行以

这么咱们就算得到了各国一个查询(x,y)应该是第几个冒出于第x履的累累

 

澳门网上娱乐 15澳门网上娱乐 16

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

#define lowbit(x) x&-x

int mx;
int n,m,q;

struct node
{
    int pos,id;

    node(int pos_=0,int id_=0) : pos(pos_),id(id_)  { }

};
vector<node>V[N];
vector<LL>num[N];

int c[N<<1];

int qx[N],qy[N];

int pre[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))  { x=x*10+c-'0'; c=getchar(); }
}

void add(int x,int w)
{
    while(x<=mx)
    {
        c[x]+=w;
        x+=lowbit(x);
    }
}

int ask(int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int query_kth(int k) 
{  
    int l=0,r=mx;
    int mid,tmp;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(mid)>=k) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    return tmp;
}

void init()
{
    read(n); read(m); read(q);
    mx=max(n,m)+q;
    for(int i=1;i<=q;++i)
    {
        read(qx[i]); read(qy[i]);
        if(qy[i]!=m) V[qx[i]].push_back(node(qy[i],i));
    }
}

void solve1()
{
    for(int i=1;i<=mx;++i) add(i,1);
    int siz;
    node now;
    for(int i=1;i<=n;++i)
    {
        siz=V[i].size();
        for(int j=0;j<siz;++j)
        {
            now=V[i][j];
            pre[now.id]=query_kth(now.pos);
            add(pre[now.id],-1);
        }
        for(int j=0;j<siz;++j) add(pre[V[i][j].id],1);
    }
}

void solve2()
{
    LL ans; int h;
    for(int i=1;i<=q;++i)
    {
        h=query_kth(qx[i]);
        ans= h<=n ? (LL)h*m : num[0][h-n-1];
        add(h,-1);
        if(qy[i]!=m)
        {
            num[qx[i]].push_back(ans);
            ans= pre[i]<m ? LL(qx[i]-1)*m+pre[i] : num[qx[i]][pre[i]-m];
        }
        num[0].push_back(ans);
        cout<<ans<<'\n';
    }
}

int main()
{
    init();
    solve1();
    solve2();
}

View Code

 

100分 splay

 没有运用的间隔都减成一个生节点

各个一样行一个splay,最后一列一个splay

碰巧开头每一行的前m-1列都压缩成一个接触

最后一列的splay把元素填进

以及30私分殊之凡查询的时用分裂节点

 

 

澳门网上娱乐 17澳门网上娱乐 18

#include<cstdio>
#include<iostream>

using namespace std;

#define N 300001

typedef long long LL;

int tot;

int root[N];
int l[N*6],r[N*6];

int ch[N*6][2],fa[N*6],siz[N*6],key[N*6];
LL num[N*6];

int rt;

LL a[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void build(int l,int r,int f)
{
    if(l>r) return;
    int mid=l+r>>1;
    fa[mid]=f;
    ch[f][mid>f]=mid;
    key[mid]=siz[mid]=1;
    num[mid]=a[mid];
    build(l,mid-1,mid);
    build(mid+1,r,mid);
    siz[mid]=siz[ch[mid][0]]+siz[ch[mid][1]]+1;
}

bool getson(int x)
{
    return ch[fa[x]][1]==x;
}

void update(int x)
{
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+key[x];
}

void rotate(int x,int &goal)
{
    int y=fa[x],z=fa[y]; 
    bool k=getson(x);
    if(y!=goal) ch[z][ch[z][1]==y]=x;
    else goal=x;
    ch[y][k]=ch[x][k^1];
    ch[x][k^1]=y;
    fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
    update(y);
}

void splay(int x,int &goal)
{
    int y;
    while(x!=goal)
    {
        y=fa[x];
        if(y!=goal) rotate(getson(x)==getson(y) ? y : x,goal);
        rotate(x,goal);
    }
    update(x);
}

void split(int now,int k,int id)
{
    if(k<=siz[ch[now][0]]) split(ch[now][0],k,id);
    else if(k>siz[ch[now][0]]+key[now]) split(ch[now][1],k-siz[ch[now][0]]-key[now],id);
    else
    {
        k-=siz[ch[now][0]];
        if(k!=1)
        {
            fa[ch[++tot][0]=ch[now][0]]=tot;  
            fa[ch[now][0]=tot]=now;
            key[tot]=k-1; 
            key[now]-=k-1;
            l[tot]=l[now]; 
            r[tot]=l[now]+key[tot]-1;
            l[now]=r[tot]+1;
            update(tot);
        }
        if(key[now]!=1)
        {
            fa[ch[++tot][1]=ch[now][1]]=tot;
            fa[ch[now][1]=tot]=now;
            key[tot]=key[now]-1;
            key[now]=1;
            l[tot]=l[now]+1;
            r[tot]=r[now];
            r[now]=l[now];
            update(tot);
        }
        splay(now,root[id]);
    }
}

void insert_last(int &rt,LL x)
{
    if(!rt)
    {
        rt=++tot;
        l[tot]=r[tot]=key[tot]=siz[tot]=1;
        num[tot]=x;
        return;
    }
    int now=rt;
    while(ch[now][1]) now=ch[now][1];
    fa[++tot]=now;
    ch[now][1]=tot;
    l[tot]=r[tot]=key[tot]=siz[tot]=1;
    num[tot]=x;
    splay(tot,rt);
}

int find_kth(int now,int x)
{
    while(1)
    {
        if(x<=siz[ch[now][0]])
        {
            now=ch[now][0];
            continue;
        }
        x-=siz[ch[now][0]];
        if(x==1) return now;
        x--;
        now=ch[now][1];
    }
}

int find_pre(int rt)
{
    int now=ch[rt][0];
    while(ch[now][1]) now=ch[now][1];
    return now;
}

void del(int &rt)
{
    if(!ch[rt][0] && !ch[rt][1])
    {
        rt=0;
        return;
    }
    if(!ch[rt][0])
    {
        rt=ch[rt][1];
        return;
    }
    if(!ch[rt][1])
    {
        rt=ch[rt][0];
        return;
    }
    int pre=find_pre(rt);
    int tmp=rt;
    splay(pre,rt);
    ch[rt][1]=ch[tmp][1];
    fa[ch[rt][1]]=rt;
    update(rt);
}

int main()
{
    int n,m,q;
    read(n); read(m); read(q);
    int i; LL j;
    for(i=1,j=m;i<=n;++i,j+=m) a[i]=j;
    build(1,n,0);
    tot=n;
    root[0]=n+1>>1;
    for(int i=1;i<=n;++i)
    {
        root[i]=++tot;
        siz[tot]=m-1;
        key[tot]=m-1;
        l[tot]=1; r[tot]=m-1;
    }
    int x,y; 
    LL ans;
    int tmp;
    while(q--)
    {
        read(x); read(y);
        tmp=find_kth(root[0],x);
        splay(tmp,root[0]);
        del(root[0]);
        if(y!=m)
        {
              split(root[x],y,x);
            ans=num[root[x]] ? num[root[x]] : (LL)(x-1)*m+l[root[x]];
            del(root[x]);
            insert_last(root[0],ans);
            insert_last(root[x],num[tmp]);
        }
        else
        {
            ans=num[tmp];
            insert_last(root[0],ans);
        }
        cout<<ans<<'\n';
    }
}

View Code

 

相关文章