【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;
}

28 thoughts to “【UOJ 284】[Goodbye Bingshen] 快乐游戏鸡”

  1. Hello! This is my first comment here so I just wanted to give a quick shout out and tell you I
    genuinely enjoy reading your blog posts. Can you suggest any other blogs/websites/forums
    that cover the same topics? Thanks a lot!

  2. Wow that was unusual. I just wrote an very long comment but after I clicked submit my
    comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyway, just wanted to say fantastic blog!

  3. Link exchange is nothing else except it is simply placing the other person’s weblog link on your page at
    suitable place and other person will also do similar in support of you.

  4. I think this is among the most significant info for me.
    And i’m glad reading your article. But should remark on few general things, The site style is wonderful, the articles
    is really nice : D. Good job, cheers

  5. Incredible! This blog looks exactly like my old
    one! It’s on a completely different subject but it has pretty much the same page layout
    and design. Superb choice of colors!

  6. Thank you for the good writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you! By the way, how could we communicate?

  7. I’m really loving the theme/design of your weblog. Do you
    ever run into any internet browser compatibility problems?

    A small number of my blog readers have complained about my website
    not operating correctly in Explorer but looks great in Firefox.
    Do you have any tips to help fix this issue?

  8. I got this website from my pal who shared with me on the topic of
    this web page and at the moment this time I am visiting this web site and
    reading very informative content here.

Leave a Reply to this coconut oil Cancel reply

Your email address will not be published. Required fields are marked *