题解 P3919 【【模板】可持久化数组(可持久化线段树/平衡树)】

2017-08-19 22:52:33


这里介绍一种使用STL混分的方法,按照现在的NOI Linux环境,比赛里面也可以通过评测。

导入ext/rope,就白送一个可持久化数组233

不过常数有点大就是了,这个题目似乎要求比较严格,只能拿80。详见代码:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int MAXM = 1e6;
int N,M;
rope<int> *S[MAXM+10];
inline int readint(){
    int f=1,r=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){r=r*10+c-'0';c=getchar();}
    return f*r;
}
int main(){
    N=readint();M=readint();
    S[0]=new rope<int>();
    S[0]->append(0);
    for(int i=1;i<=N;i++)
        S[0]->append(readint());
    for(int i=1;i<=M;i++){
        int v,k,a,b;
        v=readint();k=readint();
        S[i]=new rope<int>(*S[v]);//从指定版本生成新版本(只换根)
        if(k==1) {
            a=readint();b=readint();
            S[i]->replace(a,b);
        } else {
            a=readint();
            printf("%d\n",S[i]->at(a));
        }
    }
}