树上带修改K大，太可怕。。写了树链剖分+线段树套平衡树+二分和dfs序+主席树两种，每种都是写+调试花了将近5个小时！！我实在是太弱了。。
1. 树链剖分+线段树套平衡树+二分
最显然的做法了，没啥好多说的，不过写起来真是麻烦（我太弱），
一不小心就会把线段树和平衡树的节点的域弄混，犯了超级多傻逼错误。。写这题的时候还把自己树链剖分的风格改了一下，以前的实在是太麻烦了。。查询的时候二分答案，统计比当前的k大的数有多少个就行了。。
2. dfs序+主席树
考虑不带修改，那么可以对每个节点维护一颗权值线段树记录它到root的数，类型区间K大的，每个点的新树可以由父节点更新log n个节点来得到，所以初始化是O（Nlog N），查询只要把这两个点和lca的权值权值线段树拉出来，二分答案像上面一样搞就行。。如果这两个点是x，y，lca是p，Ui表示i节点的权值线段树，答案就是Ux+Uy-2*Up再加上p的权值。。
再来想带修改，大思路还是要把树转化成线性序列来搞。。那么就想到dfs序，若修改一个节点的权值，只会改变它的子树上的各点的权值线段树，而这些点再dfs序中又对应的是一段区间，那就有办法了。。用树状数组来维护所有的修改，若点i从a被修改为b，L[i]表示i在dfs序中出现的位置，R[i]表示i的子树上的节点在dfs中出现的最后位置，那么先将L[i]-n的a减去1，b加上1，再讲R[i]+1-n的a加上1，b减去1，那么就完成的对子树区间的修改。。具体查询的时候只要把dfs序当做区间k大那样做就行了，记得要加上原来未修改时的权值线段树。。
树剖+线段树套平衡树+二分：
?
#include
#include
#define N 80005 #define NN 1600020 #define ls c[x][0] #define rs c[x][1] using namespace std; struct edge{ int e,next; }ed[N*2]; int n,Q,s,e,ne=0,i,nd=0,cnt=0,rt,k,x,y,maxq=0,a[N],q[N],q1[N],fa[N],sz[N],top[N],son[N],d[N],xu[N],root[N*4],l[N*4],r[N*4],lc[N*4],rc[N*4],c[NN][2],size[NN],num[NN],same[NN],pre[NN]; void add(int s,int e) { ed[++ne].e=e; ed[ne].next=a[s];a[s]=ne; } //处理size 选出son void dfs1(int x) { int to,ms=0; sz[x]=1;son[x]=0; for (int j=a[x];j;j=ed[j].next) if (ed[j].e!=fa[x]) { to=ed[j].e;d[to]=d[x]+1; fa[to]=x;dfs1(to); sz[x]+=sz[to]; if (ms
1) {same[x]--;size[x]--;return;} if (ls*rs==0) {root[rt]=ls+rs,pre[ls+rs]=0;return;} merge(ls,rs,rt); } //初始化树套树 void build(int &x,int ll,int rr) { x=++cnt;l[x]=ll;r[x]=rr;root[x]=0; ins(root[x],q1[ll],x,0); if (ll==rr) { lc[x]=rc[x]=0; return; } int mid=(ll+rr)>>1; for (int i=ll+1;i<=rr;i++) ins(root[x],q1[i],x,0); build(lc[x],ll,mid);build(rc[x],mid+1,rr); } void init() { fa[1]=0;d[1]=0;size[0]=0; dfs1(1);dfs2(1,1); cnt=0;build(rt,1,n); } //修改&&询问 void change(int x,int ll,int k) { if (!x) return; del(root[x],q1[ll],x);ins(root[x],k,x,0);//print(root[x]);printf("\n");printf("%d %d %d %d**\n",root[x],l[x],r[x],size[0]); if (ll>(l[x]+r[x])/2) change(rc[x],ll,k);else change(lc[x],ll,k); } int lca(int x,int y) { if (d[top[x]]>d[top[y]]) swap(x,y); while (top[x]!=top[y]) { y=fa[top[y]]; if (d[top[x]]>d[top[y]]) swap(x,y); } return d[x]
k) ans+=size[rs]+same[x]; else if (num[x]==k) return ans+size[rs]; x=c[x][num[x]
r[x]||rr
=r[x]) { // print(root[x]);printf("*\n"); return getsz(root[x],k); } return query(lc[x],ll,rr,k)+query(rc[x],ll,rr,k); } int sum(int x,int y,int k) { int ans=0; while (top[x]!=top[y]) { if (d[top[x]]>d[top[y]]) swap(x,y); ans+=query(rt,xu[top[y]],xu[y],k);//printf("$%d %d %d\n",xu[top[y]],xu[y],ans); y=fa[top[y]]; } ans+=query(rt,min(xu[x],xu[y]),max(xu[x],xu[y]),k); return ans; } void solve(int x,int y,int k) { int p=lca(x,y),l=1,r=maxq,mid,t; if (d[x]+d[y]-2*d[p]+1
>1; t=sum(x,y,mid);//printf("re:%d %d\n",mid,t); if (t>=k) l=mid+1;else r=mid; } printf("%d\n",l); } int main() { freopen("1146.in","r",stdin); scanf("%d%d",&n,&Q); for (i=1;i<=n;i++) scanf("%d",&q[i]),a[i]=0,maxq=max(maxq,q[i]); for (i=1;i dfs序+主席树:
?
?
#include
#include
#include
#define N 80010 #define NN 8000010 using namespace std; struct edge{ int e,xu,next; }ed[N*4];//兼并了图的边和询问lca点对 struct node{ int n,yuan; node(){} node(int n,int yuan):n(n),yuan(yuan){} }num[2*N]; int n,Q,i,ne=0,nd=0,tim=0,cnt=0,tot=0,s,e,sum[2],d[N],a[N],L[N],R[N],fa[N],pre[N],size[NN],lc[NN],rc[NN],lca[N],k[N],x[N],y[N],u[N],h[N],q[N],newq[2*N],root[N],c[N],use[N][2]; int lowbit(int x){return x&-x;} int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} void add(int s,int e) { ed[++ne].e=e;ed[ne].next=a[s];a[s]=ne; } void add2(int s,int e,int xu) { ed[++ne].e=e;ed[ne].xu=xu;ed[ne].next=h[s];h[s]=ne; } bool cmp(node a,node b) {return a.n
>1; size