题解：P5217 贫穷

· · 题解

12356 操作均是简单的，难点在于 4 操作。

这里先给出一个单 \log 的正经文艺平衡树做法。

正常情况下我们写 fhq 会写完 split/merge/pushup/pushdown 之后就不再关心具体实现，而只关心如何使用 split/merge 来达成想要的操作。比如你想要提取出一段区间就对整棵树 split 两次即可。

但是 4 操作在这种视角下及其困难。考虑一些底层实现。比如原来第 x 个字符之后无论如何操作，下标仍然在 x 处。因此我们的目标就是求出树上某个点的 rank。这个是简单的。不过需要先把 tag 推下去。

具体的，我们需要从上往下 pushdown 因此我们还需要维护父亲。

Link.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10,M=2e5+10;
mt19937 rnd(100);
int n,q;
struct node{
    int ls,rs,key,siz,tag,fa;
    int S;
    char ch;
}t[N];
int tot,rt;
int new_node(char ch)
{
    t[++tot]={0,0,rnd(),1,0,0,1ll<<ch-'a',ch};
    return tot;
}
void pu(int x)
{
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
    t[x].S=t[t[x].ls].S|t[t[x].rs].S|(1ll<<t[x].ch-'a');
    t[t[x].ls].fa=x,t[t[x].rs].fa=x;
}
void pd(int x)
{
    if(!t[x].tag)return;
    swap(t[x].ls,t[x].rs);
    t[t[x].ls].tag^=1,t[t[x].rs].tag^=1;
    t[x].tag=0;
}
void split(int x,int p,int &l,int &r)
{
    if(!x){return l=r=0,void();}
    pd(x);
    if(t[t[x].ls].siz<p)
    {
        l=x;
        split(t[x].rs,p-t[t[x].ls].siz-1,t[x].rs,r);
    }else{
        r=x;
        split(t[x].ls,p,l,t[x].ls);
    }
    pu(x);
}
int merge(int l,int r)
{
    if(!l||!r)return l+r;
    pd(l),pd(r);
    if(t[l].key<t[r].key)
    {
        t[l].rs=merge(t[l].rs,r);
        return pu(l),l;
    }else{
        t[r].ls=merge(l,t[r].ls);
        return pu(r),r;
    }
}
void usetag(int x,vector<int>&vec)
{
    if(!x)return;
    usetag(t[x].fa,vec);
    vec.push_back(x);
}
int query(int x,int op)
{
    if(!x)return 0;
//  pd(x);
//  if(t[x].fa)pd(t[x].fa);
//  assert(!t[0].ls);
//  assert(!t[0].rs);
//  cerr << x << " " << op << " " << t[t[x].ls].siz << " " << t[x].ls << "\n";
    if(op==1)return 1+t[t[x].ls].siz+query(t[x].fa,t[t[x].fa].rs==x);
    return query(t[x].fa,t[t[x].fa].rs==x);
}
void print(int x)
{
    if(!x)return;
    pd(x);print(t[x].ls);cerr << (x<=n?x:0) << " ";print(t[x].rs);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
//  freopen("dt.in","r",stdin);
//  freopen("test.out","w",stdout);
    cin >> n >> q;
    for ( int i = 1 ; i <= n ; i++ )
    {
        char ch;cin >> ch;
        rt=merge(rt,new_node(ch));
    }
//  print(rt);
//  cerr << endl;
    while(q--)
    {
        char op;cin >> op;
        if(op=='I')
        {
            int p;char ch;cin >> p >> ch;
            int L,R;
            split(rt,p,L,R);
            rt=merge(merge(L,new_node(ch)),R);
        }else if(op=='D')
        {
            int p;cin >> p;
            int L,R,M;
            split(rt,p,L,R);
            split(L,t[L].siz-1,L,M);
            t[M].ch=0;
            rt=merge(L,R);
        }else if(op=='R')
        {
            int l,r;cin >> l >> r;
            int L,R,M;
            split(rt,r,L,R);
//          cerr << "debug\n";
//          print(L);
//          cerr << endl;
            split(L,l-1,L,M);
//          cerr << "debug\n";
            t[M].tag^=1;
            rt=merge(merge(L,M),R);
        }else if(op=='P')
        {
            int id;cin >>id;
//          usetag(id);
            if(t[id].ch==0)cout << 0 << endl;
            else{
                vector<int>vec;vec.clear();
                usetag(id,vec);
                for ( auto x:vec )pd(x);
                cout << query(id,1) << endl;
            }
        }else if(op=='T')
        {
            int p;cin >> p;
            int L,R,M;
            split(rt,p,L,R);
            split(L,t[L].siz-1,L,M);
            cout << t[M].ch << endl;
            rt=merge(merge(L,M),R);
        }else{
            int l,r;cin >> l >> r;
            int L,R,M;
            split(rt,r,L,R);
            split(L,l-1,L,M);
            cout << __builtin_popcount(t[M].S) << endl;
            rt=merge(merge(L,M),R);
        }
//      print(rt);
//      cerr << endl;
    }
    return 0;
}

再给出一个猎奇块状链表单根做法，我没写，闲着没事的人可以去实现一下。

难点仍在于 4 操作，考虑一些根号数据结构。由于要支持插入删除，考虑块状链表。

1256 操作显然是基本操作，3 操作考虑每次暴力交换，最多会交换 \sqrt{n} 个块并新增两个块。在整块的内部类似文艺平衡树的打 tag。4 操作考虑每个块维护一个 gp_hash_table 来快速查询某个块内有没有某个东西。也是单根的。

看起来就很屎，因此我没写。