例如自个儿要处理excel中多少,有用的行只有500行澳门永利娱乐总站

实则在大部分办事中大家能因以前处理来明确我们的数组有多大,那样大家就可以声明相应大小的数组了。我倍感那种“动态”数组就够本身用了。比如小编要处理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,全部的操作只提到第贰行和结尾一列

用数据结构分别维护第2行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

二十四分 树状数组

另一种求解格局,上面99分线段树方法于此类似

多少个树状数组,树状数组c1掩护第一行,树状数组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中找到第一个,输出,删除,加到最终边

不然,splay0中找到第y个,输出,从splay0中去除,加到splay1中;找到splay1中首个,删除,加到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分 线段树

 

对于每一行维护3个线段树

强烈不大概超前都开满,所以动态开节点 

 

线段树区间维护的高低固定,所以动态删除和动态增进不是很有利

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

始于我们默许维护前n行m-1列的线条树中全数节点都以满的

保险最后一列的线条树也是满的

 

剔除操作:

用sum[k]记录下k包罗的那段距离删除的数的个数

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

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

不然,查的数减去 区间大小-sum[k]
,到右孩子查

 

丰硕操作:

令开n+3个vector,存储动态增加到对应线段树里的数

 

询问操作:

如果y=m,

一旦维护最终一列的线条树是第n+1颗

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

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

不然输出第n+壹个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

 

九十八分 树状数组

树状数组不可以动态开节点

贰拾陆分树状数组做法中,树状数组的功能是询问k值

在此间大家照样只用树状数组查询k值

 

大家不存储没有离队过的因素,因为知道了它一初步在第i行第j列后就可以得出它的编号是(i-1)*m+j

而会离队的要素至七唯有q个

据此对于每一行的前m-1列和末段一列都开1个vector
Ai,B,记录本行或最后一列补进来的编号

 

历次询问的(x,y)是第j个冒出在第x行的数只与
这一次询问从前对第x行进行的摸底有关

暗中认同原来队列中的数是第叁到m个出现在行业的数

那就可以读入全数数据,离线处理

若大家能够处理出每多个查询(x,y)应该是第多少个冒出在第x行的数,记为pre[i]

接下来按输入顺序枚举每3个询问(x,y)

若y!=m,2个操作:

1、第x行第pre[i]个数出队,到最后一列的终极贰个岗位,即vector
B中投入第x行第pre[i]个数

二 、第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个数在哪些岗位

处理三个,树状数组中删二个

处理完一行之后,再把从前删的都加回来供下一行采纳

那般大家就拿走了每2个查询(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

 没有运用的距离都压缩成3个大节点

每一行一个splay,最终一列三个splay

刚开始每一行的前m-1列都压缩成三个点

终极一列的splay把成分填进去

与三十多分不相同的是询问的时候须要分裂节点

 

 

澳门永利娱乐总站 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

 

相关文章