题解：P4278 带插入区间K小值

Little_Fox_Fairy · 2024-09-06 21:28:04 · 题解

前言：写了将近五个小时 。

如果做过 最初分块 的话，这道题还算挺好想的吧。

操作一：区间第 K 小。

序列分块加值域分块。

具体的，我们记录一个 sums 数组和 sumc 数组。 sums[i][j] 表示在前 i 个序列块中有多少个数 j 。 sumc[i][j] 表示在前 i 个序列块中有多少个数在值域的第 j 块当中。

然后对于散块，我们记录同样作用的 s 数组和 c 数组，不过只是对于散块的统计。

查询就是扫一遍值域块，用 sumc 和 c 数组来确定第 k 大在哪个值域块中。然后扫一遍答案所在的那个值域块，用 sums 数组和 s 数组就可以找到答案了。

值域毕竟只有 7 \times 10^4 ，所以这个数组还是开得下的。

操作二：单点修改

这个就很好做了，对于我们要修改的那个点，先找到那个点所在的块，然后修改这个块以及后面块的 sums 数组和 sumc 数组就好了。

操作三：插入

由于有插入操作，那我们的序列分块就只能变为块状链表了。

块状链表，顾名思义，就是用链表穿起来的分块。

对于每一个块，还是维护三个：块内的值， sums 数组，和 sumc 数组。

但是要是一直在一个块内插入时间复杂度肯定会爆炸。所以要有一个分裂操作。

即当一个块的长度大于二倍块长时，我们就要将它分裂为两个块。分裂的时候就把信息拷贝一下，然后删去重复的，就做完了。

Code：

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;             //快读优化。
const int N=1e5+10;
const int C=350;
const int S=350;
struct Block
{
    vector<int> a;
    int lft=-1,rght=-1;
    int sums[N],sumc[C];
};
int n,m;
int limit=300,blo;
int bel[N],t[N];
int s[N],c[C],lst;
int T;
vector<Block> e;
Block tmp;
inline void init()
{
    bel[0]=1;for (int i=1;i<=1e5;i++) bel[i]=(i-1)/S+1;
    return ;
}                 //预处理值域块。
inline void split(int loc)
{
    tmp=e[loc];
    e.emplace_back(tmp);blo++;
    e[blo].lft=loc,e[blo].rght=e[loc].rght;
    if (e[loc].rght!=-1) e[e[loc].rght].lft=blo;
    e[loc].rght=blo;
    e[loc].a.erase(e[loc].a.begin()+limit,e[loc].a.end());
    e[e[loc].rght].a.erase(e[e[loc].rght].a.begin(),e[e[loc].rght].a.begin()+limit);
    for (auto v : e[e[loc].rght].a) e[loc].sums[v]--,e[loc].sumc[bel[v]]--;
    return ;
}             //块链的分裂操作。
inline void emplace(int pos,int x)     //插入。
{
    int loc=0;
//  if (pos==m+1)
//  {
//      e[blo].a.emplace_back(x);
//      loc=blo;
//  }
//  else
//  {
//      while (e[loc].a.size()<pos)
//      {
//          pos-=e[loc].a.size();
//          loc=e[loc].rght;
//          if (loc==-1) break;
//      }
//      pos--;
//      e[loc].a.emplace(e[loc].a.begin()+pos,x);
//  }                   //注意这里注释掉的做法是错的，有可能插入到最后一个数后面。
    while (e[loc].a.size()<pos)
    {
        pos-=e[loc].a.size();
        if (e[loc].rght==-1 and pos)
        {
            pos=e[loc].a.size()+1;
            break;
        }            //在这里特判一下。
        loc=e[loc].rght;
    }
    pos--;
    e[loc].a.emplace(e[loc].a.begin()+pos,x);
    for (int i=loc;i!=-1;i=e[i].rght) e[i].sums[x]++,e[i].sumc[bel[x]]++;
    if (e[loc].a.size()>(limit<<1)) split(loc);
    return ;
}
inline void update(int pos,int x)       //单点修改。
{
    int loc=0;
    while (e[loc].a.size()<pos)
    {
        pos-=e[loc].a.size();
        loc=e[loc].rght;
        if (loc==-1) break;
    }
    pos--;
    int pst=e[loc].a[pos];
    e[loc].sums[pst]--,e[loc].sumc[bel[pst]]--;
    e[loc].sums[x]++,e[loc].sumc[bel[x]]++;
    e[loc].a[pos]=x;
    for (int i=e[loc].rght;i!=-1;i=e[i].rght) e[i].sums[pst]--,e[i].sumc[bel[pst]]--,e[i].sums[x]++,e[i].sumc[bel[x]]++;
    return ;
}
inline int query(int l,int r,int k)   //查询区间第k大。
{
    int bll=0;
    while (e[bll].a.size()<l)
    {
        l-=e[bll].a.size();
        bll=e[bll].rght;
        if (bll==-1) break;
    }
    l--;
    int blr=0;
    while (e[blr].a.size()<r)
    {
        r-=e[blr].a.size();
        blr=e[blr].rght;
        if (blr==-1) break;
    }
    r--;
    if (bll==blr)
    {
        for (int i=l;i<=r;i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
        int siz=0,ll,rr;
        for (int i=1;i<=C;i++)
        {
            siz+=c[i];
            if (siz>=k)
            {
                siz-=c[i];
                ll=(i-1)*S+1;
                if (i==1) ll=0;
                rr=i*S;
                break;
            }
        }
        int ans=0;
        for (int i=ll;i<=rr;i++)
        {
            siz+=s[i];
            if (siz>=k)
            {
                ans=i;
                break;
            }
        }
        for (int i=l;i<=r;i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
        return ans;
    }
    if (e[blr].lft==-1) exit(0);
    for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]++,c[bel[e[bll].a[i]]]++;
    for (int i=0;i<=r;i++) s[e[blr].a[i]]++,c[bel[e[blr].a[i]]]++;
    int siz=0,ll,rr;
    for (int i=1;i<=C;i++)
    {
        siz+=(c[i]+e[e[blr].lft].sumc[i]-e[bll].sumc[i]);
        if (siz>=k)
        {
            siz-=(c[i]+e[e[blr].lft].sumc[i]-e[bll].sumc[i]);
            ll=(i-1)*S+1;
            if (i==1) ll=0;
            rr=i*S;
            break;
        }
    }
    int ans=0;
    for (int i=ll;i<=rr;i++)
    {
        siz+=(s[i]+e[e[blr].lft].sums[i]-e[bll].sums[i]);
        if (siz>=k)
        {
            ans=i;
            break;
        }
    }
    for (int i=l;i<e[bll].a.size();i++) s[e[bll].a[i]]--,c[bel[e[bll].a[i]]]--;
    for (int i=0;i<=r;i++) s[e[blr].a[i]]--,c[bel[e[blr].a[i]]]--;
    return ans;
}
inline void calc()   //对于原序列的块链处理。
{
    e.emplace_back();
    for (int i=1;i<=n;i++)
    {
        e[blo].a.emplace_back(t[i]);
        e[blo].sums[t[i]]++;
        e[blo].sumc[bel[t[i]]]++;
        if (e[blo].a.size()>(limit<<1)) split(blo);
    }
    m=n;
    return ;
}
signed main()
{
    init();
    cin>>n;
    for (int i=1;i<=n;i++) cin>>t[i];
    calc();
    cin>>T;
    while (T--)
    {
        char op;int x,val,l,r,k;
        cin>>op;
        if (op=='Q')
        {
            cin>>l>>r>>k;
            l^=lst,r^=lst,k^=lst;
            lst=query(l,r,k);
            cout<<lst<<endl;
        }
        if (op=='M')
        {
            cin>>x>>val;
            x^=lst,val^=lst;
            update(x,val);
        }
        if (op=='I')
        {
            cin>>x>>val;
            x^=lst,val^=lst;
            emplace(x,val);
            m++;
        }
    }
    return (0-0);
}