【BZOJ】1146: [CTSC2008]网络管理Network（树链剖分+线段树套平衡树+二分 / dfs序+树状数组+主席树）

http://www.lydsy.com/JudgeOnline/problem.php?id=1146

第一种做法（时间太感人）：

第二种做法（rank5，好开心）

================================8-20===============================

这题我真的逗了，调了一下午，疯狂造数据，始终找不到错。

后来发现自己sb了，更新那里没有打id，直接套上u了。我。。。。

调了一下午啊！一下午的时光啊！本来说好中午A掉去学习第二种做法，噗

好吧，现在第一种做法是hld+seg+bst+二分，常数巨大，log^4级别，目前只会这种。

树剖后仍然用线段树维护dfs序区间，然后在每个区间建一颗平衡树，我用treap，（这题找最大啊，，，囧，并且要注意，这里的rank是比他大的数量，so，我们在二分时判断要判断一个范围，即要加上它重叠的数量，这点自己调试的时候找出来了）

我们将路径放进一个池子里，然后累计排名就行了。

时间很感人啊。

（希望以后不要犯这种sb错了，唉，太逗。）

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define dbg(x) cout << #x << "=" << x << endl
#define read(x) x=getint()
#define rdm(u) for(int i=ihead[u]; i; i=e[i].next)
#define lc x<<1
#define rc x<<1|1
#define lson l, m, lc
#define rson m+1, r, rc
#define MID (l+r)>>1
inline const int getint() { char c=getchar(); int ret=0, k=1; for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }
const int N=80010, oo=~0u>>1;
int n, q, ihead[N], brr[N], arr[N], cnt, bak, flg, L, R, same;
int fa[N], top[N], son[N], dep[N], sz[N], id[N], tot, num;
struct Ed { int to, next; }e[N<<1];
inline void add(const int &u, const int &v) {
	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;
	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;
}

struct node* null;
struct node {
	node* ch[2]; int wei, key, sz, cnt;
	void pushup() { sz=ch[0]->sz+ch[1]->sz+cnt; }
	node(int _w=0, int _sz=1, int _cnt=1) : key(_w), sz(_sz), cnt(_cnt) {
		ch[0]=ch[1]=null; wei=rand();
	}
}*root[N*50], *nd[N*50];
inline void rot(node* &x, const bool d) {
	node* t=x->ch[!d]; x->ch[!d]=t->ch[d]; t->ch[d]=x;
	x->pushup(); t->pushup();
	x=t;
}
void insert(node* &x, const int &key) {
	if(x==null) { x=new node(key); return; }
	if(key==x->key) { ++x->cnt; ++x->sz; return; }
	bool d=key>x->key;
	insert(x->ch[d], key);
	if(x->wei>x->ch[d]->wei) rot(x, !d);
	x->pushup();
}
void remove(node* &x, const int &key) {
	if(x==null) return;
	bool d=key>x->key;
	if(key==x->key) {
		if(x->cnt>1) { --x->cnt; --x->sz; return; }
		d=x->ch[0]->wei > x->ch[1]->wei;
		if(x->ch[d]==null) {
			delete x;
			x=null;
			return;
		}
		rot(x, !d);
		remove(x->ch[!d], key);
	}
	else remove(x->ch[d], key);
	x->pushup();
}
inline int rank(node* x, const int &key) {
	int ret=0, s;
	while(x!=null) {
		s=x->ch[1]->sz + x->cnt;
		if(key==x->key) same+=x->cnt;
		if(key<x->key) ret+=s, x=x->ch[0];
		else x=x->ch[1];
	}
	return ret;
}
void build(const int &l, const int &r, const int &x) {
	if(l==r) { root[x]=new node(brr[l]); return; }
	int m=MID;
	build(lson); build(rson);
	root[x]=new node(brr[l]);
	for(int i=l+1; i<=r; ++i) insert(root[x], brr[i]);
}
void update(const int &l, const int &r, const int &x) {
	if(l==r) {
		remove(root[x], bak);
		insert(root[x], flg);
		return;
	}
	int m=MID;
	remove(root[x], bak);
	insert(root[x], flg);
	if(L<=m) update(lson); if(m<R) update(rson);
}
void query(const int &l, const int &r, const int &x) {
	if(L<=l && r<=R) { nd[++num]=root[x]; return; }
	int m=MID;
	if(L<=m) query(lson);
	if(m<R) query(rson);
}
void dfs1(const int &u) {
	sz[u]=1; int v;
	rdm(u) if(fa[u]!=(v=e[i].to)) {
		fa[v]=u; dep[v]=dep[u]+1;
		dfs1(v);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(const int &u, const int &tp) {
	id[u]=++tot; top[u]=tp; brr[tot]=arr[u];
	if(son[u]) dfs2(son[u], tp);
	rdm(u) if(fa[u]!=e[i].to && son[u]!=e[i].to) dfs2(e[i].to, e[i].to);
}
void getrange(int x, int y) {
	num=0;
	int fx=top[x], fy=top[y];
	while(fx!=fy) {
		if(dep[fx]<dep[fy]) { swap(x, y); swap(fx, fy); }
		L=id[fx], R=id[x];
		query(1, n, 1);
		x=fa[fx]; fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x, y);
	L=id[x], R=id[y];
	query(1, n, 1);
}
int getrank(const int &key) {
	int ret=0; same=0;
	for(int i=1; i<=num; ++i) ret+=rank(nd[i], key);
	return ret;
}
int getans(int x, int y, int k) {
	getrange(x, y);
	node* rt; int l=oo+1, r=oo, s=0;
	for(int i=1; i<=num; ++i) s+=nd[i]->sz;
	if(s<k) return l;
	for(int i=1; i<=num; ++i) {
		rt=nd[i];
		while(rt!=null) {
			if(rt->key<l) { rt=rt->ch[1]; continue; }
			if(rt->key>r) { rt=rt->ch[0]; continue; }
			s=getrank(rt->key);
			if(s+1<=k && k<=s+same)  return rt->key;  //这里要注意
			if(s+same>k) { l=rt->key; rt=rt->ch[1]; }
			else { r=rt->key; rt=rt->ch[0]; }
		}
	}
	return l;
}
int main() {
	null=new node(0, 0, 0); null->wei=oo;
	read(n); read(q);
	int u, v, k, ans;
	for(int i=1; i<=n; ++i) read(arr[i]);
	for(int i=1; i<n; ++i) { read(u); read(v); add(u, v); }
	dfs1(1); dfs2(1, 1); build(1, n, 1);
	while(q--) {
		read(k); read(u); read(v);
		if(!k) {
			bak=arr[u]; flg=arr[u]=v;
			L=R=id[u];
			update(1, n, 1);
		}
		else {
			ans=getans(u, v, k);
			if(ans==oo+1) puts("invalid request!");
			else printf("%d\n", ans);
		}
	}
	return 0;
}

===============================8-22============================

学习了主席树和dfs序还有lca后，终于来a这题了。

很爽。真的很爽。

代码简短，而且飞快，排到了rank5，而且这次写程序+调试只用了1小时多！！！！！！

巨大的进步，加油！

说说怎么做吧。

一开始看到dfs序很神奇的，其实很简单。

我们可以知道，从某节点x遍历下去的子树，他们的顺序一定是连续的（因为是dfs）

所以我们可以得知，如果用树状数组来维护的话，那么就要改变它所有的子树。

假设没有修改操作，那么返回这题了http://www.cnblogs.com/iwtwiioi/p/3929098.html

恩，我们来想怎么解决这个修改问题。

首先我们知道，主席树是根据前缀思想维护1-x的一种线段树，我们用上边那题（下边均称为COT）的做法，在每个节点都建到根的主席树。

那么假设无修改，那么询问u到v的路径第k大的答案就在 u到根的主席树 + v到根的主席树 - lca(u, v)到根的主席树 - fa[lca(u, v)]到根的主席树 之中。

前缀区间用啥维护呢？恩！树状数组。

但是我们并不改变节点上的主席树的形态，并不在上边操作，也就是说，建好这些主席树后，就不操作他们了。

我们再开数组用来当树状数组，因为n个节点，自然我们维护1-n的信息，但是我们知道，dfs序在不同子树顺序当然是不同的。而我们需要做到在我们需要的区间内（一段连续的子树的dfs序）做操作。

我们来想想普通的树状数组吧。

操作都是 区间1-x (求和操作) 区间x-n (更新操作)

解决方案就是，再用前缀和思想，如果要求和 [l, r] 那么我们先求和 [1, r] 再减去 求和[1, l-1]

同理，更新的话，先更新[l, n] 再减去更新（即加上相反数） [r+1, n]

哈哈，问题得到解决。

1. 咱们用tarjan离线求出lca，并且求出dfs序，并且构造每个点的主席树
2. 咱们dfs出来的序在一定子树是连续的。
3. 咱们节点x改变，起相应的子树的树状数组也要改变
4. 咱们不在原来每个点的主席树操作
5. 咱们只在树状数组进行操作
6. 咱们求k大时将原来点的主席树和树状数组放到池子里，然后加加减减

问题完美解决！

需要注意：

1. 题目是求k大
2. 主席树开的空间很大，尽量开
3. 一些数组也要开到n的几倍

自己好好领悟！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i, n) for(int i=0; i<n; ++i)
#define for1(i, a, n) for(int i=a; i<=(n); ++i)
#define read(x) x=getint()
#define MID (l+r)>>1
#define rdm(u) for(int i=ihead[u]; i; i=e[i].next)
using namespace std;
inline const int getint() { char c=getchar(); int k=1, r=0; for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
const int N=80005;
struct ED { int to, next; } e[N<<1];
struct ND { int l, r, s; } t[N*80];
int ihead[N], root[N], c[N], cnt, tot, num, suml, sumr, n, m, lca[N], L[N<<2], R[N<<2], FF[N], LL[N], fa[N], p[N], a[N], ans[N+N], u[N], v[N], K[N];
bool vis[N];
vector<pair<int, int> > q[N];
inline void add(const int &u, const int &v) {
	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;
	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;
}
void update(const int &l, const int &r, int &pos, const int &key, const int &sz) {
	t[++tot]=t[pos]; pos=tot; t[pos].s+=sz;
	if(l==r) return;
	int m=MID;
	if(key<=m) update(l, m, t[pos].l, key, sz); else update(m+1, r, t[pos].r, key, sz);
}
int query(const int &l, const int &r, const int &k) {
	if(l==r) return l;
	int s=0, tt=0, m=MID;
	for1(i, 1, sumr) s+=t[t[R[i]].r].s, tt+=t[R[i]].s; //将池子里要加减的求和
	for1(i, 1, suml) s-=t[t[L[i]].r].s, tt-=t[L[i]].s;
	if(tt<k) return -1; //当数目不够时，自己可以算算
	if(k<=s) { //这里是求k大，不是k小！！！
		for1(i, 1, suml) L[i]=t[L[i]].r;
		for1(i, 1, sumr) R[i]=t[R[i]].r;
		return query(m+1, r, k);
	}
	else {
		for1(i, 1, suml) L[i]=t[L[i]].l;
		for1(i, 1, sumr) R[i]=t[R[i]].l;
		return query(l, m, k-s);
	}
}
inline void get(int x, const int &k) {
	if(k) { R[++sumr]=root[x]; for(x=FF[x]; x; x-=(x&-x)) R[++sumr]=c[x]; } //这里要注意，要加上原本信息，即root
	else  { L[++suml]=root[x]; for(x=FF[x]; x; x-=(x&-x)) L[++suml]=c[x]; }
}
inline void change(int x, const int &key, const int& k) {
	for(; x<=n; x+=(x&-x)) update(1, num, c[x], key, k);
}
int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }
void dfs(const int &x) {
	p[x]=x; root[x]=root[fa[x]]; update(1, num, root[x], a[x], 1);
	static int nm=0;
	FF[x]=++nm; //首次发现x的序
	rdm(x) if(fa[x]!=e[i].to) { fa[e[i].to]=x; dfs(e[i].to); p[e[i].to]=x; }
	LL[x]=nm; //遍历完x的所有子树后的序，那么这些子树的连续区间就是[FF[x], LL[x]]
	vis[x]=1;
	int t=q[x].size();
	rep(i, t) if(vis[q[x][i].first]) lca[q[x][i].second]=ifind(q[x][i].first);
}

int main() {
	read(n); read(m); int tt=0;
	for1(i, 1, n) { read(a[i]); ans[++tt]=a[i]; }
	rep(i, n-1) add(getint(), getint());
	for1(i, 1, m) {
		read(K[i]); read(u[i]); read(v[i]);
		if(K[i]) {
			q[u[i]].push_back(pair<int, int> (v[i], i));
			q[v[i]].push_back(pair<int, int> (u[i], i));
		}
		else ans[++tt]=v[i];
	}
	sort(ans+1, ans+1+tt); ans[tt+1]=1000000013; //离散
	for1(i, 1, tt) if(ans[i]!=ans[i+1]) ans[++num]=ans[i]; //将重叠的合并，缩短主席树的区间范围
	for1(i, 1, n) a[i]=lower_bound(ans+1, ans+1+num, a[i])-ans; //查找原来元素在ans域的位置，即主席树上对应的区间值
	dfs((n+1)>>1); //这里我们从中间遍历，防止爆栈（至于为什么，你自己画一条长链，你懂的）
	int out, x, y;
	for1(i, 1, m) {
		if(K[i]) {
			suml=sumr=0;
			get(u[i], 1); get(v[i], 1); //将u到根、v到根的原本信息（root）和修改信息（c）全部放到池子里
			get(lca[i], 0); get(fa[lca[i]], 0); //同上
			out=query(1, num, K[i]);
			if(out<=0) puts("invalid request!");
			else printf("%d\n", ans[out]);
		}
		else {
			x=u[i]; y=v[i];
			y=lower_bound(ans+1, ans+1+num, y)-ans; //求出修改的值在ans的位置
			change(FF[x], a[x], -1); change(LL[x]+1, a[x], 1); //首先将区间[FF[x], n]全部减去a[x]，然后将区间[LL[x]+1, n]全部加回a[x]
			change(FF[x], y, 1); change(LL[x]+1, y, -1); //同上
			a[x]=y;
		}
	}
	return 0;
}

---

Description

M 公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通 信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信 子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器 之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。作为M公司网络部门的一名实习员工，现在要求你编写一个简单的程序来 监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第k大的路由器 的延迟时间。【任务】 你的程序从输入文件中读入N个路由器和N-1条光缆的连接信息，每个路由器初始的数据交换延迟时间Ti，以及Q条询问（或状态改变）的信息。并依次处理这 Q条询问信息，它们可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查询某两个路由器a和b之间的路径上延迟第k大的路由器的延迟时间。

Input

第 一行为两个整数N和Q，分别表示路由器总数和询问的总数。第二行有N个整数，第i个数表示编号为i的路由器初始的数据延迟时间Ti。紧接着N-1行，每行 包含两个整数x和y。表示有一条光缆连接路由器x和路由器y。紧接着是Q行，每行三个整数k、a、b。如果k=0，则表示路由器a的状态发生了变化，它的 数据交换延迟时间由Ta变为b。如果k>0，则表示询问a到b的路径上所经过的所有路由器（包括a和b）中延迟第k大的路由器的延迟时间。注意a可 以等于b，此时路径上只有一个路由器。

Output

对于每一个第二种询问（k>0），输出一行。包含一个整数为相应的延迟时间。如果路径上的路由器不足k个，则输出信息“invalid request!”（全部小写不包含引号，两个单词之间有一个空格）。

Sample Input

5 5
5 1 2 3 4
3 1
2 1
4 3
5 3
2 4 5
0 1 2
2 2 3
2 1 4
3 3 5

Sample Output

3
2
2
invalid request!

HINT

10% 测试数据满足N<=8000,Q<=3000,

任意一个路由器在任何时刻都满足延迟时间小于10^8。对于所有询问满足0<=K<=N 。

Source