可持久化数组
<pre><code class="language-cpp">#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);
}
</code></pre>