北京网站建设 和君,怎样做国际网站,seo系统培训,北极鱼wordpress主席树学习笔记 说在前边#xff1a; 之前了解过主席树的基础的思想#xff0c;但是没有系统学习过#xff0c;所以打算通过一些题目重新学习。POJ2104 题意#xff1a;静态区间查询 k-th number思路#xff1a;对每个位置开一颗权值线段树#xff0c;维护前缀区间每个数… 主席树学习笔记 说在前边 之前了解过主席树的基础的思想但是没有系统学习过所以打算通过一些题目重新学习。POJ2104 题意静态区间查询 k-th number思路对每个位置开一颗权值线段树维护前缀区间每个数字出现的次数这样只需实现两棵线段树相减利用简单的二分思想即可求出 k-th number。问题内存不足以开n颗线段树时间自然也不够。解决方法注意到相邻两个位置只会一个位置不同那么发生改变的只有包含这个位置的一条链。那建树时可以把新建这一条链其他的边都接在上一个位置的线段树上即可。通过这样的方式我们保存了历史版本的线段树。#include iostream
#include cstdio
#include algorithm
#define rep(i,a,b) for(int ia;ib;i)
typedef long long ll;
const int N 1e5 100;
using namespace std;
int n, m;
struct node{ll v; int id;}a[N];
bool cmp(node a,node b){return a.vb.v;}
int root[N], fid[N], tot;
struct tree{int l,r,num;}T[N*20];
void ins(int x,int p,int l,int r) {T[tot]T[x]; x tot; T[x].num;if(l r) return;int mid (l r) 1;if(p mid) ins(T[x].l,p,l,mid);else ins(T[x].r,p,mid1,r);
}
int ask(int pl,int pr,int k,int l,int r) {if(lr)return l;int mid (lr)1;if(T[T[pr].l].num-T[T[pl].l].numk) return ask(T[pl].l,T[pr].l,k,l,mid);else return ask(T[pl].r, T[pr].r,k-(T[T[pr].l].num-T[T[pl].l].num),mid1,r);
}
int main() {scanf(%d%d,n,m);rep(i,1,n)scanf(%lld,a[i].v),a[i].idi;sort(a1,a1n,cmp);rep(i,1,n)fid[a[i].id]i;rep(i,1,n)root[i]root[i-1],ins(root[i],fid[i],1,n);rep(i,1,m) {int l,r,k;scanf(%d%d%d,l,r,k);printf(%lld\n,a[ask(root[l-1],root[r],k,1,n)]);}return 0;
}BZOJ1901 题意动态区间查询 k-th number思路利用静态主席树思想维护权值线段树的前缀和而本题要维护动态前缀和那就可以想到利用树状数组维护动态前缀和。实现实现单点修改操作主席树的关键 - 保存历史版本所以显然不能在已经建好的树上操作。需要新开一个节点作为这个位置新的根在这个位置原来的位置上加一条新链。这个操作我们在实现静态前缀和的时候已经掌握了。前缀和时第i棵树是由第i-1棵树修改得到的而修改操作中新的这棵树是由它原先这个位置的值修改得到的。他们的本质都是修改操作。实现动态前缀和T[i]表示树状数组中的下表为i代表的区间。利用主席树维护每个位置前缀和利用树状数组来完成//bzoj1901 ac
#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
#define mem(W) memset(W,0,sizeof(W))
const int N 6e45;
const int M 1e45;
inline int read() {char cgetchar(); int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
int n,m,a[N];
vectorint v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;}
struct node{int l,r,k;bool opt;} A[M];
struct tree{int l,r,num;}T[N*200];
int root[N],tot;
void ins(int rt,int pre,int p,int l,int r,int d) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,l,mid,d);else ins(T[rt].r,T[pre].r,p,mid1,r,d);
}
void update(int p,int v) {for(int ip;in;i(i-i)) ins(root[i],root[i],id(a[p]),1,num,-1);for(int ip;in;i(i-i)) ins(root[i],root[i],id(v),1,num,1);a[p]v;
}
int L[N],R[N],cntl,cntr;
int qury(int l,int r,int k) {if(lr)return l;int mid(lr)1,sum0;rep(i,1,cntr) sumT[T[R[i]].l].num;rep(i,1,cntl) sum-T[T[L[i]].l].num;if(ksum) {rep(i,1,cntl) L[i]T[L[i]].l;rep(i,1,cntr) R[i]T[R[i]].l;return qury(l,mid,k);}else {rep(i,1,cntl) L[i]T[L[i]].r;rep(i,1,cntr) R[i]T[R[i]].r;return qury(mid1,r,k-sum);}
}
int main() {int K;scanf(%d,K);while(K--) {char s[5];scanf(%d%d,n,m); v.clear(); tot0; mem(root);mem(T);rep(i,1,n) scanf(%d,ai), v.pb(a[i]);rep(i,1,m) {scanf( %s,s);if(s[0]Q)A[i].opt1,scanf(%d%d%d,A[i].l,A[i].r,A[i].k);else A[i].opt0,scanf(%d%d,A[i].l,A[i].r),v.pb(A[i].r);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());num v.size();rep(i,1,n) for(int ji;jn;j(j(-j))) ins(root[j],root[j],id(a[i]),1,num,1);rep(ti,1,m) {if(A[ti].opt) {cntlcntr0;for(int iA[ti].l-1;i;i-(i(-i))) L[cntl]root[i];for(int iA[ti].r;i;i-(i(-i))) R[cntr]root[i];printf(%d\n,v[qury(1,num,A[ti].k)-1]);}elseupdate(A[ti].l,A[ti].r);}}return 0;
} ZOJ2112 题意与BZOJ1901相同动态区间查询 k-th number内存限制思路如果用上题的做法内存无法接受。那么思考有什么地方可以减少节点的数量。注意到一开始读入的n个数完全可以与后面的操作独立开一颗静态的主席树一颗用来修改查询时将两棵树的信息合并即可。这样这n棵数的空间复杂度少了一个树状数组的log//bzoj1901 ac
//zoj2112 ac
#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
#define mem(W) memset(W,0,sizeof(W))
const int N 6e45;
const int M 1e45;
inline int read() {char cgetchar(); int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
int n,m,a[N];
vectorint v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;}
struct node{int l,r,k;bool opt;} A[M];
struct tree{int l,r,num;}T[N*32];
int root[N],root0[N],tot;
void ins(int rt,int pre,int p,int l,int r,int d) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,l,mid,d);else ins(T[rt].r,T[pre].r,p,mid1,r,d);
}
void update(int p,int v) {for(int ip;in;i(i-i)) ins(root[i],root[i],id(a[p]),1,num,-1);for(int ip;in;i(i-i)) ins(root[i],root[i],id(v),1,num,1);a[p]v;
}
int L[N],R[N],cntl,cntr;
int qury(int l,int r,int ls,int rs,int k) {if(lr)return l;int mid(lr)1,sum0;rep(i,1,cntr) sumT[T[R[i]].l].num;rep(i,1,cntl) sum-T[T[L[i]].l].num;sum (T[T[rs].l].num-T[T[ls].l].num);if(ksum) {rep(i,1,cntl) L[i]T[L[i]].l;rep(i,1,cntr) R[i]T[R[i]].l;return qury(l,mid,T[ls].l,T[rs].l,k);}else {rep(i,1,cntl) L[i]T[L[i]].r;rep(i,1,cntr) R[i]T[R[i]].r;return qury(mid1,r,T[ls].r,T[rs].r,k-sum);}
}
int main() {int K;scanf(%d,K);while(K--) {char s[5];scanf(%d%d,n,m); v.clear(); tot0; mem(root);mem(T);rep(i,1,n) scanf(%d,ai), v.pb(a[i]);rep(i,1,m) {scanf( %s,s);if(s[0]Q)A[i].opt1,scanf(%d%d%d,A[i].l,A[i].r,A[i].k);else A[i].opt0,scanf(%d%d,A[i].l,A[i].r),v.pb(A[i].r);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());num v.size();rep(i,1,n) root0[i]root0[i-1],ins(root0[i],root0[i],id(a[i]),1,num,1);rep(ti,1,m) {if(A[ti].opt) {cntlcntr0;for(int iA[ti].l-1;i;i-(i(-i))) L[cntl]root[i];for(int iA[ti].r;i;i-(i(-i))) R[cntr]root[i];printf(%d\n,v[qury(1,num,root0[A[ti].l-1],root0[A[ti].r],A[ti].k)-1]);}elseupdate(A[ti].l,A[ti].r);}}return 0;
} 洛谷P3567 题意静态区间查询出现大于(r-l1)/2次的数。思路出现超过(r-l1)/2次的数至多有一个所以直接在静态主席树上查询区间内大于(r-l1)/2的位置即可与静态区间第k大的区别就是递归到右边时不修改k值#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
typedef long long ll;
const int N 500000100;
using namespace std;
int n,m,a[N];
struct chair_tree{int l,r,num;}T[N*30];
int root[N],tot;
void ins(int rt,int pre,int p,int d,int l,int r) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid (lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);
}
int ask(int rtl,int rtr,int l,int r,int X) {if(lr) return l;int mid (lr)1;if((T[T[rtr].l].num-T[T[rtl].l].num)*2X) return ask(T[rtl].l,T[rtr].l,l,mid,X);else if((T[T[rtr].r].num-T[T[rtl].r].num)*2X) return ask(T[rtl].r,T[rtr].r,mid1,r,X);else return 0;
}
int main() {scanf(%d%d,n,m);rep(i,1,n)scanf(%d,a[i]);rep(i,1,n)ins(root[i],root[i-1],a[i],1,1,n);rep(i,1,m) {int l,r;scanf(%d%d,l,r);printf(%d\n,ask(root[l-1],root[r],1,n,r-l1));}return 0;
} BZOJ2588 题意无修改树上查询路径上的第k大思路考虑如何树上主席树对每个从根节点延伸出的链建前缀的主席树。那么这条路径上就是\(u的值 v的值 - lca(u,v)的值 - fa[lca(u,v)]的值\), 其他与静态区间第k大一致。lca求法倍增5260 ms树剖3900 ms倍增lca #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
typedef long long ll;
const int N 1e5 100;
using namespace std;
int n,m,a[N];
vectorint v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;}
struct edge{int e,nxt;}E[N1];
int h[N],cc;
void add(int u,int v) {cc;E[cc].ev;E[cc].nxth[u];h[u]cc;
}
int fa[N][20],dep[N];
int lca(int u,int v) {if(dep[u]dep[v])swap(u,v);for(int i17;i0;--i)if(dep[fa[u][i]]dep[v])ufa[u][i];if(uv)return u;for(int i17;i0;--i) {if(fa[v][i]!fa[u][i])vfa[v][i],ufa[u][i];}return fa[v][0];
}
struct chair_tree{int l,r,num;}T[N*20];
int root[N], tot;
void ins(int rt,int pre,int p,int d,int l,int r) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);
}
int vis[N];
void build_T() {queueint q;q.push(0);vis[0]1;dep[0]0;while(!q.empty()) {int uq.front();q.pop();for(int i1;i17;i) fa[u][i]fa[fa[u][i-1]][i-1];for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(!vis[v]) {vis[v]1;fa[v][0]u;dep[v]dep[u]1;ins(root[v],root[u],id(a[v]),1,1,num);q.push(v);}}}
}
int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {if(lr) return l;int mid(lr)1,sum0;sum T[T[ur].l].num - T[T[lcar].l].num T[T[vr].l].num - T[T[lcafr].l].num;if(sumk) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid1,r);
}
int main() {scanf(%d%d,n,m);rep(i,1,n) scanf(%d,a[i]),v.pb(a[i]);sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());num v.size();memset(h,-1,sizeof(h));rep(i,1,n-1) {int u,v;scanf(%d%d,u,v);add(u,v),add(v,u);}a[0]0; add(0,1),add(1,0);build_T();int lastans0;rep(ti,1,m) {int x,y,k;scanf(%d%d%d,x,y,k);x^lastans;lastans v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)][0]],k,1,num)-1];printf(%d\n,lastans);}return 0;
} 树剖lca #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
typedef long long ll;
const int N 1e5 100;
using namespace std;
int n,m,a[N];
vectorint v;
int num;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;}
struct chair_tree{int l,r,num;}T[N*50];
int root[N], tot;
void ins(int rt,int pre,int p,int d,int l,int r) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);
}struct edge{int e,nxt;}E[N1];
int h[N],cc;
void add(int u,int v) {cc;E[cc].ev;E[cc].nxth[u];h[u]cc;
}
int dep[N],fa[N],son[N],sz[N],top[N];
void dfs1(int u,int pre,int d) {dep[u]d;fa[u]pre;sz[u]1;for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!pre) {ins(root[v],root[u],id(a[v]),1,1,num);dfs1(v,u,d1);sz[u]sz[v];if(son[u]-1||sz[v]sz[son[u]]) son[u]v;}}
}
void dfs2(int u,int sp) {top[u]sp;if(son[u]-1)return;dfs2(son[u],sp);for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!fa[u]v!son[u])dfs2(v,v);}
}
void init() {memset(son,-1,sizeof(son));dfs1(0,-1,1);dfs2(0,0);
}
int lca(int u,int v) {while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);return u;
}
int ask(int ur,int vr,int lcar,int lcafr,int k,int l,int r) {if(lr) return l;int mid(lr)1,sum0;sum T[T[ur].l].num - T[T[lcar].l].num T[T[vr].l].num - T[T[lcafr].l].num;if(sumk) return ask(T[ur].l,T[vr].l,T[lcar].l,T[lcafr].l,k,l,mid);else return ask(T[ur].r,T[vr].r,T[lcar].r,T[lcafr].r,k-sum,mid1,r);
}
int main() {scanf(%d%d,n,m);rep(i,1,n) scanf(%d,a[i]),v.pb(a[i]);sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());num v.size();memset(h,-1,sizeof(h));rep(i,1,n-1) {int u,v;scanf(%d%d,u,v);add(u,v),add(v,u);}a[0]0; add(0,1),add(1,0);init();int lastans0;rep(ti,1,m) {int x,y,k;scanf(%d%d%d,x,y,k);x^lastans;lastans v[ask(root[x],root[y],root[lca(x,y)],root[fa[lca(x,y)]],k,1,num)-1];if(ti!m)printf(%d\n,lastans);else printf(%d,lastans);}return 0;
}洛谷P4175 题意带修改树上查询路径上的第k大思路1在前一题的基础上考虑如何修改。当一个节点更新之后受影响的只有它的子树处理dfs序对于节点i相当于要修改\([ L[i],R[i] ]\)这个区间的值树状数组差分实现区间修改单点查询。询问方法看大佬Blog都是直接将[1,L[i]]当作树上根到节点i的前缀套用常规静态的方法。讲道理感觉很奇怪。。。但还是过了思路2把修改改成单点修改树剖的做法也可以过这个正确性很显然了。做法1 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
typedef long long ll;
inline int read() {char cgetchar();int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
const int N 1e5 100;
struct Q{int a,b,k;}q[N];
struct edge{int e,nxt;}E[N1];
int h[N],cc;
void add(int u,int v) {cc;E[cc].ev;E[cc].nxth[u];h[u]cc;}
int n,m,a[N];
vectorint mp;
int num;
int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()1;}struct chiarman{int l,r,num;}T[N*200];
int tot,rt[N],rtc[N];
void ins(int rt,int pre,int p,int d,int l,int r) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);
}int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos;
void dfs1(int u,int pre,int d) {dep[u]d;fa[u]pre;sz[u]1;for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!pre) {dfs1(v,u,d1);sz[u]sz[v];if(son[u]-1||sz[v]sz[son[u]]) son[u]v;}}
}
void dfs2(int u,int sp) {top[u]sp;L[u]tid[u]pos;if(son[u]-1)return;dfs2(son[u],sp);for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!fa[u]v!son[u])dfs2(v,v);}R[u]pos;
}
void init_tp() {memset(son,-1,sizeof(son));dfs1(1,0,1);dfs2(1,1);
}
int lca(int u,int v) {while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);return u;
}void build(int u){if(u-1) return;ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);build(son[u]);for(int ih[u];~i;iE[i].nxt)if(E[i].e!fa[u]E[i].e!son[u]) build(E[i].e);
}void B_add(int x,int p,int d){for(int ix;ipos;i(i-i)) ins(rtc[i],rtc[i],p,d,1,num);
}vectorint A,B;
int ck(int k) {int sum0;rep(i,0,A.size()-1)sumT[A[i]].num;rep(i,0,B.size()-1)sum-T[B[i]].num;return (sumk);
}
int qury(int l,int r,int k) {if(lr)return l;int mid(lr)1,sum0;rep(i,0,A.size()-1)sumT[T[A[i]].r].num;rep(i,0,B.size()-1)sum-T[T[B[i]].r].num;if(sumk) {rep(i,0,A.size()-1)A[i]T[A[i]].r;rep(i,0,B.size()-1)B[i]T[B[i]].r;return qury(mid1,r,k);}else {rep(i,0,A.size()-1)A[i]T[A[i]].l;rep(i,0,B.size()-1)B[i]T[B[i]].l;return qury(l,mid,k-sum);}
}
int cal() {int sum0;rep(i,0,A.size()-1)sumT[T[A[i]].r].num;rep(i,0,B.size()-1)sum-T[T[B[i]].r].num;return sum;
}
void chai(int u,int v) {while(top[u]!top[v]) {if(dep[top[u]]dep[top[v]]) swap(u,v);for(int itid[u];i;i-(i-i))A.pb(rtc[i]);for(int itid[top[u]]-1;i;i-(i-i))B.pb(rtc[i]);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);for(int itid[v];i;i-(i-i))A.pb(rtc[i]);for(int itid[u]-1;i;i-(i-i))B.pb(rtc[i]);return ;
}void ask(int u,int v,int k) {int plca(u,v);A.clear();B.clear();A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);chai(u,v);if(!ck(k)) {puts(invalid request!);return;}printf(%d\n,mp[qury(1,num,k)-1]);return;
}
int main() {scanf(%d%d,n,m);memset(h,-1,sizeof(h));memset(son,-1,sizeof(son));rep(i,1,n) a[i] read(), mp.pb(a[i]);rep(i,1,n-1) {int uread(),vread();add(u,v),add(v,u);}rep(i,1,m) {q[i].kread(),q[i].aread(),q[i].bread();if(q[i].k0)mp.pb(q[i].b);}sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());num mp.size();init_tp();build(1);rep(i,1,m) {if(q[i].k0) {B_add(tid[q[i].a],id(a[q[i].a]),-1);a[q[i].a]q[i].b;B_add(tid[q[i].a],id(a[q[i].a]),1);}else {ask(q[i].a,q[i].b,q[i].k);}}return 0;
} 做法2 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
typedef long long ll;
inline int read() {char cgetchar();int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
const int N 1e5 100;
struct Q{int a,b,k;}q[N];
struct edge{int e,nxt;}E[N1];
int h[N],cc;
void add(int u,int v) {cc;E[cc].ev;E[cc].nxth[u];h[u]cc;}
int n,m,a[N];
vectorint mp;
int num;
int id(int x){return lower_bound(mp.begin(),mp.end(),x)-mp.begin()1;}struct chiarman{int l,r,num;}T[N*200];
int tot,rt[N],rtc[N];
void ins(int rt,int pre,int p,int d,int l,int r) {rttot;T[rt]T[pre];T[rt].numd;if(lr)return;int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);
}int dep[N],fa[N],son[N],sz[N],top[N],tid[N],L[N],R[N],pos;
void dfs1(int u,int pre,int d) {dep[u]d;fa[u]pre;sz[u]1;for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!pre) {dfs1(v,u,d1);sz[u]sz[v];if(son[u]-1||sz[v]sz[son[u]]) son[u]v;}}
}
void dfs2(int u,int sp) {top[u]sp;L[u]tid[u]pos;if(son[u]-1)return;dfs2(son[u],sp);for(int ih[u];~i;iE[i].nxt) {int vE[i].e;if(v!fa[u]v!son[u])dfs2(v,v);}R[u]pos;
}
void init_tp() {memset(son,-1,sizeof(son));dfs1(1,0,1);dfs2(1,1);
}
int lca(int u,int v) {while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])swap(u,v);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);return u;
}void build(int u){if(u-1) return;ins(rt[u],rt[fa[u]],id(a[u]),1,1,num);build(son[u]);for(int ih[u];~i;iE[i].nxt)if(E[i].e!fa[u]E[i].e!son[u]) build(E[i].e);
}void B_add(int x,int p,int d){for(int ix;ipos;i(i-i)) ins(rtc[i],rtc[i],p,d,1,num);
}vectorint A,B;
int ck(int k) {int sum0;rep(i,0,A.size()-1)sumT[A[i]].num;rep(i,0,B.size()-1)sum-T[B[i]].num;return (sumk);
}
int qury(int l,int r,int k) {if(lr)return l;int mid(lr)1,sum0;rep(i,0,A.size()-1)sumT[T[A[i]].r].num;rep(i,0,B.size()-1)sum-T[T[B[i]].r].num;if(sumk) {rep(i,0,A.size()-1)A[i]T[A[i]].r;rep(i,0,B.size()-1)B[i]T[B[i]].r;return qury(mid1,r,k);}else {rep(i,0,A.size()-1)A[i]T[A[i]].l;rep(i,0,B.size()-1)B[i]T[B[i]].l;return qury(l,mid,k-sum);}
}
int cal() {int sum0;rep(i,0,A.size()-1)sumT[T[A[i]].r].num;rep(i,0,B.size()-1)sum-T[T[B[i]].r].num;return sum;
}
void chai(int u,int v) {while(top[u]!top[v]) {if(dep[top[u]]dep[top[v]]) swap(u,v);for(int itid[u];i;i-(i-i))A.pb(rtc[i]);for(int itid[top[u]]-1;i;i-(i-i))B.pb(rtc[i]);ufa[top[u]];}if(dep[u]dep[v])swap(u,v);for(int itid[v];i;i-(i-i))A.pb(rtc[i]);for(int itid[u]-1;i;i-(i-i))B.pb(rtc[i]);return ;
}void ask(int u,int v,int k) {int plca(u,v);A.clear();B.clear();A.pb(rt[u]),A.pb(rt[v]),B.pb(rt[p]),B.pb(rt[fa[p]]);chai(u,v);if(!ck(k)) {puts(invalid request!);return;}printf(%d\n,mp[qury(1,num,k)-1]);return;
}
int main() {scanf(%d%d,n,m);memset(h,-1,sizeof(h));memset(son,-1,sizeof(son));rep(i,1,n) a[i] read(), mp.pb(a[i]);rep(i,1,n-1) {int uread(),vread();add(u,v),add(v,u);}rep(i,1,m) {q[i].kread(),q[i].aread(),q[i].bread();if(q[i].k0)mp.pb(q[i].b);}sort(mp.begin(),mp.end()); mp.erase(unique(mp.begin(),mp.end()),mp.end());num mp.size();init_tp();build(1);rep(i,1,m) {if(q[i].k0) {B_add(tid[q[i].a],id(a[q[i].a]),-1);a[q[i].a]q[i].b;B_add(tid[q[i].a],id(a[q[i].a]),1);}else {ask(q[i].a,q[i].b,q[i].k);}}return 0;
}BZOJ2212 题意现在有一棵二叉树所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换使得最终所有叶子节点的权值按照遍历序写出来逆序对个数最少。思路动态开点给每个叶子节点开一颗权值线段树自底向上合并线段树合并的过程中通过左右子树的权值线段树计算逆序数。线段树合并及复杂度分析大佬的Blog#include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
typedef long long ll;
const int N 8000010;
using namespace std;
int n,rt;
struct tr{int l,r,num;}tree[N],T[N];
int cc,tot,root[N];
void build(int rt) {rt cc;int x;scanf(%d,x);if(x) tree[rt].numx;else build(tree[rt].l),build(tree[rt].r);
}
void ins(int rt,int pre,int p,int d,int l,int r){rttot;T[rt]T[pre];T[rt].numd;if(lr){T[rt].num1;return;}int mid(lr)1;if(pmid) ins(T[rt].l,T[pre].l,p,d,l,mid);else ins(T[rt].r,T[pre].r,p,d,mid1,r);T[rt].num T[T[rt].l].num T[T[rt].r].num;
}
ll ans1,ans2,ans;
int merge(int x,int y) {if(!x)return y;if(!y)return x;ans1 1LL*T[T[x].l].num*T[T[y].r].num;ans2 1LL*T[T[x].r].num*T[T[y].l].num;T[x].l merge(T[x].l,T[y].l);T[x].r merge(T[x].r,T[y].r);T[x].num T[T[x].l].num T[T[x].r].num;return x;
}
void solve(int rt) {if(tree[rt].num) return;solve(tree[rt].l),solve(tree[rt].r);ans1ans20;root[rt] merge(root[tree[rt].l],root[tree[rt].r]);ansmin(ans1,ans2);
}
int main() {scanf(%d,n);build(rt);rep(i,1,cc)if(tree[i].num)ins(root[i],root[i],tree[i].num,1,1,n);solve(rt);printf(%lld\n,ans);return 0;
}这个专题就先到这了。。。 转载于:https://www.cnblogs.com/RRRR-wys/p/9211634.html
