旅行（树剖+主席树）
旅行（树剖+主席树）
给定一个n(<=1e5)的图，m(<=1e5)个操作，每次标记第ci个点，或者询问a到b的路径中，在第y个操作之后没有被标记的第k个点。
树剖+主席树维护重链。就说三点（说多了都是泪）：1. 线段树上二分要注意min max。2. windows的缺省栈值只有4m，所以递归1e5层铁定爆栈了（我的程序3e4层就爆了）。 3. 暴力算法，通常，隐藏的很深。
……
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5, INF=0x3f3f;
int n, m, root;
struct Edge{
int to, nxt;
}e[maxn*2];
int cnte, fir[maxn];
void addedge(int x, int y){
Edge &ed=e[++cnte];
ed.to=y; ed.nxt=fir[x]; fir[x]=cnte; }
int dep[maxn], siz[maxn], son[maxn], fa[maxn];
void dfs1(int now, int fat, int depth){
dep[now]=depth; siz[now]=1;
int maxm=0; fa[now]=fat;
for (int i=fir[now]; i; i=e[i].nxt){
dfs1(e[i].to, now, depth+1);
siz[now]+=siz[e[i].to];
if (siz[e[i].to]>maxm){
maxm=siz[e[i].to]; son[now]=e[i].to; }
}
}
int top[maxn], id[maxn], ori[maxn], cnt; //id[i]:结点i在主席树中位置的编号
void dfs2(int now){
id[now]=++cnt; ori[cnt]=now;
for (int i=fir[now]; i; i=e[i].nxt)
if (e[i].to==son[now]){
top[e[i].to]=top[now];
dfs2(e[i].to); }
for (int i=fir[now]; i; i=e[i].nxt)
if (e[i].to!=son[now]){
top[e[i].to]=e[i].to;
dfs2(e[i].to);
}
}
int rt[maxn], cntnode;
struct Node{
int x, l, r; //x表示有多少点*没有*被标记过
}node[maxn*20];
//now:当前主席树的结点编号 ori:前一个主席树的同位点编号
void ins(int &now, int ori, int l, int r, int pos){
now=++cntnode; node[now]=node[ori];
if (l==r){ node[now].x=1; return; }
int mid=(l+r)>>1;
if (pos<=mid) ins(node[now].l, node[ori].l, l, mid, pos);
else ins(node[now].r, node[ori].r, mid+1, r, pos);
++node[now].x; //保证区间内被标的点数+1
}
int query(int now, int l, int r, int L, int R){
if (!now) return 0;
if (l>r) return 0;
if (r<L||l>R) return 0;
if (l>=L&&r<=R){ return node[now].x; }
int mid=(l+r)>>1, ans=0;
if (mid>=L) ans+=query(node[now].l, l, mid, L, R);
if (mid<R) ans+=query(node[now].r, mid+1, r, L, R);
return ans;
}
struct Query{ //表示能被询问到的区间
Query(int x=0, int y=0, int d=0){ l=x; r=y; dir=d; }
int l, r, dir; //l和r都是主席树上的点
}q[maxn]; //若dir=1表示是上升的，dir=-1表示是下降的
int cntq, latest;
void jump(int x, int y, int flag){ //处理出所有询问区间
cntq=0; int lca, ox=x, oy=y, lx, ly;
if (flag&&(x==y||fa[x]==y||fa[y]==x)) return;
while (top[x]!=top[y]){
if (dep[top[x]]>dep[top[y]]){
q[cntq++]=Query(id[top[x]], id[x], 1);
lx=top[x]; x=fa[top[x]];
}
if (top[x]==top[y]) break;
if (dep[top[x]]<=dep[top[y]]){
q[cntq++]=Query(id[top[y]], id[y], -1);
ly=top[y]; y=fa[top[y]];
}
}
if (dep[x]>dep[y]) q[cntq++]=Query(id[y], id[x], 1), lca=y;
else q[cntq++]=Query(id[x], id[y], -1), lca=x;
if (!flag) return;
if (ox==lca){
if(x==y) jump(ly, fa[oy], 0); else jump(son[ox], fa[oy], 0);
} else if (oy==lca){
if (x==y) jump(fa[ox], lx, 0); else jump(fa[ox], son[oy], 0);
} else jump(fa[ox], fa[oy], 0);
}
//二分查找线段树区间上从左到右第k个未标记点
int div1(int nowb, int nowa, int l, int r, int L, int R, int k){
if (l==r) return l;
int mid=(l+r)>>1;
int lans=query(node[nowb].l, l, mid, L, R)
-query(node[nowa].l, l, mid, L, R); //左边有多少标记点
lans=mid-max(l, L)+1-lans; if (mid<L) lans=0; //注意max这里是坑！
if (lans>=k) return div1(node[nowb].l, node[nowa].l, l, mid, L, R, k);
else return div1(node[nowb].r, node[nowa].r, mid+1, r, L, R, k-lans);
}
//二分查找线段树区间上从右到左第k个未标记点
int div2(int nowb, int nowa, int l, int r, int L, int R, int k){
if (l==r) return l;
int mid=(l+r)>>1;
int rans=query(node[nowb].r, mid+1, r, L, R)
-query(node[nowa].r, mid+1, r, L, R); //右边有多少标记点
rans=min(r, R)-mid-rans; if (mid>=R) rans=0;
if (rans>=k) return div2(node[nowb].r, node[nowa].r, mid+1, r, L, R, k);
else return div2(node[nowb].l, node[nowa].l, l, mid, L, R, k-rans);
}
int solve(int k, int y, int now){ //已知这些顺序的区间问第k个未标记点
for (int i=0; i<cntq; ++i){
if (q[i].dir==-1) continue;
int t=query(rt[now], 1, n, q[i].l, q[i].r)
-query(rt[y], 1, n, q[i].l, q[i].r); //整段区间上的标记点个数
t=q[i].r-q[i].l+1-t;
if (k<=t) return ori[div2(rt[now], rt[y], 1, n, q[i].l, q[i].r, k)];
k-=t;
}
for (int i=cntq-1; i>=0; --i){ //倒着处理区间
if (q[i].dir==1) continue;
int t=query(rt[now], 1, n, q[i].l, q[i].r)
-query(rt[y], 1, n, q[i].l, q[i].r);
t=q[i].r-q[i].l+1-t;
if (k<=t) return ori[div1(rt[now], rt[y], 1, n, q[i].l, q[i].r, k)];
k-=t;
}
return -1;
}
int main(){
scanf("%d", &n); int t;
for (int i=1; i<=n; ++i){
scanf("%d", &t);
if (!t) root=i; else addedge(t, i);
}
dfs1(root, 0, 0); top[root]=root; dfs2(root);
int op, a, b, c, k, y;
scanf("%d", &m);
for (int i=1; i<=m; ++i){
scanf("%d", &op);
if (op==1){
scanf("%d", &c);
ins(rt[i], rt[i-1], 1, n, id[c]); continue; }
rt[i]=rt[i-1];
scanf("%d%d%d%d", &a, &b, &k, &y);
jump(a, b, 1);
printf("%d
", solve(k, y, i)); //走y+1到i时刻之间没有被标记的点
}
return 0;
}