题解 P6166 【[IOI2012]scrivener】

向辛苦审核题解的管理道歉，感谢指出排版错误，确实是我孤陋寡闻了。

P6166 [IOI2012]scrivener

闲话

蒟蒻my最近学了主席树，这可真是个好东西，他决定写篇题解加深下印象。

• P3919 【模板】可持久化线段树 1（可持久化数组）
• P3834 【模板】可持久化线段树 2（主席树）

主席树，又名函数式线段树。由于发明人黄嘉泰的名字缩写和某位中国共产党领导人是一样的，故名主席树。

实现可持久化使用复制节点的方式，由于一次修改最多修改 \log n 个节点，于是需要开 n\log n 的空间。

弱化版 P1383 高级打字机 ,所谓挑战指的应该就是这题了。

做法

首先没有初始版本，于是不需要建树。

1. 对于输入字符操作，我们维护一个 \text{len} 表示这个节点维护的区间的字符长度，实际上只有根节点的 \text{len} 值有用，但是我懒得理他了（doge
2. 对于撤销操作，直接让当前版本根节点指向之前的版本即可。注意撤销最后 \text{x} 个操作不是直接复制 \text{x} 版本。
3. 对于查询操作，记得线段树维护的区间从 \text{1} 开始，位置要对应加一，然后在最新版本查询。
4. 注意询问操作并不生成一个新版本，所以版本号要另外统计。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=1e6+10;

int n,cnt,rt[N],tot;
struct node {int l,r,len; char c;} hjt[N << 5];
inline int clone(int now) {hjt[++cnt]=hjt[now]; return cnt;}//复制

int modify(int now,int l,int r,int p,char ch)
{
    now=clone(now); hjt[now].len++;//只会修改log个节点，不用写pushup 
    if(l == r) {hjt[now].c=ch; return now;}
    int mid=(l+r) >> 1;
    if(p <= mid) hjt[now].l=modify(hjt[now].l,l,mid,p,ch);
    else hjt[now].r=modify(hjt[now].r,mid+1,r,p,ch);
    return now;
}

char query(int now,int l,int r,int p)
{
    if(l == r) return hjt[now].c;
    int mid=(l+r) >> 1;
    if(p <= mid) return query(hjt[now].l,l,mid,p);
    return query(hjt[now].r,mid+1,r,p);
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d",&n);
    char op,ch;
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf(" %c",&op);
        if(op == 'T') {scanf(" %c",&ch); tot++; rt[tot]=modify(rt[tot-1],1,n,hjt[rt[tot-1]].len+1,ch);}//在最后插入新字符
        if(op == 'U') {scanf("%d",&x); tot++; rt[tot]=rt[tot-x-1];}//指向旧版本，注意这个版本号
        if(op == 'P') {scanf("%d",&x); printf("%c\n",query(rt[tot],1,n,x+1));}
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

吐槽弱化版数据过水，空间只开 \text{n} 都能过。

Thank you for your reading!

您的点赞和评论是对作者最大的支持！