P3919 【模板】可持久化数组（可持久化线段树/平衡树）

题面

https://www.luogu.org/problem/P3919

题解

#include<iostream>
#include<cstdio>
using namespace std;
struct node{
  int lson,rson,lb,rb,x;
} tree[50000050];
int n,m,cnt=0;
int a[1000500],root[1000500];

void maketree(int x,int l,int r){
  //printf("%d %d %d\n",x,l,r);
  tree[x].lb=l; tree[x].rb=r;
  if (l==r) {
    tree[x].x=a[l];
  }
  else {
    int mid=(l+r)/2;
    tree[x].lson=cnt+1;
    //printf("%d\n",tree[x].lson);
    maketree(++cnt,l,mid);
    tree[x].rson=cnt+1;
    //printf("%d\n",tree[x].rson);
    maketree(++cnt,mid+1,r);
  }
}

void build(int nee,int oll,int loc,int val) {
  tree[nee]=tree[oll];
  if (tree[nee].lb==tree[nee].rb) {
    tree[nee].x=val;
    return;
  }
  int mid=(tree[nee].lb+tree[nee].rb)/2;
  if (loc<=mid) {
    tree[nee].lson=cnt+1;
    build(++cnt,tree[oll].lson,loc,val);
  }
  else {
    tree[nee].rson=cnt+1;
    build(++cnt,tree[oll].rson,loc,val);
  }
}

int visit(int x,int loc) {
  //printf("%d %d\n",tree[x].lb,tree[x].rb);
  if (tree[x].lb==tree[x].rb) return tree[x].x;
  int mid=(tree[x].lb+tree[x].rb)/2;
  if (loc<=mid) return visit(tree[x].lson,loc); else return visit(tree[x].rson,loc);
}

int main(){
  int i,opt,v,loc,val;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;i++) scanf("%d",&a[i]);
  root[0]=1;
  cnt=1;
  maketree(1,1,n);
  for (i=1;i<=cnt;i++) {
    //printf("%d %d %d %d %d\n",tree[i].lson,tree[i].rson,tree[i].lb,tree[i].rb,tree[i].x);
  }
  for (i=1;i<=m;i++) {
    scanf("%d %d",&v,&opt);
    if (opt==1) {
      scanf("%d %d",&loc,&val);
      root[i]=++cnt;
      build(root[i],root[v],loc,val);
    }
    else {
      scanf("%d",&loc);
      root[i]=root[v];
      printf("%d\n",visit(root[v],loc));
    }
  }
  return 0;
}