题目链接:BZOJ1146
【分析】这题最容易想到的就是二分答案+树链剖分+线段树套BST,但是复杂度有q*logn^4,而且代码量极大,本人太懒不想写了,学习了一种神一样的解法;而且复杂度才q*logn^2;
首先BZOJ2588可以知道,对于静态树上第K大,可以在每个点建一棵到根的前缀可持久化线段树,则查询任意两点间(x,y)的第k大可以在主席树T=a[x]+a[y]-2*[LCA(x,y)];由于是点所以变成T = a[x]+a[y]-a[LAC(x,y)]-a[fa[LCA(x,y)]];这个查询可以在主席树带入这四个点实现O(logn)的查询。然后这题是可修改的,如果直接套上树状数组没法在树上维护前缀和,怎么办?可以用DFS序呀!对于每一个点,在其入栈的时候加上,在出栈的时候减去。那么如果查询一个点入栈位置的前缀和,就是它到根的路径的信息。这样就转变成了区间可修改第k大+静态树上K大,查询时带入树状数组表示的值树按照这个公式T=a[x]+a[y]-2*[LCA(x,y)]计算即可。查询复杂度O(logn^2),可以配合静态n*logn预处理加上另外维护修改可以把空间复杂度降到n*logn+n*logn^2
【AC CODE】5188ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) #include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 80000+10, MAXQ = 80000+10, MAXM = 80*MAXN; struct IN{ int k,a,b; }in[MAXQ]; int a[MAXN],n,num[MAXN+MAXQ],cnt,sot[MAXN+MAXQ],head[MAXN],e,nxt[MAXN<<1],to[MAXN<<1]; int sum[MAXM], lc[MAXM],rc[MAXM],tol; int rt[MAXN<<2]; inline void add_edge(int u, int v) { nxt[e] = head[u], to[e] = v; head[u] = e++; } inline int mhash(int v){return lower_bound(sot+1,sot+1+cnt,v)-sot;} int fa[MAXN], ft[MAXN], d[MAXN<<1],id[MAXN<<1],all; int df[MAXN<<1],st[MAXN],ed[MAXN],dcnt; bool ised[MAXN<<1]; void dfs(int u, int dep) { ft[u] = all, d[all] = dep, id[all++] = u; df[++dcnt] = a[u];st[u] = dcnt;ised[dcnt] = 0; for(int i = head[u]; ~i; i = nxt[i]) { int v = to[i]; if(v == fa[u]) continue; fa[v] = u; dfs(v,dep+1); d[all] = dep, id[all++] = u; } df[++dcnt] = a[u];ed[u] = dcnt;ised[dcnt] = 1; } int dp[MAXN<<1][21], dp_num[MAXN<<1][21];//dp_num记录dp对应的点的编号 void st_init() { rep(i,0,all) dp[i][0] = d[i], dp_num[i][0] = id[i]; for(int j = 1; (1<<j) <= all; j++) { for(int i = 0; i+(1<<j)-1 < all; i++) { if(dp[i][j-1] < dp[i+(1<<(j-1))][j-1]) { dp[i][j] = dp[i][j-1]; dp_num[i][j] = dp_num[i][j-1]; } else { dp[i][j] = dp[i+(1<<(j-1))][j-1]; dp_num[i][j] = dp_num[i+(1<<(j-1))][j-1]; } } } } int st_query(int x, int y) { if(x > y) swap(x,y); int k = 0; while((1<<(k+1)) <= y-x+1) k++; if(dp[x][k] <= dp[y-(1<<k)+1][k]) return dp_num[x][k]; return dp_num[y-(1<<k)+1][k]; } int lca_query(int x, int y){ return st_query(ft[x],ft[y]);}//x,y的LCA, O(1) void bulid(int &u, int x, int y, int p, int v) { sum[++tol] = sum[u]+v,lc[tol] = lc[u],rc[tol] = rc[u]; u = tol; if(x == y) return; int m = (x+y)>>1; if(p <= m) bulid(lc[u],x,m,p,v); else bulid(rc[u],m+1,y,p,v); } void init() { all = tol = 0; clc(rt,0); dfs(1,0); st_init(); rt[dcnt+1] = rt[0]; bulid(rt[dcnt+1],1,cnt,mhash(df[1]),1); repe(i,2,dcnt) { rt[i+dcnt] = rt[i-1+dcnt]; int v = 1; if(ised[i]) v = -1; bulid(rt[i+dcnt],1,cnt,mhash(df[i]),v); } } void t_update(int &u, int x, int y, int p, int v) { if(!u) {lc[++tol] = lc[u],rc[tol] = rc[u], sum[tol] = sum[u];u = tol;} sum[u] += v; if(x == y) return; int m = (x+y)>>1; if(p <= m) t_update(lc[u],x,m,p,v); else t_update(rc[u],m+1,y,p,v); } inline int lowbit(int x){return x&-x;} void add(int x, int v) { int p = mhash(df[x]); while(x <= dcnt) { t_update(rt[x],1,cnt,p,v); x += lowbit(x); } } void update(int x, int v) { add(st[x],-1);//第一次出现点删掉原来加上新的 df[st[x]] = v; add(st[x],1); add(ed[x],1);//最后一次出现点相反 df[ed[x]] = v; add(ed[x],-1); } int tx[100],ty[100],len[2]; int query(int x, int y, int k) { if(x == y) return x; int m = (x+y)>>1, tmp = 0; rep(i,0,len[1]) tmp += sum[rc[ty[i]]]; rep(i,0,len[0]) tmp -= sum[rc[tx[i]]]; if(tmp >= k) { rep(i,0,len[1]) ty[i] = rc[ty[i]]; rep(i,0,len[0]) tx[i] = rc[tx[i]]; return query(m+1,y,k); } rep(i,0,len[1]) ty[i] = lc[ty[i]]; rep(i,0,len[0]) tx[i] = lc[tx[i]]; return query(x,m,k-tmp); } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int q; scanf("%d %d",&n, &q); int cc = 0; repe(i,1,n) scanf("%d", &a[i]), num[++cc] = a[i]; e = 0; clc(head,-1); rep(i,1,n) { int u,v; scanf("%d %d", &u, &v); add_edge(u,v); add_edge(v,u); } rep(i,0,q) { scanf("%d %d %d", &in[i].k, &in[i].a, &in[i].b); if(!in[i].k) num[++cc] = in[i].b; } sort(num+1,num+1+cc); sot[cnt=1] = num[1]; repe(i,2,cc) if(num[i] != num[i-1]) sot[++cnt] = num[i]; init(); rep(i,0,q) { if(in[i].k) { len[0]=len[1]=0; int lca = lca_query(in[i].a,in[i].b); int ta = st[in[i].a], tb = st[in[i].b],tlca = st[lca],tflca = st[fa[lca]]; ty[len[1]++] = rt[ta+dcnt],ty[len[1]++] = rt[tb+dcnt];//静态初始值 for(int j = ta; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j]; for(int j = tb; j > 0; j -= lowbit(j)) ty[len[1]++] = rt[j]; tx[len[0]++] = rt[tlca+dcnt],tx[len[0]++] = rt[tflca?tflca+dcnt:0]; for(int j = tlca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j]; for(int j = tflca; j > 0; j -= lowbit(j)) tx[len[0]++] = rt[j]; int tmp = 0; rep(j,0,len[1]) tmp += sum[ty[j]]; rep(j,0,len[0]) tmp -= sum[tx[j]]; if(tmp < in[i].k) puts("invalid request!"); else printf("%d\n", sot[query(1,cnt,in[i].k)]); } else update(in[i].a,in[i].b); } return 0; }