可持久化数组

#include <iostream>
using namespace std;
const int maxn = 2e5+5;
int n;
struct Node{
    int l,r,val;
};
Node tree[maxn*40];
int cnt, tot;
void build(int l, int r, int &now)
{
    now = ++cnt;
    if(l == r)
    {
        tree[now].val = ++tot;
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, tree[now].l);
    build(mid+1, r, tree[now].r);
}
void modify(int l, int r, int ver, int &now, int pos, int val){
    tree[now = ++cnt] = tree[ver];
    if(l == r)
    {
        tree[now].val = val;
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) modify(l, mid, tree[ver].l, tree[now].l, pos, val);
    else modify(mid+1, r, tree[ver].r, tree[now].r, pos, val);
}
int query(int l, int r, int now, int pos){
    if(l == r) return tree[now].val;
    int mid = (l+r) >> 1;
    if(pos <= mid) return query(l, mid, tree[now].l, pos);
    else return query(mid+1, r, tree[now].r, pos);
}