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

panda_2134

2017-08-19 22:52:33

Solution

这里介绍一种使用STL混分的方法,按照现在的NOI Linux环境,比赛里面也可以通过评测。 导入ext/rope,就白送一个可持久化数组233 不过常数有点大就是了,这个题目似乎要求比较严格,只能拿80。详见代码: ```cpp #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)); } } } ```