【BZOJ 4196】[NOI2015] 软件包管理器

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4196

解题报告

考虑树链剖分
线段树部分只需要支持区间赋值,查询区间中1的个数
总的时间复杂度:$O(n \log ^ 2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 200009;

int n, m, head[N], nxt[N], to[N], beg[N], ot[N];
int fa[N], top[N], hvy[N], sz[N], dep[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

inline void DFS1(int w, int f) {
	fa[w] = f;
	dep[w] = dep[f] + 1;
	sz[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		DFS1(to[i], w);
		sz[w] += sz[to[i]];
		if (sz[to[i]] > sz[hvy[w]]) {
			hvy[w] = to[i];
		}
	}
}

inline void DFS2(int w, int t) {
	static int dfc = 0;
	beg[w] = ++dfc;
	top[w] = t;
	if (hvy[w]) {
		DFS2(hvy[w], t);
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			} 
		}
	}
	ot[w] = dfc;
}

class Segment_Tree{
int cnt, root, ch[M][2], sum[M], tag[M];
public:
	inline void init() {
		init(root, 1, n);
	}
	inline int install(int w) {
		int ret = 0, tmp;
		while (true) {
			int l = beg[top[w]], r = beg[w], len = r - l + 1;
			tmp = len - modify(root, 1, n, beg[top[w]], beg[w], 1);
			ret += tmp;
			if (fa[top[w]] != w && tmp) {
				w = fa[top[w]];
			} else {
				break;
			}
		} 
		return ret;
	}
	inline int uninstall(int w) {
		return modify(root, 1, n, beg[w], ot[w], -1);
	}
private:
	inline void init(int &w, int l, int r) {
		w = ++cnt;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			init(ch[w][0], l, mid - 1);
			init(ch[w][1], mid, r);
		}
	}
	inline void PushDown(int w, int l, int mid, int r) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			if (tag[w] == 1) {
				sum[ls] = mid - l;
				sum[rs] = r - mid + 1;
			} else {
				sum[ls] = sum[rs] = 0;
			}
			tag[ls] = tag[rs] = tag[w];
			tag[w] = 0;
		}
	}
	inline int modify(int w, int l, int r, int L, int R, int t) {
		if (L <= l && r <= R) {
			int ret = sum[w];
			sum[w] = t == -1? 0: r - l + 1;
			tag[w] = t;
			return ret;
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			PushDown(w, l, mid, r);
			if (L < mid) {
				ret += modify(ch[w][0], l, mid - 1, L, R, t);
			}
			if (mid <= R) {
				ret += modify(ch[w][1], mid, r, L, R, t);
			}
			sum[w] = sum[ch[w][1]] + sum[ch[w][0]];
			return ret;
		}
	}
}SGT;

int main() {
	freopen("manager.in", "r", stdin);
	freopen("manager.out", "w", stdout);
	n = read();
	for (int i = 2; i <= n; i++) {
		AddEdge(read() + 1, i);
	}
	DFS1(1, 1);
	DFS2(1, 1);
	SGT.init();
	m = read();
	char cmd[20];
	for (int i = 1; i <= m; i++) {
		scanf("%s", cmd + 1);
		if (cmd[1] == 'i') {
			printf("%d\n", SGT.install(read() + 1));
		} else {
			printf("%d\n", SGT.uninstall(read() + 1));
		}	
	}
	return 0;
}

【BZOJ 2402】陶陶的难题II

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2402

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度:$O(n \log^3 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

int n, head[N], nxt[N], to[N];
struct Point{
	double x, y;
	inline Point() {
	}
	inline Point(double a, double b):x(a), y(b) {
	}
	inline bool operator < (const Point &PP) const {
		return x < PP.x || (x == PP.x && y < PP.y);
	}
	inline bool operator == (const Point &PP) const {
		return x == PP.x && y == PP.y;
	}
 	inline Point operator - (const Point &PP) const {
		return Point(x - PP.x, y - PP.y);
	}
	inline double operator * (const Point &PP) {
		return x * PP.y - y * PP.x;
	}
	inline double slope() {
		return y / x;
	}
}d[N][2];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
	int num[N], root, ch[N][2];
	inline void init() {
		build(root, 1, n);	
	}
	inline void update(int l, int r, double a, double *mx) {
		query(root, 1, n, l, r, a, mx);
	}
private:
	inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
		if (L <= l && r <= R) {
			mx[0] = max(mx[0], cal(cvx[w][0], a));
			mx[1] = max(mx[1], cal(cvx[w][1], a));
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				query(ch[w][0], l, mid - 1, L, R, a, mx);
			}
			if (R >= mid) {
				query(ch[w][1], mid, r, L, R, a, mx);
			}
		}
	}
	inline double cal(const vector<Point> &que, double a) {
		int l = 0, r = que.size() - 1, mid, ret = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
				ret = mid; 
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -a * que[ret].x + que[ret].y;
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			cvx[w][0].push_back(d[num[l]][0]);
			cvx[w][1].push_back(d[num[l]][1]);
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			int ls = ch[w][0], rs = ch[w][1];
			cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
			cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
		}
	}
	inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
		vector<Point> cur, ret;
		for (int i = 0; i < (int)c1.size(); i++) {
			cur.push_back(c1[i]);
		}
		for (int i = 0; i < (int)c2.size(); i++) {
			cur.push_back(c2[i]);
		}
		sort(cur.begin(), cur.end());
		cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
		for (int i = 0; i < (int)cur.size(); i++) {
			while ((int)ret.size() > 1) {
				int idx = ret.size() - 1;
				if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
					ret.pop_back();
				} else {
					break;
				}
			}
			ret.push_back(cur[i]);
		}
		return ret;
	}
}SGT;
public:
	inline void init() {
		DFS1(1, 1);
		DFS2(1, 1);
		SGT.init();
	}	
	inline double query(int u, int v) {
		double l = 0, r = INF, ret = 0, mid;
		while (r - l > EPS) {
			mid = (l + r) * 0.5;
			if (judge(u, v, mid)) {
				ret = mid;
				l = mid;
			} else {
				r = mid;
			}
		}	
		return ret;
	}
private:
	inline bool judge(int u, int v, double a) {
		double mx[] = {-INF, -INF};
		while (top[u] != top[v]) {
			if (dep[top[u]] > dep[top[v]]) {
				SGT.update(idx[top[u]], idx[u], a, mx);
				u = fa[top[u]];
			} else {
				SGT.update(idx[top[v]], idx[v], a, mx);
				v = fa[top[v]];
			}
		}
		if (dep[u] > dep[v]) {
			SGT.update(idx[v], idx[u], a, mx);
		} else {
			SGT.update(idx[u], idx[v], a, mx);
		}
		return mx[0] + mx[1] > 0;
	}
	inline void DFS1(int w, int f) {
		fa[w] = f;
		sz[w] = 1;
		dep[w] = dep[f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != f) {
				DFS1(to[i], w);
				sz[w] += sz[to[i]];
				if (sz[to[i]] > sz[hvy[w]]) {
					hvy[w] = to[i];
				}
			}
		}
	}
	inline void DFS2(int w, int t) {
		static int dcnt = 0;
		SGT.num[idx[w] = ++dcnt] = w;
		top[w] = t;
		if (hvy[w]) {
			DFS2(hvy[w], t);
		}
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != fa[w] && to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			}
		}
	}
}HLD;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].y);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].y);
	}
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}

【BZOJ 3307】雨天的尾巴

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3307
神犇题解:http://blog.csdn.net/ww140142/article/details/48660513

解题报告

这题,搬到序列上大家都会啊
就是先把操作打成tag,扔到序列上
然后用线段树扫一遍,统计答案即可

当然线段树合并也很好写啊
也是先搞成tag,然后合并上去,顺便记录一下答案
时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;
const int G = 7000000;
const int INF = 1e9;

int n,m,dep[N],ans[N],fa[N][20];
int head[N],to[M],nxt[M];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f) {
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int u, int v) {
	if (dep[u]<dep[v]) swap(u, v);
	for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u = fa[u][j];
	if (u == v) return u;
	for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
	return fa[u][0];
}

class Segment_Tree{
	int cnt,ch[G][2],mx[G],id[G],root[N];
	public:
		inline void merge(int x, int y) {
			root[x] = Merge(root[x], root[y]);
		}
		inline void insert(int w, int p, int t) {
			insert(root[w], 1, INF, p, t);
		}
		inline int query(int w) {
			return mx[root[w]]? id[root[w]]: 0;
		}
	private:
		int Merge(int x, int y) {
			if (!x || !y) return x + y;
			if (!ch[x][0] && !ch[x][1]) {
				mx[x] += mx[y];
				return x;
			} else {
				ch[x][0] = Merge(ch[x][0], ch[y][0]);
				ch[x][1] = Merge(ch[x][1], ch[y][1]);
				if (mx[ch[x][0]] >= mx[ch[x][1]]) id[x] = id[ch[x][0]], mx[x] = mx[ch[x][0]];
				else id[x] = id[ch[x][1]], mx[x] = mx[ch[x][1]];
				return x;
			}
		}
		void insert(int &w, int l, int r, int p, int delta) {
			if (!w) w = ++cnt; 
			if (l == r) {
				mx[w] += delta; id[w] = l;
			} else {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, delta);
				else insert(ch[w][1], mid, r, p, delta);
				if (mx[ch[w][0]] >= mx[ch[w][1]]) id[w] = id[ch[w][0]], mx[w] = mx[ch[w][0]];
				else id[w] = id[ch[w][1]], mx[w] = mx[ch[w][1]];
			}
		}
}ST;

void solve(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			solve(to[i], w);
			ST.merge(w, to[i]);
		}
	}
	ans[w] = ST.query(w);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<n;i++) AddEdge(read(), read());
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca,c;i<=m;i++) {
		u = read(); v = read(); c = read();
		lca = LCA(u, v);
		ST.insert(u, c, 1);
		ST.insert(v, c, 1);
		ST.insert(lca, c, -1);
		if (lca-1) ST.insert(fa[lca][0], c, -1);		
	}
	solve(1, 1);
	for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

【BZOJ 4713】迷失的字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4713

解题报告

这题拿bitset搞一搞就好了
f[i]表示前缀匹配,g[i]表示后缀匹配
然后暴力更新
时间复杂度:$O(\frac{n^2}{64})$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int M = 16;
const int SGZ = 26;
const int N = 30000+9;

int head[N],nxt[N<<1],to[N<<1],col[N<<1],sz[N],hvy[N];
int n,m,tot,beg[N],ed[N],id[N],pool[M],top; char s[N];
bitset<N> vout,ans,ve,vis[SGZ],vs[SGZ],f[M],g[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}

void DFS1(int w, int f) {
	sz[w] = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS1(to[i], w);
			sz[w] += sz[to[i]];
			if (sz[hvy[w]]<sz[to[i]]) 
				hvy[w] = to[i];
		}
	}
}

inline void init(int w) {
	id[w] = pool[top--];
	f[id[w]].reset();
	g[id[w]] = ve;	
}

inline void solve(int x, int y, int c) {
	int ix = id[x], iy = id[y];
	f[iy] <<= 1; f[iy] &= vis; f[iy] |= vs;
	g[iy] = g[iy] & vis;
	vout |= g[iy];
	g[iy] >>= 1;
	ans |= f[ix] & g[iy];
	ans |= g[ix] & f[iy];
	f[ix] |= f[iy];
	g[ix] |= g[iy];
	pool[++top] = iy;
}

void DFS2(int w, int f) {
	if (hvy[w]) DFS2(hvy[w], w);
	init(w);
	for (int i=head[w];i;i=nxt[i]) if (to[i] == hvy[w]) 
		solve(w, hvy[w], col[i]);
	for (int i=head[w];i;i=nxt[i]) if (to[i] != hvy[w] && to[i] != f) 
		DFS2(to[i], w), solve(w, to[i], col[i]);
} 

int main() {
	for (int i=top=M-1;~i;i--) pool[i] = i;
	for (int i=n=read(),u,v;i>1;i--) {
		u = read(); v = read(); 
		scanf("%s",s);
		Add_Edge(u, v, s[0]-'a');
	}
	for (int i=m=read(),len;i;i--) {
		scanf("%s",s); len = strlen(s); 
		vs[s[0]-'a'][beg[m-i+1]=tot+1] = 1; 
		for (int j=0;j<len;j++) vis[s[j]-'a'][++tot] = 1;
		ve[ed[m-i+1]=tot] = 1; 
	}
	DFS1(1, 1); 
	DFS2(1, 1);
	for (int i=1,tag=0;i<=m;i++,tag=0) {
		if (vout[beg[i]]) tag = 1;
		for (int j=beg[i];j<=ed[i]&&!tag;j++) if (ans[j]) tag = 1;
		puts(tag?"YES":"NO");
	}
	return 0;
}

后记

这题似乎之前听谁说过有点分的做法?
不过想不起怎么做了 _(:з」∠)_
会的神犇可不可以给我讲一讲怎么做啊 QwQ

【UOJ 284】[Goodbye Bingshen] 快乐游戏鸡

相关链接

题目传送门:http://uoj.ac/problem/284
数据生成器:http://paste.ubuntu.com/23987506/
官方题解:http://vfleaking.blog.uoj.ac/blog/2292

解题报告

这题有一点不想写题解 _(:з」∠)_
UOJ的官方题解还是很清楚的吧?
那就偷懒不写辣!

值得一提的是,这题也是用链剖来强行优化复杂度
这个优化技巧已经多次在各种比赛中出现了
很多复杂度跟深度有关的题目都可以拿这货优化

另外,scPointer好劲啊!
都给UOJ出题了!
scPointer是我榜样!

Code

这份代码多了一个$log$
问题不是在链剖那里,而是线段树那里偷懒,多了一个二分

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;
const int M = 19;

int n,m,tot,head[N],to[N],nxt[N],sz[N],pos[N];
int fa[N][M],val[N][M],hvy[N],dep[N],Val[N];
vector<pair<int,int> > q[N];
LL vout[N],sum[N];

class Segment_Tree{
	int tag[N<<2],cnt;
	LL sum[N<<2],ans_tmp;
	public:
		inline void modify(int l, int r, int v) {
			modify(1, 1, n, l, r, v);
		}
		inline int query(int p) {
			query(1, 1, n, p);
			return ans_tmp;
		}
		inline LL GetSum(int l, int r) {
			ans_tmp = 0;
			GetSum(1, 1, n, l, r);
			return ans_tmp;
		}
	private:
		void push_down(int w, int l, int r) {
			tag[w<<1] = tag[(w<<1)+1] = tag[w];
			int mid = l + r + 1 >> 1;
			sum[w<<1] = (LL)(mid - l) * tag[w];
			sum[(w<<1)+1] = (LL)(r -mid + 1) * tag[w];
			tag[w] = 0;
		}
		void modify(int w, int l, int r, int L, int R, int v) {
			if (L <= l && r <= R) {
				tag[w] = v;
				sum[w] = (LL)(r - l + 1) * v; 
			} else {
				if (tag[w]) push_down(w, l, r);
				int mid = l + r + 1 >> 1;
				if (L < mid) modify(w<<1, l, mid-1, L, R, v);
				if (mid <= R) modify((w<<1)+1, mid, r, L, R, v);
				sum[w] = sum[w<<1] + sum[(w<<1)+1]; 
			}
		}
		void query(int w, int l, int r, int p) {
			if (tag[w] || l == r) {
				ans_tmp = tag[w];
				return;
			} else {
				int mid = l + r + 1 >> 1;
				if (p < mid) query(w<<1, l, mid - 1, p);
				else query((w<<1)+1, mid, r, p);
			}
		}	
		void GetSum(int w, int l, int r, int L, int R) {
			if (L <= l && r <= R) {
				ans_tmp += sum[w];
			} else {
				if (tag[w]) push_down(w, l, r);
				int mid = l + r + 1 >> 1;
				if (L < mid) GetSum(w<<1, l, mid-1, L, R);
				if (mid <= R) GetSum((w<<1)+1, mid, r, L, R);
			}
		}
}SEG;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS1(int w, int f) {
	sz[w] = 1; fa[w][0] = f; 
	dep[w] = dep[f] + 1;
	val[w][0] = Val[f];
	for (int i=head[w];i;i=nxt[i]) {
		DFS1(to[i], w);
		sz[w] = max(sz[w], sz[to[i]] + 1);
		if (sz[hvy[w]] < sz[to[i]]) 
			hvy[w] = to[i];
	}
}

inline int query(int x, int y) {
	int ret = 0; x = dep[x]; 
	for (int j=M-1;~j;j--) {
		if (dep[fa[y][j]] > x) {
			ret = max(ret, val[y][j]);
			y = fa[y][j];
		}  
	} 
	return ret;
}

inline int find(int l, int r, int v) {
	int ret = l, mid;
	while (l <= r) {
		mid = l + r >> 1; 
		if (SEG.query(mid) < v) ret = mid, l = mid + 1;
		else r = mid - 1;
	} 
	return ret + 1;
}

void DFS2(int w) {
	pos[w] = ++tot;
	if (hvy[w]) DFS2(hvy[w]);
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != hvy[w]) {
			DFS2(to[i]);
		}
	} 
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != hvy[w]) {
			for (int j=0,p,v;j<sz[to[i]];j++) {
				v = SEG.query(pos[to[i]]+j);
				if (SEG.query(pos[w]+j+1) >= v) continue;
				p = find(pos[w]+j-1, pos[w]+sz[w]-1, v); 
				SEG.modify(pos[w]+j+1, p-1, v);
			}
		}
	}
	for (int i=0,lim=q[w].size(),t,id,mx,p;i<lim;i++) {
		t = q[w][i].first; id = q[w][i].second;
		mx = query(w, t); 
		p = find(pos[w], pos[w]+sz[w]-1, mx) - pos[w]; 
		vout[id] = (LL)p * mx - (p?SEG.GetSum(pos[w], pos[w]+p-1):0LL) + dep[t] - dep[w];
	}
	int p = find(pos[w], pos[w]+sz[w]-1, Val[w]);
	SEG.modify(pos[w], p-1, Val[w]);
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) Val[i] = read();
	for (int i=2;i<=n;i++) Add_Edge(read(), i);
	m = read();
	for (int i=1,s,t;i<=m;i++) {
		s = read(); t = read();
		q[s].push_back(make_pair(t, i));
	}
	DFS1(1, 1);
	for (int j=1;j<M;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
			val[i][j] = max(val[i][j-1],val[fa[i][j-1]][j-1]);
		}
	}
	DFS2(1);
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 4543】[POI2014] Hotel加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4543
神犇题解Ⅰ:http://blog.csdn.net/u010600261/article/details/53576251
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/51278993

解题报告

设$f[i][j]$为到点$i$距离为$j$的点的个数
设$g[i][j]$表示一堆点到点$i$,各自距离均为$j$的对数
这样的话,我们就可以愉快地DP了,时间复杂度$O(n^2)$

现在将这颗树树链剖分,将重儿子重定义为子树深度最深的点
明显一个点的重儿子到这个点的转移可以直接将数组平移,这个用指针实现是$O(1)$的
现在考虑轻儿子,用轻儿子的数组去更新父亲节点的信息

这样看起来是$O(n^2)$的,但实际上这是$O(n)$的
考虑内存使用了多少:每一条重链的空间等于重链长度,所以空间复杂度为$O(n)$的
考虑每一个申请的空间,只会被用来更新所在重链的最上面那个点的父亲
也就是说每一个数组的单位,只会被访问一次,所以时间复杂度也是$O(n)$的啦!

另外值得一提的是,这种优化方式的普适性较强
除了这道题之外,我还在四道题里见到过这样的优化
比如:UOJ 284

【BZOJ 4712】洪水

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4712
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/6006305.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/53454323

解题报告

考虑每一个节点保存三个值

  1. $w(i)$ 表示第i个点自己的权值
  2. $f(i) = \sum\limits_{j \in son(i)} {d(j)} $
  3. $d(i) = \min (w(i),f(i))$

显然 $d(i)$ 就是答案
于是我们只需要考虑维护 $f(i)$ 即可

考虑每一次修改操作
其一定是改变了到根节点的路径上连续一个区间的 $f(i)$
这个连续的区间满足 $f(i) + delta < w(i)$ 于是可以直接用树链剖分搞区间加就可以了

现在考虑复杂度:

因为 $f(i)$ 是不减的,所以如果一个点的 $f(i)$ 大于了 $w(i)$ 那么便会一直大下去
初始每一个点会贡献一次暴力修改,每一次修改操作也会贡献一次暴力修改

于是均摊下来,单次操作的暴力修改次数就是 $O(1)$ 的了
于是总复杂度:$O((n+m)log^2n)$

【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解:http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树,第一维是权值(用BIT搞成后缀和),第二维是DFS序
这样的话,对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ,我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话,原问题转化为:在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话,复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的,感觉很有道理的样子
然而懒得写代码了,也不知道对不对

另外的话,再说一说正解吧!
考虑一条路径,说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话,该路径对应的 $ {log(n)}$ 个区间应该忽略,其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间,所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【BZOJ 3924】[ZJOI2015] 幻想乡战略游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3924
神犇题解:http://www.cnblogs.com/clrs97/p/4779754.html
官方题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

考虑从根开始向下走
如果一个儿子的子树的权值和大于总和的一半
那么所求的点一定在这个儿子的子树中
由此可见,实际上我们所求的是这样的点:

深度最大的,子树权值和大于总权值和一半的点

这样的话,暴力找复杂度不稳定
考虑树链剖分的话,可以在\({\log ^2}(n)\)的时间复杂度内找到答案
最后考虑输出解的话,似乎直接用树链剖分不行的样子
于是似乎还得用一个点分治? (・∀・(・∀・(・∀・*)

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int L = 18;
const int INF = 1e9;

int n,m,head[N],nxt[M],to[M],cost[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}

class Heavy_Light_Decomposition{
	int dep[N],dis[N],fa[N],top[N],sz[N];
	int go[N],pos[N],len[N],sum,cnt;
	vector<int> que[N];
	class Fenwick_Tree{
		#define lowbit(x) ((x)&-(x))
		int arr[N];
		public:
			inline void modify(int l, int r, int delta) {
				modify(l-1, -delta);
				modify(r, delta);
			}
			inline int query(int p) {
				LL ret = 0;
				for (int i=p;i<=n;i+=lowbit(i))
					ret += arr[i];
				return ret;
			}
		private:
			inline void modify(int p, int delta) {
				for (int i=p;i;i-=lowbit(i))
					arr[i] += delta;
			}
	}BIT;
	public:
		inline void init() {
			DFS1(1, 1);
			DFS2(1, 1, 1);
		}
		inline int DIS(int u, int v) {
			int lca = LCA(u, v);
			return dis[u] + dis[v] - (dis[lca] << 1);	
		}
		inline void modify(int w, int v) {
			sum += v;
			for (;w;w=fa[top[w]]) 
				BIT.modify(pos[top[w]], pos[w], v);
		}
		inline int query() {
			int w = 1, tag = 1;
			while (tag) {
				int l = 1, r = len[w]-1, mid, ret = 0;
				while (l <= r) {
					mid = l + r >> 1;
					if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
					else l = mid + 1, ret = mid;
				} 
				w = que[w][ret]; tag = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
						tag = 1; w = to[i]; break;
					}
				}
			}
 			return w;
		}
	private:
		void DFS1(int w, int f) {
			sz[w] = 1; dep[w] = dep[f] + 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f) {
					dis[to[i]] = dis[w] + cost[i];
					fa[to[i]] = w;
					DFS1(to[i], w);
					sz[w] += sz[to[i]];
					if (sz[to[i]] > sz[go[w]])
						go[w] = to[i];
				}
			}
		}
		void DFS2(int w, int f, int t) {
			que[t].push_back(w);
			top[w] = t;	pos[w] = ++cnt;
			if (go[w]) DFS2(go[w], w, t);
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && to[i] != go[w]) {
					DFS2(to[i], w, to[i]);
				}
			}
			len[w] = que[w].size();
			que[w].push_back(w);
		}
		inline int LCA(int u, int v) {
			while (top[u] != top[v]) 
				if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
				else v = fa[top[v]];
			return dep[u] > dep[v]? v: u;
		}
}HLD;

class Vertex_Based_Divide_and_Conquer{
	int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
	int root,size,cur,val_sum[N],val_sum_del[N];
	LL part_ans[N],part_ans_del[N];
	public:
		inline void init() {
			int rt = Get_Root(1, n);
			len[rt] = 1;
			build(rt, n);
		}
		inline void modify(int w, int v) {
			val_sum[w] += v;
			for (int i=1,p=w,d,u;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				val_sum[p] += v;
				val_sum_del[u] += v;
				part_ans[p] += (LL)v * d;
				part_ans_del[u] += (LL)v * d;
			}
		}
		inline LL query(int w) {
			LL ret = part_ans[w];
			for (int i=1,p=w,u,d;i<len[w];i++) {
				u = p; p = fa[w][i]; d = rod[w][i];
				ret += part_ans[p] + (LL)val_sum[p] * d;
				ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
			}
			return ret;
		} 
	private:
		inline int Get_Root(int w, int sz) {
			size = sz; cur = INF;
			Get_root(w, w);
			return root;
		}
		void Get_root(int w, int f) {
			int mx = 1; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_root(to[i], w);
					sum[w] += sum[to[i]];
					mx = max(mx, sum[to[i]]);
				}
			}
			mx = max(mx, size - sum[w]);
			if (mx < cur) cur = mx, root = w;
		}
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=1;i<len[w];i++) 
				rod[w][i] = HLD.DIS(w, fa[w][i]);
			for (int i=head[w],tmp,rt;i;i=nxt[i]) {
				if (!vis[to[i]]) {
					tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
					rt = Get_Root(to[i], tmp);
					len[rt] = len[w] + 1;
					memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
					build(rt, tmp);
				}
			}
		}
		
}VDC;

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u, v, read());
	}
	HLD.init();
	VDC.init();
	for (int i=1,p,v;i<=m;i++) {
		p = read(); v = read();
		HLD.modify(p, v);
		VDC.modify(p, v);
		p = HLD.query();
		printf("%lld\n",VDC.query(p));
	}
	return 0;
}

【BZOJ 4568】[Scoi2016] 幸运数字

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/

《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 20000+9; 

int n,q,head[N],nxt[N*2],to[N*2];
LL arr[N];

inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

namespace LCA{
	int fa[N][16],dep[N];
	LL f[N][16][61],POW[61];

	void DFS(int w, int f) {
		fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; 
		for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
	} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}
	
	inline void merge(LL *a, LL *b) {
		for (int i=60;~i;i--) if (b[i]) {
			LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
				if (!a[j]) {a[j] = w; break;}
				else w ^= a[j];
			}
		} 
	}
	
	inline void init() {
		for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
		for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
		for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) 
			fa[i][j] = fa[fa[i][j-1]][j-1], 
			memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
			merge(f[i][j],f[fa[i][j-1]][j-1]);
	}
	
	inline LL query(int x, int y) {
		static LL bas[61]; memset(bas,0,sizeof(bas));
		if (dep[x] < dep[y]) swap(x,y);
		for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) 
			merge(bas,f[x][i]), x = fa[fa[x][i]][1];
		if (x == y) merge(bas,f[x][0]);  
		else {
			for (int i=15;~i;i--)  if (fa[x][i] != fa[y][i])
				merge(bas,f[x][i]), merge(bas,f[y][i]), 
				x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
			merge(bas,f[x][0]); 
		} LL ret = 0;
		for (int i=0;i<=60;i++) if (bas[i]) 
		for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
		for (int i=0;i<=60;i++) ret ^= bas[i];
		return ret;
	}	
};

int main(){
	n = read(); q = read();
	for (int i=1;i<=n;i++) arr[i] = readL();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	LCA::DFS(); LCA::init(); 
	for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read()));
	return 0;
}

另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html