题解 CF589C Polycarp's Masterpiece

· · 题解

magic！科学的可持久化！

可持久化平衡树，他好吗？他不好！

考虑魔改可持久化线段树！

我们先对原序列建一棵线段树，支持求区间某字符出现次数。

然后我们要支持 \log v 次 copy 操作，v=10^{18}。之所以是 \log v 是因为 \log v 次操作后的元素位置 \ge v，不在 [l,r] 内。

每次 copy 是把后 k 个元素放到序列最后，再把前面的元素放到序列最后。

众所周知线段树会把一个区间分成 \log n 个子段，而可持久化的意义在于共用重复信息。

所以，我们把要 copy 的区间分成子段，排成一个序列，然后在他们上面建树！

设序列长为 5，k=1，友情供图：

相信你看了图之后就会了！

一些实现细节：

线段树比较臃肿，换成非 leafy tree（相当于把线段树换成一棵完美的平衡树）会快些。

这个线段树不方便维护区间左右端点（你写了自然知道），所以不妨维护每个节点的 size，即区间长度。因此一个询问 [l,r] 要拆成 [1,r]-[1,l-1]。

另外，维护 size 后功能变弱，对于 copy 的元素，前/后的要分别考虑。因此，遗憾的，我们无法支持 copy 任意区间的操作。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char s[105];
int cnt,ncnt;
struct seg
{
    ll size;
    int s[2];
    ll cnt[26];
}t[1000005];
#define ls t[w].s[0]
#define rs t[w].s[1]
int nd[100005];
int build(int l,int r)
{
    int w=++cnt,i,mid=l+r>>1;
    t[w].size=r-l+1;
    for(i=l;i<=r;i++)
        t[w].cnt[s[i]-'a']++;
    if(l<r)
        ls=build(l,mid),
        rs=build(mid+1,r);
    return w;
}
void pushup(int w)
{
    for(int i=0;i<26;i++)
        t[w].cnt[i]=t[ls].cnt[i]+t[rs].cnt[i];
    t[w].size=t[ls].size+t[rs].size;
}
void getp(int w,ll x)
{
    if(t[w].size==1)
    {
        if(x) nd[++ncnt]=w;
    }
    else if(x>t[ls].size)
        nd[++ncnt]=ls,getp(rs,x-t[ls].size);
    else
        getp(ls,x);
}
void getn(int w,ll x)
{
    if(t[w].size==1)
    {
        if(x) nd[++ncnt]=w;
    }
    else if(x>t[rs].size)
        getn(ls,x-t[rs].size),nd[++ncnt]=rs;
    else
        getn(rs,x);
}
int build2(int l,int r)
{
    if(l==r) return nd[l];
    int w=++cnt,mid=l+r>>1;
    ls=build2(l,mid),
    rs=build2(mid+1,r);
    pushup(w);
    return w;
}
ll ask(int w,ll x,int c)
{
    if(t[w].size==1)
        return x*t[w].cnt[c];
    if(x>t[ls].size)
        return ask(rs,x-t[ls].size,c)+t[ls].cnt[c];
    return ask(ls,x,c);
}
int main()
{
    int n,m,rt,k,ne;
    ll len,l,r;
    char c[3];
    scanf("%s%d%d",s+1,&n,&m);
    rt=build(1,len=strlen(s+1));
    while(n--)
    {
        scanf("%d",&k);
        if(len>1e18) continue;
        k%=len;
        ncnt=0;
        getn(rt,k),getp(rt,len-k);  
        ne=++cnt;
        t[ne].s[0]=rt,
        t[ne].s[1]=build2(1,ncnt);
        pushup(rt=ne);
        len*=2;
    }
    while(m--)
    {
        scanf("%lld%lld%s",&l,&r,c);
        printf("%lld\n",ask(rt,r,*c-'a')-ask(rt,l-1,*c-'a'));
    }
}