[关闭]
@zzzc18 2017-12-28T17:35:36.000000Z 字数 1461 阅读 1113

可持久化数组

洛谷 可持久化数据结构 线段树


洛谷模板题

题目描述
如题,你需要维护这样的一个长度为 的数组,支持如下几种操作

1.在某个历史版本上修改某一个位置上的值

2.访问某个历史版本上的某一位置的值

此外,每进行一次操作(对于操作2,即为生成一个完全一样的版本,不作任何改动),就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号,版本0表示初始状态数组)


直接使用主席树维护就可以了,似乎会比用平衡树维护常数小

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 1000000+9;
  6. int n,m;
  7. int num[MAXN];
  8. int rt[MAXN];
  9. struct T{
  10. int ls,rs;
  11. int val;
  12. }tree[MAXN*21];
  13. int cnt;
  14. void update(int x){
  15. //nothing to do ...
  16. }
  17. int Build(int l,int r){
  18. int now=++cnt;
  19. if(l==r){
  20. tree[now].val=num[l];
  21. return now;
  22. }
  23. int mid=l+r>>1;
  24. tree[now].ls=Build(l,mid);
  25. tree[now].rs=Build(mid+1,r);
  26. update(now);
  27. return now;
  28. }
  29. int insert(int pre,int left_range,int right_range,int pos,int val){
  30. int now=++cnt;
  31. tree[now]=tree[pre];
  32. if(left_range==right_range){
  33. tree[now].val=val;
  34. return now;
  35. }
  36. int mid=left_range+right_range>>1;
  37. if(pos<=mid)tree[now].ls=insert(tree[pre].ls,left_range,mid,pos,val);
  38. else tree[now].rs=insert(tree[pre].rs,mid+1,right_range,pos,val);
  39. return now;
  40. }
  41. int query(int k,int left_range,int right_range,int pos){
  42. if(left_range==right_range)
  43. return tree[k].val;
  44. int mid=left_range+right_range>>1;
  45. if(pos<=mid)return query(tree[k].ls,left_range,mid,pos);
  46. else return query(tree[k].rs,mid+1,right_range,pos);
  47. }
  48. int main(){
  49. freopen("in.in","r",stdin);
  50. scanf("%d%d",&n,&m);
  51. for(int i=1;i<=n;i++)
  52. scanf("%d",&i[num]);
  53. rt[0]=Build(1,n);
  54. for(int i=1;i<=m;i++){
  55. int v,opt,loc,val;
  56. scanf("%d%d",&v,&opt);
  57. if(opt==1){
  58. scanf("%d%d",&loc,&val);
  59. rt[i]=insert(rt[v],1,n,loc,val);
  60. }
  61. else{
  62. scanf("%d",&loc);
  63. rt[i]=rt[v];
  64. printf("%d\n",query(rt[v],1,n,loc));
  65. }
  66. }
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注