P3960 列队 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Youngsc_AFO
    请问大佬您在赛场用Splay了?
  • _rqy
    @Youngsc 嗯嗯,怎么了(反正我现在Splay都能一遍写对)
  • Lance1ot
    666,世界史真的小
  • goldimax
    左闭右开赞!
  • 紫钦
    问一下dalao:为什么空间要开那么大?似乎1,500,000就可以过了? 感谢大佬给予的良好思路%%%。
  • Dispwnl
    %%%
  • Capella
    %%%rqy!!!
  • _Sugar_
    %%%rqy
  • __shiina
    orz
  • 夏夜空
    不会树状数组会splay?QAQ
作者: _rqy  更新时间: 2017-11-13 17:43  在Ta的博客查看 举报    212  

qwq据说正解是树状数组但是我完全不会。。。

蒟蒻只会用splay做qwq。

我们观察每一行除了最后一个数之外的数在操作中是如何变化的。

如果出队在(x,y),那么第x行(除了最后一个数)会弹出第y个数,它后面的数依次左移,再在最后插入一个数(就是最后一列当前的第x个数);然后,对于最后一列,我们要弹出第x个数(插入到第x行),再在最后插入一个数(就是刚出队的那个)。

所以,我们无论是对于行还是列,都要执行两种操作:第一,弹出第k个数,第二,在尾部插入一个数。这可以用splay来实现。

但是这样的话空间复杂度是$O(nm)$。

我们发现有些人从始至终都是左右相邻的,这些人对应的splay节点可以合并。

于是我们在维护splay的时候,所有连续的数的区间我们用一个节点维护,记录这个节点表示的区间的左右端点;

如果我们发现要弹出的数在某个节点内部,我们就把它拆开,拆成3个节点(其中中间那个节点只有一个数,就是我们要的那个数),拆点的过程可以直接跑splay上的insert,删除中间那个节点就是splay上的删除。

总时间复杂度为$O(nlogn)$。

代码:

#include <cstdio>
namespace rqy{            //命名空间是为了防止和某些奇怪的变量命名冲突,也可以去掉
  typedef long long LL;
  const int N = 3000500;
  int fa[N], son[N][2], cnt;
  LL l[N], r[N], siz[N]; //l, r表示区间左右端点,此处左闭右开(个人习惯)
  struct Splay{
    int root;
    inline int newNode(LL ll, LL rr) {    //ll, rr表示新节点的区间左右端点
      ++cnt;
      fa[cnt] = son[cnt][0] = son[cnt][1] = 0;
      siz[cnt] = (r[cnt] = rr) - (l[cnt] = ll);
      return cnt;
    }
    inline void init(LL ll, LL rr) {      //初始化树,只有一个对应[ll,rr)的根节点。
      root = newNode(ll, rr);
    }
    inline void upd(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + r[x] - l[x]; }
    inline int dir(int x) { return son[fa[x]][1] == x; }    //x是fa[x]的哪个儿子
    inline void rotate(int x) {   //没什么好说的
      int d = dir(x), f = fa[x];
      fa[x] = fa[f];
      if (f == root) root = x;
      else son[fa[f]][dir(f)] = x;
      if (son[f][d] = son[x][d ^ 1]) fa[son[f][d]] = f;
      fa[son[x][d ^ 1] = f] = x;
      upd(f);
      upd(x);
    }
    void splay(int x) {   //同上
      for (; fa[x]; rotate(x))
        if (fa[fa[x]]) rotate(dir(x) == dir(fa[x]) ? fa[x] : x);
    }
    int splitNode(int x, LL k) {  //把节点x分裂,分裂后x的区间里前k个数还在x节点上,
      k += l[x];                  //后边的数对应新节点(即该函数返回值)
      int y = newNode(k, r[x]);
      r[x] = k;
      if (son[x][1] == 0) {
        fa[son[x][1] = y] = x;
      } else {
        int t = son[x][1];
        while (son[t][0]) t = son[t][0];
        fa[son[t][0] = y] = t;
        while (t != x) upd(t), t = fa[t];
      }
      splay(y);
      return y;
    }
    LL popKth(LL k) {             //弹出第k大数
      int o = root;
      while (1) {
        if (siz[son[o][0]] >= k) {
          o = son[o][0];
        } else {
          k -= siz[son[o][0]];
          if (k <= r[o] - l[o]) {
            if (k != r[o] - l[o]) splitNode(o, k);
            if (k != 1) o = splitNode(o, k - 1);
            break;
          } else {
            k -= r[o] - l[o];
            o = son[o][1];
          }
        }
      }
      splay(o);
      fa[son[o][0]] = fa[son[o][1]] = 0;
      if (!son[o][0]) {           //splay删除
        root = son[o][1];
      } else {
        int t = son[o][0];
        while (son[t][1]) t = son[t][1];
        splay(t);
        upd(root = fa[son[t][1] = son[o][1]] = t);
      }
      return l[o];
    }
    void pushBack(LL k) {         //尾部插入数k
      int y = newNode(k, k + 1);
      if (!root) {
        root = y;
      } else {
        int o = root;
        while (son[o][1]) o = son[o][1];
        splay(o);
        upd(fa[son[o][1] = y] = o);
      }
    }
  };
  Splay s[N];
  void main() {
    cnt = 0;
    int n, m, q;
    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));
      printf("%lld\n", p = s[x].popKth(y));
      s[0].pushBack(p);
    }
  }
};
int main() {
  rqy::main();
  return 0;
}

评论

  • sqrt(3B)
    还没有评论
  • jiuguaiwf
    %%%
  • 张曜玺
    写下你的评论......
  • ___new2zy___
    %%%
  • ___new2zy___
    神仙
  • 幸济蒸馒头
    写下你的评论...
  • 枉却东风
    怎么算动态开点的内存阿QAQ
  • Capella
    您的初始化方法学习了
  • ZXZ695
    同问:怎么算动态开点的空间
  • vanilla
    %%%
作者: Tgotp  更新时间: 2017-11-22 19:05  在Ta的博客查看 举报    76  

观察发现每次变动有影响的点只有当前点,最后一行最后一列的点以及当前这一行的最后一个点。

所以可以用一个支持单点修改的线段树,建立n + 1棵,前n棵代表第n行前m - 1个答案,第n+1棵表示最后一列。

每次操作将当前点(x,y)记录输出并删除,然后加入第n+1的最后一个位置,然后把第n+1棵的x位置记录加入到第x行的最后一个位置,

注意如果x本身就在最后一列就不用管。

考虑q的范围,即最多有q个点加入,那么线段树的长度最长为 max(n,m) + q.

而n,m,q,的范围均在3e5的范围,所以需要动态开点,所以内存最多只有 3 * log n *q ,搞定

蒟蒻noip题解传送门

c++代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define rep(i,x,y) for(register int i = x;i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ;i >= y; -- i)
#define abs(x) (x > 0 ? x : - (x))
using namespace std;
typedef long long ll;
template<class T>inline bool chkmax(T&x,T y) { return x < y ? x = y,1 : 0; }
template<class T>inline bool chkmin(T&x,T y) { return x > y ? x = y,1 : 0; }
template<typename T>inline void read(T&x)
{
    x = 0;char c;int sign = 1;
    do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c > '9');
    do { x = x * 10 + c - '0'; c = getchar();  }while(c <= '9' && c >= '0');
    x *= sign;
}
inline void init(string name )
{
    string in = name + ".in",out = name + ".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
const int N = 3e5 + 500,M = 1e7;
int n,m,now,o[N],q,root[N],SZ,sz[M],ls[M],rs[M];ll val[M];
inline int get_sz(int l,int r)
{
    if(now == n + 1)
    {
        if(r <= n) return r - l + 1;
        if(l <= n) return n - l + 1;
        return 0;
    }
    if(r < m) return r - l + 1;
    if(l < m) return m - l ;
    return 0;
}
ll query(int&id,int x,int l,int r)
{
    if(!id)
    {
        id = ++SZ;
        sz[id] = get_sz(l,r);
        if(l == r)
        {
            if(now <= n) val[id] = (ll)(now - 1) * m + l;
            else val[id] = (ll)l * m;
        }
    }
    sz[id]--;
    if(l == r) return val[id];
    int mid = (l + r) >> 1;
    if((!ls[id] && x <= (mid - l + 1)) || x <= sz[ls[id]]) return query(ls[id],x,l,mid);
    else
    {
        if(!ls[id]) x -= (mid - l + 1); else x -= sz[ls[id]];
        return query(rs[id],x,mid + 1,r);
    }
}
void update(int&id,int x,ll w,int l,int r)
{
    if(!id)
    {
        id = ++SZ;
        sz[id] = get_sz(l,r);
        if(l == r) val[id] = w;
    }
    sz[id]++;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) update(ls[id],x,w,l,mid);
    else update(rs[id],x,w,mid + 1,r);
}
int main()
{
    init("phalanx");
    int x,y;
    read(n); read(m); read(q);
    int p = max(m,n) + q ;ll z;
    rep(i,1,q)
    {
        read(x);read(y);
        if(y == m) now = n + 1,z = query(root[now],x,1,p);
        else now = x,z = query(root[now],y,1,p);
        printf("%lld\n",z);
        now = n + 1;update(root[n + 1],n + ( ++o[n+1] ),z,1,p); 
        if(y != m)
        {
            now = n + 1;z = query(root[now],x,1,p);
            now = x;update(root[x],m - 1 + ( ++o[x] ),z,1,p);
        }
    }
    return 0;
}

评论

  • March_H
    Orzzzzzzzzzzzzzzzzzzzzzzzzz
  • March_H
    大佬sum数组是干嘛的啊啊啊啊
  • CK6100LGEV2
    每个节点的sum表示这个区间有多少个人已经进行过离队操作了。
  • March_H
    哦哦哦哦谢谢
  • 辣鸡z蒟蒻
    35行dalaoOrz
  • Jelly_Goat
    戏路很清晰,可惜压行严重
  • Ameiyo
    我是第一次见到如此工整美观的代码,虽然有压行,但是好看就行,不是吗
  • tan_gent
    算法1好像沒那麼高哎
  • tan_gent
    不不不,我錯了,我拿到50了
  • LZDQ
    这么短的程序为什么不排更前一点
作者: CK6100LGEV2 更新时间: 2018-08-11 12:11  在Ta的博客查看 举报    33  

前言

noip2017的时候我连线段树都不会,树状数组也只会板子,而且当时因为肛T2时间太多连50分都没写,30分就跑路了。现在回来看这个题,真的是一言难尽啊。

算法1

对于前50%的数据,我们取出所有询问用到的行和最后一列进行暴力模拟即可。

期望得分:50

算法2

对于11-16测试点,我们开1/2棵线段树,维护每个区间实际存在的数字个数,这样就可以利用区间长度-sum[x]的方法找到区间的第k个元素,同时我们维护1/2个vector,表示添加到末尾的数字,如果查找到的pos是在实际范围以内,那么直接按照pos计算,否则我们在vector中按照下标查找,之后再更新vector和线段树即可。

注意:线段树维护的是1~n+q/m+q的区间,所以空间记得开大一倍。

算法3

对每一行和最后一列维护n+1棵线段树和n+1个vector,由于动态开点我们的内存能够控制在$nlogn$的级别,vector中的元素在$2q$级别,不会超出内存限制,剩下的就按照算法2进行就行了,注意如果$y=m$,就不用对第x行的线段树进行操作了,否则我们就先在第x行找到答案,然后在第n+1棵线段树中找到第x个元素并添加到x中,然后把ans添加到n+1中。

算法3代码

其实这道题代码还是很好写的,35行,不到1K的长度。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q,x,y,pos,tot,lim,rt[300005],ls[12000005],rs[12000005],sm[12000005];vector<ll>v[300005];
int que(int x,int l,int r,int v)
{
    if(l==r) return l;
    int mid=(l+r)>>1,tmp=mid-l+1-sm[ls[x]];
    if(v<=tmp) return que(ls[x],l,mid,v);
    return que(rs[x],mid+1,r,v-tmp);
}
void upd(int &x,int l,int r,int p)
{
    if(!x) x=++tot;sm[x]++;
    if(l==r) return;int mid=(l+r)>>1;
    if(p<=mid) upd(ls[x],l,mid,p);
    else upd(rs[x],mid+1,r,p);
}
ll wk1(int x,ll y)
{
    pos=que(rt[n+1],1,lim,x);upd(rt[n+1],1,lim,pos);
    ll ans=pos<=n?1ll*pos*m:v[n+1][pos-n-1];
    return v[n+1].push_back(y?y:ans),ans;
}
ll wk2(int x,int y)
{
    pos=que(rt[x],1,lim,y);upd(rt[x],1,lim,pos);
    ll ans=pos<m?1ll*(x-1)*m+pos:v[x][pos-m];
    return v[x].push_back(wk1(x,ans)),ans;
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);lim=max(n,m)+q;
    for(;q--;printf("%lld\n",y==m?wk1(x,0):wk2(x,y))) scanf("%d%d",&x,&y);
}

评论

  • OI_lover
    %%%%%%%%%%%%%%%
  • 天秀
    在这里十分感谢勤劳的管理员啊,另外祝大家2018noip rp++,挺进NOI2019
  • 太过年轻ya
    @天秀 mc友军发来贺电
  • zyh2333
    就要NOIP了大佬还能发题解
  • zyh2333
    4楼
  • 咯咯咯
    %%%%我也是动态开点线段树
  • 张鑫杰
    luogu没有小姐姐qwq
  • Sakura_梦瑶
    有呀
  • plysc
    。。。。。。。。。
  • FruitCandy
    变量iakioi是什么鬼?!
作者: 天秀 更新时间: 2018-11-08 15:00  在Ta的博客查看 举报    36  

离noip只有一天了,我终于搞懂了线段树的骚操作,为了加深理解以及帮助一下和我之前一样不会平衡树(其实我会一点)但却看不懂线段树的思路的小可爱们,当然,不会有人和我一样菜的

下面讲一讲思路,主要参考@ Sakura_梦瑶 大佬的 根据线段树二分的性质来维护一个序列是十分方便的,像这类有主席树和动态点开线段树,这里我使用的是动态点开线段树(其实在这之前我都不知道有这玩意儿)。

然而,我skyshow境泽就是死,就是从这跳下去也不用动态,这辈子都不用vector,所以,我选择使用以静态来模拟动态,我们用n+1棵线段树来分别维护n行的前m-1列,第n+1棵来维护第m列,这样,就可以了,然而值得指出的是,这里所构建的线段树不同于像打的板子一样的那种(当然,有人也许一开始就打的板子和我的不一样),这一点我耗费了很长时间才弄懂。

下面是代码,先发我最开始写错的(惊喜吧!)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
long long stree[666666];
long long cnt;
long long n,m,q;
long long us[6666666];
long long num[6666666];
long long num1;
long long x,y;
long long lson[6666666];
long long rson[6666666];
long long sum[666666];
long long doa;
bool flag;
void insert(long long &pos,long long l,long long r,long long k,long long th){
    if(!pos){
        pos=++cnt;
    }
    if(l==r){
        num[pos]=k;
        return;
    }
    long long mid=l+r>>1;
    long long cur=(mid-l+1);
    if(cur>=th){
        insert(lson[pos],l,mid,k,th);
    }
    else insert(rson[pos],mid+1,r,k,th-cur);
}
void find_th(long long &pos,long long l,long long r,long long th){
    if(!pos){
        pos=++cnt;
        }
    us[pos]++;
    if(l==r){
        if(num[pos]){
            num1=num[pos];
        }
        else if(flag){
            num1=(x-1)*m+l;
        }
        else{
            num1=l*m;
        }
        return;
    }
    long long mid=l+r>>1;
    long long cur=(mid-l+1)-us[lson[pos]];
    if(cur>=th){
        find_th(lson[pos],l,mid,th);
    }
    else find_th(rson[pos],mid+1,r,th-cur);
    return;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(long long iakioi=1;iakioi<=q;iakioi++){
        scanf("%lld%lld",&x,&y);
        if(y==m){
            flag=0;
            //printf("%lld %lld\n",x,y);
            find_th(stree[n+1],1,n+q,x);
            printf("%lld\n",num1);
            long long th=++sum[n+1];
            insert(stree[n+1],1,n+q,num1,n+th);
        }
        else{
            flag=1;
            find_th(stree[x],1,m+q,y);
            printf("%lld\n",num1);
            doa=num1;
            y=m;
            find_th(stree[n+1],1,n+q,x);
            long long th=++sum[x];
            insert(stree[x],1,m+q,num1,m+th);
            th=++sum[n+1];
            insert(stree[n+1],1,n+q,doa,n+th);
        }
    }
    return 0;
}

为什么我要先发一波错误代码呢?,其实不是想坑人什么的,是想提醒大家细节真的超重要,对比代码要来了,你们留意一下区别,详细注释也在下面

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
long long stree[666666];//这里不是指线段树,而是那几颗线段树的初始根节点
long long cnt;//线段树节点
long long n,m,q;
long long us[6666666];
long long num[6666666];//66666666什么的,不要在意啦
long long num1;
long long x,y;
long long lson[6666666];//左子树根节点
long long rson[6666666];//右子树根节点
long long sum[666666];//当前线段树扩展的节点数
long long doa;//辅助储存功能
bool flag;//分辨是否是前m-1行的
void insert(long long &pos,long long l,long long r,long long k,long long th){//注意&符号
    if(!pos){
        pos=++cnt;//-》当前节点编号
    }
    if(l==r){
        num[pos]=k;
        return;
    }
    long long mid=l+r>>1;
    long long cur=(mid-l+1);
    if(cur>=th){//不懂先看主程序
        insert(lson[pos],l,mid,k,th);
    }
    else insert(rson[pos],mid+1,r,k,th-cur);
}
void find_th(long long &pos,long long l,long long r,long long th){//注意&符号
    if(!pos){
        pos=++cnt;
        }
    us[pos]++;//表示这一段中有多少节点出队列,这样就可以维护了,想一想为什么(l==r时被确定了,所以不用担心)
    if(l==r){
        if(num[pos]){
            num1=num[pos];
        }
        else if(flag){//flag为真表示在前m-1列
            num1=(x-1)*m+l;//这里很显然是l
        }
        else{
            num1=l*m;
        }
        return;
    }
    long long mid=l+r>>1;
    long long cur=(mid-l+1)-us[lson[pos]];
    if(cur>=th){
        find_th(lson[pos],l,mid,th);
    }
    else find_th(rson[pos],mid+1,r,th-cur);
    return;
}
int main(){//从主程序开始看代码是个好习惯
    scanf("%lld%lld%lld",&n,&m,&q);
    for(long long iakioi=1;iakioi<=q;iakioi++){//皮这一下,开森
        scanf("%lld%lld",&x,&y);
        if(y==m){
            flag=0;
            //printf("%lld %lld\n",x,y);
            find_th(stree[n+1],1,n+q,x);
            printf("%lld\n",num1);
            long long th=++sum[n+1];
            insert(stree[n+1],1,n+q,num1,n+th);
        }
        else{
            flag=1;
            find_th(stree[x],1,m+q-1,y);
            printf("%lld\n",num1);
            doa=num1;
            y=m;
            flag=0;
            find_th(stree[n+1],1,n+q,x);
            long long th=++sum[x];
            insert(stree[x],1,m+q-1,num1,m+th-1);//注意这里是m-1+q和m+th-1,血的教训
            th=++sum[n+1];
            insert(stree[n+1],1,n+q,doa,n+th);
        }
    }
    return 0;
}

另外,建议在考场上没有很大自信的话就不要强求正解,不然一个细节就爆零了很吃亏,我调了一上午,无数次怀疑自己写错了,最后睡了个午觉才发现(睡午觉有益身心健康)。

再看不懂的可以私信我,但一定要指出哪里不懂

另外求管理员能在10号之前过审核啊,您最帅了(不会是小姐姐吧)

评论

  • 颜伟业_C_Asm
    %%%
  • BriMon
    式子炸了
  • wzhy
    %%%
  • Chaos1018
    %%%
  • plysc
    %%%
  • Freddie
    为什么 N*20 可以存 N*N
  • 神奇的呆子
    真的好啊
  • 神奇的呆子
    signed main什么意思
  • S20外环隧道
    #define int long long海星
  • 关怀他人
    @Fredddie因为平衡树的空间是Nlog(N)啊
作者: YoungNeal 更新时间: 2018-05-20 16:22  在Ta的博客查看 举报    30  

题解在博客食用效果更佳哦~

Solution

$fhq\_Treap$ 了解一下


算法部分

这题不管怎么做直接存每个人都会炸,所以我们用 $Treap$ 维护区间,即 $Treap$ 上的每个节点代表的是一个区间。

对于每行从第 $1$ 列到第 $m-1$ 列维护一个 $Treap$。

对于最后一列我们单独维护一个 $Treap$ 。

如果 $(x,y)$ 出队,要分两种情况讨论,第一种 $y=m$,即出队的人在最后一列的情况,如果不讨论的话我们在每行维护的 $Treap$ 上是找不到这个点的,因此需要分类。
对于这种情况,我们直接在最后一列的 $Treap$ 中找到第 $x$ 个人,把它 $split$ 出来,然后 $merge$ 到结尾即可。

(关于如何 $split$ 和 $merge$ 下面有讲)

第二种 $y\neq m$。
对于这种情况,我们需要在第 $x$ 行的那个 $Treap$ 中找到第 $y$ 个点,把它 $split$ 出来记为点 $a$,同时在最后一列的 $Treap$ 中找到第 $x$ 个点,同样 $split$ 出来记为点 $b$ 。
之后把点 $b$ 合并到第 $x$ 行 $Treap$ 的最后一个节点,把点 $a$ 合并到最后一列的 $Treap$ 的最后一个节点即可。


实现部分

这题 $fhq\_Treap$ 难实现的地方就在如何 $split$ 出一个不存在的节点(因为我们维护的一直是区间,而这题里 $split$ 要做的就是在一个大区间的基础上 $split$ 出两个新的小区间)

如何处理呢?

仿照一般 $fhq\_Treap$ 的 $split$ 操作,我们定义

split(int now,int k,int &x,int &y)

表示在以 $now$ 为根的子树中进行分离,分离出的左子树大小为 $k$,根节点为 $x$,分离出的右子树根节点为 $y$ (我们并不能知道右子树的大小是多少)。

这时我们就要分情况讨论了:

如果 $now$ 的左子树的大小已经大于了 $k$,那么我们就不用把 $now$ 这个点拆开而是递归进入 $now$ 的左子树进行处理。

否则我们就要进行麻烦的裂点操作了。

因为要在以 $now$ 为根的子树中分出 $k$ 个,所以我们要从 $now$ 和 $now$ 的右子树里分出 $k-sze[ch[now][0]]$ 个。

这里又要分情况讨论:

如果 $now$ 这个点维护的区间大小不小于 $k$ 的话,从 $now$ 里分出大小为 $k-sze[ch[now][0]]$ 的区间即可(因为左子树已经有了 $sze[ch[now][0]]$ 那么多)。

否则就要调用

split(ch[now][1],k-sze[ch[now][0]]-(r[now]-l[now]+1),ch[now][1],y)

这个意思是,把 $now$ 这个点的区间全部给了左子树还是不够,所以要进入右子树分剩下的大小为 $k-sze[ch[now][0]]-(r[now]-l[now]+1)$ 的区间。

但是实际写代码的时候不必要那么复杂的分类讨论。因为如果 $split$ 传进去的 $k$ 是非正整数的话(对应第一种情况),那么递归会一直进入左子树,相反对于第二种情况,在分裂新节点的时候判一下就可以了,大概长这样。

void split_new(int now,int k){
    if(k>=r[now]-l[now]+1) return;
    ...
}

Code

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define N 300005
#define int long long

int root[N];
int n,m,T,tot;
int ch[N*20][2];
int l[N*20],r[N*20];
int sze[N*20],prio[N*20];

int newnode(int x,int y){
    tot++;
    l[tot]=x;
    r[tot]=y;
    sze[tot]=y-x+1;
    prio[tot]=rand();
    return tot;
}

void pushup(int x){
    sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+r[x]-l[x]+1;
}

int merge(int x,int y){
    if(!x or !y) return x+y;
    if(prio[x]<prio[y]){
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    }
    else{
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }
}

void split_new(int now,int k){//把now的大小变为k
    if(k>=r[now]-l[now]+1) return;
    int want=l[now]+k-1;
    int nn=newnode(want+1,r[now]);
    r[now]=want;
    ch[now][1]=merge(nn,ch[now][1]);
    pushup(now);
}

void split(int now,int k,int &x,int &y){
    if(!now) x=y=0;
    else{
        if(sze[ch[now][0]]>=k){
            y=now;
            split(ch[now][0],k,x,ch[now][0]);
        }
        else{
            split_new(now,k-sze[ch[now][0]]);
            x=now;
            split(ch[now][1],k-sze[ch[now][0]]-(r[now]-l[now]+1),ch[now][1],y);
        }
        pushup(now);
    }
}

signed main(){
    srand(time(0));
    scanf("%lld%lld%lld",&n,&m,&T);
    for(int i=1;i<=n;i++)
        root[i]=newnode((i-1)*m+1,i*m-1);
    for(int i=1;i<=n;i++)
        root[n+1]=merge(root[n+1],newnode(i*m,i*m));
    while(T--){
        int a,b;
        scanf("%lld%lld",&a,&b);
        if(b!=m){
            int x,y,z;
            split(root[a],b,x,y);
            split(x,b-1,x,z);
            printf("%lld\n",l[z]);
            int x1,y1,z1;
            split(root[n+1],a,x1,y1);
            split(x1,a-1,x1,z1);
            root[a]=merge(x,merge(y,z1));
            root[n+1]=merge(x1,merge(y1,z));
        }
        else{
            int x,y,z;
            split(root[n+1],a,x,y);
            split(x,a-1,x,z);
            printf("%lld\n",l[z]);
            root[n+1]=merge(x,merge(y,z));
        }
    }
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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