【题解】P4278 带插入区间K小值

ExplodingKonjac · 2021-08-30 17:51:07 · 题解

【原题链接】

大力块状链表套权值线段树

这题整整搞了两天，太毒瘤了。（真心感觉伏特太难了）

线段树套平衡树和平衡树套线段树的做法都有想过，但是不会写 qwq。最后瞄了一眼标签，决定使用块状链表套权值线段树。

思路相当的暴力：块状链表搞插入操作，每个块开一个权值线段树，查询时拎出完整块的跟，对于不完整的块加到一个临时的树里面。查询时一起查。

（什么？值域分块？？不会！）

当然这样的做法是 O(n\sqrt{n}\log n) 的，在数据 7e4 的范围下相当危，但是毕竟是可以卡常卡过去的。下面说几种优化：

手动设置块长

因为我们的临时树是需要每次清空的，所以零散块的影响会更大一些。我们考虑缩短块长。

经过实验，块长 65 最优。别问为什么，问就是和另一个同学一共长达 3 页的提交。

找对应块时分方向

由于我们的块是一个链表，无法 O(1) 定位某一位置 p 所在的块，只能暴力找。

考虑改成双向链表，当 p\le n/2 时从左往右找，当 p>n/2 时从右往左找。

使用快读快写

你可以将快读快写升级为超级快读快写，也就是给快读快写分别写一个 char 类型数组 buf 作为缓存区。输出时先放到缓存里，如果缓存满了就用玄学的 fwrite 全部输出，然后清空缓存。输入的话可以先用 fread 将缓存填满，然后一个个从 buf 里拿，buf 空了就再填一次。

当然别忘了在程序结束时清空输出的缓存。

【广告】我写的快读快写类（在这题快读开启缓存会莫名其妙 TLE）

你那么聪明，肯定有其它的优化方法

用完上面的方法后，我已经卡过时限了，所以就不介绍其它方法了。

代码实现

由于以前没写过块状链表，写法可能与正常写法不太一样，见谅。

#include <bits/stdc++.h>
using namespace std;

/*
省略80多行的快读快写模板
也就是代码里用的qin、qout
*/

int n,m,size=65;
struct TreeNode
{
    int val;
    int lc,rc;
}t[20000005];
int cnt,rubbish[20000005],top;
inline int newNode()
    { return top?rubbish[top--]:++cnt; }
inline void deleteNode(int &i)
    { rubbish[++top]=i,t[i].lc=t[i].rc=t[i].val=0,i=0; }
void destroy(int &i)
    { if(i)destroy(t[i].lc),destroy(t[i].rc),deleteNode(i); }
void add(int p,int &i,int l=0,int r=70000)
{
    if(!i)  i=newNode();
    t[i].val++;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        if(mid>=p)  add(p,t[i].lc,l,mid);
        else    add(p,t[i].rc,mid+1,r);
    }
}
void sub(int p,int &i,int l=0,int r=70000)
{
    t[i].val--;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        if(mid>=p)  sub(p,t[i].lc,l,mid);
        else    sub(p,t[i].rc,mid+1,r);
    }
    if(!t[i].val)   deleteNode(i);
}
struct Block
{
    int *b,cnt,rt;
    Block *nxt,*pre;
    Block(Block *p): cnt(0),rt(0),pre(p)
        { b=new int[size+5],nxt=nullptr; }
    inline bool full()
        { return cnt==size; }
}*head,*tail;
void build(Block *&i,int pos=1,Block *last=nullptr)
{
    i=new Block(last);
    int x;
    while(!i->full() && pos<=n)
        qin>>x,i->b[++i->cnt]=x,add(x,i->rt),pos++;
    if(pos<=n)  build(i->nxt,pos,i);
    else    tail=i;
}
Block *find(int &x)
{
    Block *i;
    if(x<=(n>>1))
        for(i=head;i->cnt<x;x-=i->cnt,i=i->nxt);
    else
    {
        x=n-x+1;
        for(i=tail;i->cnt<x;x-=i->cnt,i=i->pre);
        x=i->cnt-x+1;
    }
    return i;
}
int ans,tot,rt[200005];
int main()
{
    // freopen("P4278.in","r",stdin);
    // freopen("P4278.out","w",stdout);
    qin>>n,build(head);
    qin>>m;
    while(m--)
    {
        char opt;
        while((opt=getchar())<33);
        int x,y,z;
        qin>>x>>y,x^=ans,y^=ans;
        if(opt=='Q')
        {
            Block *a=find(x),*b=find(y);
            qin>>z,z^=ans,tot=rt[0]=0;
            if(a==b)
                for(int i=x;i<=y;i++)   add(a->b[i],rt[0]);
            else
            {
                for(int i=x;i<=a->cnt;i++)  add(a->b[i],rt[0]);
                for(int i=1;i<=y;i++)   add(b->b[i],rt[0]);
                for(;a->nxt!=b;a=a->nxt,rt[++tot]=a->rt);
            }
            int oldrt=rt[0],l=0,r=70000;
            while(l<r)
            {
                int sz=0,mid=(l+r)>>1;
                for(int i=0;i<=tot;i++) sz+=t[t[rt[i]].lc].val;
                if(sz>=z)
                {
                    r=mid;
                    for(int i=0;i<=tot;i++) rt[i]=t[rt[i]].lc;
                }
                else
                {
                    l=mid+1,z-=sz;
                    for(int i=0;i<=tot;i++) rt[i]=t[rt[i]].rc;
                }
            }
            qout.writeln(ans=l),destroy(oldrt);
        }
        else if(opt=='M')
        {
            Block *i=find(x);
            sub(i->b[x],i->rt),add(i->b[x]=y,i->rt);
        }
        else if(opt=='I')
        {
            Block *i,*j;
            if(x==n+1)
            {
                i=find(--x),x++;
                if(i->full())
                    i->nxt=new Block(i),i=i->nxt,tail=i,x=1;
            }
            else    i=find(x);
            if(i->full())
            {
                j=i->nxt;
                if(!j || j->full())
                {
                    i->nxt=new Block(i),i->nxt->nxt=j;
                    if(j)   j->pre=i->nxt;
                    else    tail=i->nxt;
                    j=i->nxt;
                }
                for(int k=++j->cnt;k>1;k--) j->b[k]=j->b[k-1];
                j->b[1]=i->b[size];
                add(j->b[1],j->rt),sub(i->b[size],i->rt);
                for(int k=size;k>x;k--) i->b[k]=i->b[k-1];
            }
            else
                for(int k=++i->cnt;k>x;k--) i->b[k]=i->b[k-1];
            i->b[x]=y,add(y,i->rt),n++;
        }
    }
    return qout.flush(),0;
}