【HackerRank】Unique Colors

相关链接

题目传送门:https://www.hackerrank.com/challenges/unique-colors
题目大意:http://paste.ubuntu.com/23686184/
官方题解:https://www.hackerrank.com/challenges/unique-colors/editorial

解题报告

Ⅰ.点分治的做法 \(O(n\log (n))\)

先考虑一种较为简单的情况:只有一种颜色
询问有多少对节点间至少存在一个点被染色

直接考虑点分治的做法的话
设当前的分治点为1
定义\({T_i}\)为点i的子树中到1号点的路径上有点被染色的点的数量
定义\({S_i}\)为点i的子树中点的个数

考虑此时对 点3 的贡献:

  1. 点3点1 的简单路径上没有染色点
    那么贡献为\({T_1} – {T_3}\)
  2. 点3点1 的简单路径上有染色点
    那么贡献为\({S_1} – {S_2}\)

这样的话,只有一种颜色的情况就解决了
现在考虑有多种颜色:

不难发现对于一个固定点i,颜色只需要分两类:
1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色

这样的话,我们发现只需要一次DFS就可以解决这个问题
于是就可以使用点分治解决这个问题啦!

Ⅱ. DFS序的做法 \(O(n)\)

先来考虑一个简单一点的版本:假如这货是在序列上
考虑每一种颜色单独处理的话,就是将序列分成几块,每一块的贡献不同
现在重新考虑树上的版本,其实也是把整个树分成好几块
酱紫的话,我们唯一需要解决的就是如何给树上一个连通块统一加上一个数

我们发现我们可以先搞出一个最小的包含“需要更改的连通块”的子树
然后去掉一些子树来删掉多余的部分
子树操作的话,在DFS序上是连续的,于是打差分就好
因为题目的特殊性,不难发现需要删掉的子树总共只会有\(O(n)\)个
于是此题就 \(O(n)\) 辣!

Code

好像两种写法都不是特别好写的样子
于是就不写代码辣!

【UOJ 213】[UNR #1] 争夺圣杯

题目传送门:http://uoj.ac/problem/213
原厂题解:http://c_sunshine.blog.uoj.ac/blog/1860

我发现这道题目,我写了30分的暴力,60分的乱搞,100分的乱搞QAQ

说一说100分的乱搞O(nlogn):
考虑每一个区间的右端点右移一格,左端点不动
那么区间mx要么变成最右边那个,要么不动
考虑计算最右边那货对于答案的贡献,实际上就是区间加减
于是线段树维护一下

其实搞到这里,O(n)的做法就很明显了
因为线段树那里,只需要区间加减,不需要支持中途询问
于是搞一个差分就可以把线段树给去掉

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int MOD = 998244353;

int n,arr[MAXN],vout,que[MAXN],lft[MAXN],MX[MAXN],BUF[MAXN]; 

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

inline void prework(){
	int tot = 0;
	for  (int i=1;i<=n;i++) {
		while (tot && arr[que[tot]] < arr[i]) tot--;
		BUF[1] = (BUF[1]+arr[i])%MOD;
		BUF[i-que[tot]+1] = ((BUF[i-que[tot]+1] - arr[i]) % MOD + MOD ) %MOD;
		lft[i] = i-que[tot]; que[++tot] = i; 
	} tot = 0; que[0] = n+1;
	for (int i=n;i;i--) {
		while (tot && arr[que[tot]] <= arr[i]) tot--;
		if(tot) {
			BUF[que[tot]-i+1] = ((BUF[que[tot]-i+1]-arr[i]) % MOD + MOD) % MOD; 
			BUF[que[tot]-i+lft[i]+1] = (BUF[que[tot]-i+lft[i]+1] + arr[i]) % MOD;
		} que[++tot] = i;
	}
	for (int i=n;i;i--) MX[i] = max(MX[i+1], arr[i]);
}

inline void solve(){
	int tmp = 0, delta = 0;
	for (int i=1;i<=n;i++) {
		delta = ((delta + BUF[i]) % MOD + MOD) % MOD;
		tmp = ((tmp + delta) % MOD + MOD) % MOD;
		vout ^= tmp;
		tmp -= MX[n-i+1];
	}
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) arr[i] = read();
	prework(); solve();
	printf("%d\n",vout);
	return 0;
}