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

· · 题解

本文同步发表于窝的个人博客.

简单题,不用卡常.

解题思路

默认n询问,值域同阶.

首先看到待插入考虑平衡树和块状链表.理论上平衡树相关的有\Theta(n\lg^3n)的解法,但是窝不会而且这种解法常数巨大,所以考虑块状链表.

如果做过洛谷P4119 [Ynoi2018]未来日记就会容易地想到在分块里面查第k大会用值域分块,套上去就行了.

修改

没什么好说的,找到所在的块(怎么找后面说),修改之后更新值域分块的前缀和即可.

查询

值 域 分 块.

插入

就和块状链表的一样,放进去就行.

块状链表

好吧主要的难点就在这里.块状链表大概是长成这个样子的

譬如窝要在E后面插入一个J,那就将同一块里面的F往后移一位,然后把J放进去就行了,复杂度是\Theta(块长)的.像这样

如果再接着在J后面插入一个K和一个L,就分别是

但是这时候发现如果窝们一直在同一块里面插,那块长就会达到n,再插入时复杂度就太高了,所以当块长达到2\sqrt n时要将这个块拆成两个\sqrt n的小块,就像这样

当然实际上的小块并不是在中间,而是在最后面,通过维护左右两边的块来连成一个链表,所以叫块状链表.至于具体找某个块,就直接沿着链表依次找过去即可,因为最多新建\sqrt n个块,所以复杂度仍然是\sqrt n.

具体到这道题,那窝们就要将原来的块(会变成前一个小块)的前缀和信息复制到后面的小块,然后将原来大块的后\sqrt n个数放进后面小块,并在前面的块的前缀和信息减去.

/*复制前缀和信息*/
for (int j=0;j<q;++j) b[cnt].sbk[j]=s->sbk[j];
for (int j=0;j<70001;++j) b[cnt].snm[j]=s->snm[j];
/*减去放到后面的小块的数的前缀和信息*/
for (int j=0;j<q;++j) {
    b[cnt][j]=s->a[j+q];
    --(s->sbk[p[b[cnt][j]]]);
    --(s->snm[b[cnt][j]]);
}
/*维护剩下相关内容*/

复杂度分析

查询和修改显然都是\Theta(\sqrt n)的(和未来日记类似),插入可以看到复制前缀和信息是单次\Theta(n)的,但是最多会建\sqrt n个新块,所以总体上仍然是\Theta(\sqrt n).

并且这道题不像Ynoi那么毒瘤,不用调块长,直接取\lceil\sqrt{70000}\rceil=265即可,但是要记得数组要开到265^2=70225.

Code

没什么好说的,注意细节.另外建议把块长调到3左右跑样例,能过再调回265交.

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

#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048577,stdin),p0==p1)?EOF:*p0++)

const int q=265;

int cnt,p[70505];
char buf[1048577],*p0,*p1;
struct bxt {
    int lps,rps,siz;
    int a[545],sbk[545],snm[70505];
    bxt *lbk,*rbk;
    int& operator [] (const int p) {
        return a[p];
    }
} b[545],fir,lst;

inline int read() {
    int re=0; char ch=gc();
    while (ch<48||ch>57) ch=gc();
    while (ch>47&&ch<58) {
        re=(re<<3)+(re<<1)+(ch^48);
        ch=gc();
    }
    return re;
}

inline int ropt() {
    char ch;
    while (true) switch (ch=gc()) {
        case 81: return 0;
        case 77: return 1;
        case 73: return 2;
        default: break;
    }
}

inline int find_kth(int opl,int opr,int opk) {
    static int fbk[265],fnm[70505];
    int ql=opl,qr=opr,sum=0,ret=-1;
    bxt *pl=NULL,*pr=NULL;
    for (bxt *i=fir.rbk;i;i=i->rbk) {
        if ((!pl)&&i->siz>ql) pl=i;
        else if (!pl) ql-=i->siz;
        if ((!pr)&&i->siz>qr) pr=i;
        else if (!pr) qr-=i->siz;
    }
    if (pl==pr) {
        for (int i=ql;i<=qr;++i) {
            ++fbk[p[pl->a[i]]]; ++fnm[pl->a[i]];
        }
        for (int i=0;i<q;++i)
            if ((sum+=fbk[i])>=opk) {
                for (int j=(i+1)*q-1;;--j)
                    if ((sum-=fnm[j])<opk) {
                        ret=j; break;
                    }
                break;
            }
        for (int i=ql;i<=qr;++i) {
            --fbk[p[pl->a[i]]]; --fnm[pl->a[i]];
        }
        return ret;
    }
    for (int i=ql;i<pl->siz;++i) {
        ++fbk[p[pl->a[i]]]; ++fnm[pl->a[i]];
    }
    for (int i=0;i<=qr;++i) {
        ++fbk[p[pr->a[i]]]; ++fnm[pr->a[i]];
    }
    for (int i=0;i<q;++i)
        if ((sum+=(pr->lbk->sbk[i])-(pl->sbk[i])+fbk[i])>=opk) {
            for (int j=(i+1)*q-1;;--j)
                if ((sum-=(pr->lbk->snm[j])-(pl->snm[j])+fnm[j])<opk) {
                    ret=j; break;
                }
            break;
        }
    for (int i=ql;i<pl->siz;++i) {
        --fbk[p[pl->a[i]]]; --fnm[pl->a[i]];
    }
    for (int i=0;i<=qr;++i) {
        --fbk[p[pr->a[i]]]; --fnm[pr->a[i]];
    }
    return ret;
}

inline void update(int opp,int opx) {
    int w=0,opo=0; bxt *r=fir.rbk;
    for (;r->rps<opp;r=r->rbk) w+=r->siz;
    for (int i=0;i<r->siz;++i) if (w+i==opp)
        {opo=r->a[i]; r->a[i]=opx;}
    for (;r!=&lst;r=r->rbk) {
        --(r->sbk[p[opo]]); --(r->snm[opo]);
        ++(r->sbk[p[opx]]); ++(r->snm[opx]);
    }
}

inline void insert(int opp,int opx) {
    int w=0; bxt *r=fir.rbk,*s;
    for (;r->rps<opp;r=r->rbk) w+=r->siz;
    if (r==&lst) w-=(r=r->lbk)->siz;
    for (int i=0;i<=r->siz;++i) if (w+i==opp) {
        for (int j=r->siz;j>i;--j)
            r->a[j]=r->a[j-1]; r->a[i]=opx;
    }
    ++((s=r)->siz); --(r->lps);
    for (;r!=&lst;r=r->rbk) {
        ++(r->lps); ++(r->rps);
        ++(r->sbk[p[opx]]); ++(r->snm[opx]);
    }
    if (s->siz==(q<<1)) {
        for (int j=0;j<q;++j) b[cnt].sbk[j]=s->sbk[j];
        for (int j=0;j<70001;++j) b[cnt].snm[j]=s->snm[j];
        for (int j=0;j<q;++j) {
            b[cnt][j]=s->a[j+q];
            --(s->sbk[p[b[cnt][j]]]);
            --(s->snm[b[cnt][j]]);
        }
        s->siz=b[cnt].siz=q;
        b[cnt].rps=(s->rps=(b[cnt].lps=s->lps+q)-1)+q;
        b[cnt].lbk=s; b[cnt].rbk=s->rbk;
        s->rbk->lbk=&b[cnt]; s->rbk=&b[cnt]; ++cnt;
    }
}

int main() {
    int n=read(),m,las=0,x,y,z;
    memset(fir.sbk,0x00,sizeof(fir.sbk));
    memset(fir.snm,0x00,sizeof(fir.snm));
    for (int i=0;i<70505;++i) p[i]=i/q;
    for (int i=0;i<n;++i) {
        b[p[i]][i%q]=read();
        ++b[p[i]].siz;
    }
    for (int i=0;i<=p[n-1];++i) {
        b[i].lps=(i?b[i-1].rps+1:0);
        b[i].rps=b[i].lps+b[i].siz-1;
        (b[i].lbk=i?&b[i-1]:&fir)->rbk=&b[i];
        for (int j=0;j<q;++j)
            b[i].sbk[j]+=b[i].lbk->sbk[j];
        for (int j=0;j<70001;++j)
            b[i].snm[j]+=b[i].lbk->snm[j];
        for (int j=0;j<b[i].siz;++j) {
            ++b[i].sbk[p[b[i][j]]];
            ++b[i].snm[b[i][j]];
        }
    }
    b[p[n-1]].rbk=&lst;
    lst.lbk=&b[p[n-1]];
    lst.rps=0x3fffffff;
    cnt=p[n-1]+1; m=read();
    while (m--) {
        z=-1;
        switch (ropt()) {
            case 0:
                x=(read()^las)-1; y=(read()^las)-1;
                z=read()^las;
                printf("%d\n",las=find_kth(x,y,z));
                break;
            case 1:
                x=(read()^las)-1; y=read()^las;
                update(x,y); break;
            case 2:
                x=(read()^las)-1; y=read()^las;
                insert(x,y); break;
            default: break;
        }
    }
    return 0;
}