[BZOJ1146]CTSC2008網絡管理|樹上帶修改K大
樹上帶修改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 (ms1) {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<n;i++) {="" scanf("%d%d",&s,&e);="" add(s,e);add(e,s);="" }="" init();="" for="" (i="1;i<=n;i++) d=" " if="" maxq="max(maxq,y);else"" pre="" while="">
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[x]=size[last]+del;
lc[x]=rc[x]=0;
if (l==r) return x;
if (k<=mid) lc[x]=update(l,mid,lc[last],k,del),rc[x]=rc[last];else rc[x]=update(mid+1,r,rc[last],k,del),lc[x]=lc[last];
return x;
}
void dfs(int x)
{
fa[x]=x;L[x]=++tim;u[x]=0;
root[x]=update(1,tot,root[pre[x]],q[x],1);
for (int j=a[x];j;j=ed[j].next)
if (ed[j].e!=pre[x])
{
d[ed[j].e]=d[x]+1;pre[ed[j].e]=x;
dfs(ed[j].e);fa[ed[j].e]=x;
}
R[x]=tim;u[x]=1;
for (int j=h[x];j;j=ed[j].next)
if (u[ed[j].e]) lca[ed[j].xu]=getfa(ed[j].e);
}
void change(int x,int k,int del)
{
for (int i=x;i<=n;i+=lowbit(i)) c[i]=update(1,tot,c[i],k,del);
}
void get(int x,int kind)
{
for (int i=x;i;i-=lowbit(i)) use[++sum[kind]][kind]=c[i];
}
int calc(int kind)
{
int ans=0;
for (int i=1;i<=sum[kind];i++) ans+=size[rc[use[i][kind]]];
return ans;
}
void next(int kind,int dir)
{
for (int i=1;i<=sum[kind];i++) use[i][kind]=dir?rc[use[i][kind]]:lc[use[i][kind]];
}
void query(int p,int x,int y,int k)
{
if (d[x]+d[y]-2*d[p]+1>1;
now=size[rc[ux]]+calc(1)+size[rc[uy]]-2*(calc(0)+size[rc[up]]);
if (f)now+=(q[p]>mid);
if (now>=k)
{
next(1,1);next(0,1);ux=rc[ux];uy=rc[uy];up=rc[up];
l=mid+1;
}
else
{
next(1,0);next(0,0);ux=lc[ux];uy=lc[uy];up=lc[up];
if (q[p]>mid) f=false;
r=mid,k-=now;
}
}
printf("%d\n",newq[l]);
}
int main()
{
scanf("%d%d",&n,&Q);
for (i=1;i<=n;i++)
{
scanf("%d",&q[i]);
num[++cnt]=node(q[i],i);
a[i]=h[i]=c[i]=0;
}
for (i=1;in) y[num[i].yuan-n]=tot;else q[num[i].yuan]=tot;
}
d[(n+1)/2]=0;pre[(n+1)/2]=0;root[0]=0;lc[0]=rc[0]=0;size[0]=0;
dfs((n+1)/2);
for (i=1;i<=Q;i++)
if (k[i]) query(lca[i],x[i],y[i],k[i]);
else
{
change(L[x[i]],q[x[i]],-1);change(R[x[i]]+1,q[x[i]],1);
change(L[x[i]],y[i],1);change(R[x[i]]+1,y[i],-1);
q[x[i]]=y[i];
}
}
