CF1827题解

A

将\(a\)和\(b\)排序，对于每个\(a_i\)，可以找到最大的\(j\)，使得\(a_i > b_j\)，由于排序，这个\(j\)一定具有单调性，且\(a_i\)排列后对应的数一定是这\(j\)个中的一个。

又因为前面\(i - 1\)个数已经选了\(i - 1\)个\(b_t，t \leq j\)，（管它选的什么）所以留给\(a_i\)的选择只有\(j - i + 1\)种，如果这个数\(\leq 0\)则答案等于0。

时间复杂度\(O(n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,MOD = 1e9 + 7;
int a[N],b[N],n,ans = 1;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		ans = 1;
		cin>>n;
		for(int i = 1;i <= n;i++) cin>>a[i];
		for(int i = 1;i <= n;i++) cin>>b[i];
		sort(a + 1,a + n + 1);
		sort(b + 1,b + n + 1);
		for(int i = 1,j = 1;i <= n - 1;i++)
		{
			while(b[j] < a[i] && j <= n) ++j;
			--j;
			ans = 1ll * ans * max((j - i + 1),0) % MOD;
		}
		if(a[n] <= b[n]) ans = 0;
		cout<<ans<<endl;
	}
	return 0;
}

B（B2）

离谱陷阱题，个人认为难度高于C、D、E。

考虑每一个缝隙\(i \to i + 1\)，它总共会有\(i * (n - i)\)个贡献，考虑它不会对一个区间产生贡献，当且仅当\(max(l,i) \leq min(i + 1,r)\)。考虑找到这些区间。

枚举每个位置\(x\)，设\(a_x\)是前半个区间（这个区间末尾不一定为\(x\)）的最大值。单调栈可以预处理求出前面第一个大于\(a_x\)的值\(pre_x\)（没有则0），后面第一个大于\(a_x\)的值\(suf_x\)（没有则0）。左端点可以在\(pre_x + 1 \to x\)当中取。我们又发现，如果前、后半段的分界点小于\(suf_x - 1\)，那么我们在后半段的最小值一定小于\(a_x\)（保证\(a\)中两两不同）。所以前后段分界点一定是\(suf_i - 1\)，假设\(suf_i\)以后第一个比\(a_x\)小的数的位置记为\(f\)，那么右端点一定可以在\(suf_i\to f - 1\)当中取，贡献减去\((x - pre_x) * (f - suf_x)\)，\(f\)在离散化后用值域树状数组求，所以枚举\(x\)时按照\(suf_x\)从大到小的顺序枚举。

时间复杂度\(O(n \log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n,m;
struct BIT{
	int a[N];
	inline void init() {for(int i = 1;i <= m;i++) a[i] = n + 1;}
	inline int lowbit(int x)
	{
		return x & (-x);
	}
	inline void md(int x,int k)
	{
		if(x > m) return;
		a[x] = min(a[x],k);
		md(x + lowbit(x),k);
	}
	inline int query(int x)
	{
		if(!x) return n + 1;
		return min(query(x - lowbit(x)),a[x]);
	}
}p;
int a[N],b[N],stk[N],pos[N],pre[N],suf[N],top = 0,pl[N];
inline int fd(int x)
{
	int l = 1,r = m;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(b[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}
inline bool cmp(int x,int y)
{
	return suf[x] > suf[y];
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i = 1;i <= n;i++) cin>>a[i],b[i] = a[i];
		sort(b + 1,b + n + 1);
		m = unique(b + 1,b + n + 1) - (b + 1);
		p.init();top = 0;
		for(int i = 1;i <= n;i++) a[i] = fd(a[i]);
		for(int i = 1;i <= n;i++)
		{
			while(top && stk[top] <= a[i]) --top;
			pre[i] = (top ? pos[top] : 0);
			stk[++top] = a[i],pos[top] = i;
		}
		top = 0;
		for(int i = n;i >= 1;i--)
		{
			while(top && stk[top] <= a[i]) --top;
			suf[i] = (top ? pos[top] : n + 1);
			stk[++top] = a[i],pos[top] = i;
		}
		for(int i = 1;i <= n;i++) pl[i] = i;
		sort(pl + 1,pl + n + 1,cmp);
		long long ans = 0;
		for(int i = 1,tp = n;i <= n;i++)
		{
			int x = pl[i];
			while(tp >= suf[x]) p.md(a[tp],tp),--tp;
			int f = p.query(a[x] - 1);
			if(f > suf[x])
				ans -= 1ll * (x - pre[x]) * (f - suf[x]);
		}
		for(int i = 2;i <= n;i++) ans += 1ll * (i - 1) * (n - i + 1);
		cout<<ans<<endl;
	}
	return 0;
}

C

考虑好的字符串拆分成若干极小偶回文子串的方法是一定的，就是每次减去一个最短偶回文后缀，所以设\(f_i\)是以\(i\)结尾的好子串个数，\(g_i\)是以\(i\)结尾的最短偶回文后缀长度，则有

\[f_i = f_{i - g_i} + 1 \]

+1是表示最短回文后缀也是一个好的串。

现在考虑求\(g\)的值，这个地方当然可以用\(PAM\)再在\(fail\)树上求解，但是此处可以用\(manacher\)。先用\(manacher\)跑一边最大回文半径，然后只扫描以间隔为中心的回文串，发现对于一个\(i\)，只有一个中心（即最靠右的中心）能够更新这个点，所以我们从右向左扫描每个间隔，将\(\frac {i + 1}2 \to \frac {i + p_i - 2}2\)的\(g_i\)值（还没被删掉的）用\(i\)这个中心更新，然后在链表中删除这些点即可。

时间复杂度\(O(n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,m,p[N];
int f[N],g[N],nxt[N],pre[N];
char s[N],rd[N];
inline void read()
{
	char k = getchar();
	m = 0; s[m] = '?';
	++m; s[m] = '#';
	scanf("%s",rd + 1);
	for(int i = 1;i <= n;i++)
	{
		++m;s[m] = rd[i];
		++m;s[m] = '#';
	}
	s[m + 1] = ']';
}
inline void del(int x)
{
	nxt[pre[x]] = nxt[x];
	pre[nxt[x]] = pre[x];
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		read();
		for(int i = 1;i <= n;i++) f[i] = 0;
		for(int i = 1,r = 0,mid = 0;i <= m;i += 2)
		{
			if(r > i) p[i] = min(p[(mid << 1) - i],r - i + 1); else p[i] = 0;
			while(s[i + p[i]] == s[i - p[i]]) ++p[i];
			if(i + p[i] - 1 > r) r = i + p[i] - 1,mid = i;
		}
		for(int i = 1;i <= n;i++) pre[i] = i - 1,nxt[i] = i + 1;
		for(int i = m;i > 0;i -= 2)
			for(int j = (i + 1) >> 1;j <= (i + p[i] - 2) >> 1;j = nxt[j])
			{
				f[j] = (j << 1) - i + 1;
				del(j);
			}
		long long ans = 0;
		for(int i = 1;i <= n;i++) 
			if(f[i]) g[i] = 1 + g[i - f[i]],ans += g[i];
			else g[i] = 0;
		cout<<ans<<endl;
	}
	return 0;
}

D

考虑树的重心的两个性质：

1.增加一个节点，重心最多移动一条边。

2.要让树有两个重心，当且仅当树的节点数为偶数并且切开两个重心的边（两个重心相邻），可以将树切成等大的两部分。

对于本题，让树有两个重心的最快方法就是往原重心最大的子树中加点，使子树大小等于剩余部分大小，设子树大小为\(k\)，则当前答案为\(n - 2k\)。

所以我们考虑先建好树的结构，一个一个加点。维护每个点子树大小，重心，和重心最大的子树大小。

当加入一个点时：

如果这个点加在子树内，分为两种情况：
- 增加点所在的子树大小超过\(\lfloor \frac n2 \rfloor\)，那么一定是\(\lfloor \frac n2 \rfloor + 1\)，如果超过这个值，上一步就已经移动；并且此时\(n\)是奇数（若\(n\)是偶数上一步也进入这个情况，重心移动）。那么重心移动到相应儿子，新重心最大的子树是它的父亲（原重心方向），子树大小是\(\lfloor \frac n2 \rfloor\)。
- 否则更新最大的子树大小。
如果加在子树外，则增加点所在的子树大小是重心的父亲往上的一部分大小，同上处理即可。

对于其中增加点在哪个子树的判断，\(dfs\)记录深度且用倍增即可。

时间复杂度\(O(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct Edge{
	int v,next;
}e[N * 2];
int n,dfn[N],tot = 0,head[N],fa[22][N],dep[N],siz[N];
struct BIT{
	int a[N];
	inline void init()
	{
		for(int i = 1;i <= n;i++) a[i] = 0;
	}
	inline int lowbit(int x)
	{
		return x & (-x);
	}
	inline void md(int x,int k)
	{
		for(;x <= n;x += lowbit(x)) a[x] += k;
	}
	inline int query(int x)
	{
		int ret = 0;
		for(;x;x -= lowbit(x)) ret += a[x];
		return ret;
	}
}t;
inline void add(int x,int y)
{
	++tot;
	e[tot].v = y;
	e[tot].next = head[x];
	head[x] = tot;
}
inline void dfs(int x)
{
	dfn[x] = ++tot; ++siz[x];
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		fa[0][to] = x;
		dep[to] = dep[x] + 1;
		dfs(to);
		siz[x] += siz[to];
	}
}
inline int jump(int x,int d)
{
	for(int i = 20;i >= 0;i--)
		if(d & (1 << i)) x = fa[i][x];
	return x;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		t.init();
		for(int i = 1;i <= n;i++) siz[i] = head[i] = dfn[i] = fa[0][i] = dep[i] = 0;
		tot = 0;
		for(int i = 2,x;i <= n;i++)
		{
			cin>>x;
			add(x,i);
		}
		tot = 0;
		dfs(1);
		for(int i = 1;i <= 20;i++)
			for(int j = 1;j <= n;j++)
				fa[i][j] = fa[i - 1][fa[i - 1][j]];
		t.md(dfn[1],1);
		for(int i = 2,g = 1,maxson = 0;i <= n;i++)
		{
			t.md(dfn[i],1);
			if(dfn[i] <= dfn[g] + siz[g] - 1 && dfn[i] >= dfn[g])
			{
				int to = jump(i,dep[i] - dep[g] - 1);
				int sizson = t.query(dfn[to] + siz[to] - 1) - t.query(dfn[to] - 1);
				if(sizson > i / 2)
				{
					g = to;
					maxson = i / 2;
				}
				else maxson = max(maxson,sizson);
			}
			else
			{
				int sizson = i - t.query(dfn[g] + siz[g] - 1) + t.query(dfn[g] - 1);
				if(sizson > i / 2)
				{
					g = fa[0][g];
					maxson = i / 2;
				}
				else maxson = max(maxson,sizson);
			}
			cout<<i - 2 * maxson<<" ";
		}
		cout<<endl;
	}
	return 0;
}

E

~~点分做法：G~~

这道题的确有点分做法，但~~博主调了四个小时~~，故先不管，讲个更简单的方法。

首先发现如果两个节点不能连通，那么它们下面的叶子节点也不能连通，所以只考虑叶节点即可。我们记录\(anc_i\)为叶节点\(i\)向上经过一条路线能到达最浅的节点。

对于一个叶节点，到达\(anc_i\)后如果想一步走到另外一个叶节点，只能接一条路径，也就是从另外一个叶节点出发到\(anc_j\)的路径，所以所有\(anc\)一定排列在一条直链上（没有拐点）。

但这并不是充要条件，我们找一个最深的\(anc_j\)，如果有一个叶节点不能直接到\(anc_j\)，就意味着这个点和\(j\)无法连通，所以我们直接以\(anc_j\)为根，求一遍\(anc\)，看是否所有叶节点的\(anc\)都等于根即可。

至于\(anc_i\)的求法，直接求对于以\(i\)为端点的每条路径，\(lca_{i,v}\)就是\(anc_i\)。

时间复杂度\(O(n\log n)\)。

本题有些卡常，建议使用\(O(n\log n) - O(1)\)的\(LCA\)。即记录树的\(dfs\)序（经过一次就记一次，从儿子回来也记一次）。记录每一个点第一次出现的位置\(dfn_i\)，\(ST\)表预处理后，求\(lca_{i,j}\)时直接求\(min\{min\{dfn_i,dfn_j\} \to max\{dfn_i,dfn_j\}\}\)即可。证略。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int eu[21][N * 3],head[N],dfn[N],rev[N * 3],n,m,tot = 0,anc[N],leaf[N],dep[N];
vector <int> G[N];
struct Edge{
	int v,next;
}e[N * 2];
inline void add(int x,int y)
{
	++tot;
	e[tot].v = y;
	e[tot].next = head[x];
	head[x] = tot;
}
inline void dfs(int x,int last)
{
	dfn[x] = ++tot; rev[tot] = x;
	dep[x] = dep[last] + 1;
	eu[0][tot] = dfn[x];
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		if(to == last) continue;
		dfs(to,x);
		eu[0][++tot] = dfn[x];
	}	
	if(!e[head[x]].next) leaf[x] = 1;
}
inline void dfs1(int x,int last)
{
	if(leaf[x])
	{
		anc[x] = x;
		for(auto v : G[x])
		{
			int s = min(dfn[x],dfn[v]),t = max(dfn[x],dfn[v]),d = log(t - s + 1) / log(2);
			int lca = rev[min(eu[d][s],eu[d][t - (1 << d) + 1])];
			if(dep[lca] < dep[anc[x]]) anc[x] = lca;
		}
	}
	for(int i = head[x];i;i = e[i].next)
	{
		int to = e[i].v;
		if(to == last) continue;
		dfs1(to,x);
	}
}
inline void getanc(int rt)
{
	tot = 0;
	for(int i = 1;i <= n;i++) leaf[i] = 0;
	dep[rt] = 0;
	dfs(rt,0);
	for(int i = 1;i <= 20;i++)
		for(int j = 1;j + (1 << i) - 1 <= tot;j++)
			eu[i][j] = min(eu[i - 1][j],eu[i - 1][j + (1 << (i - 1))]);
	dfs1(rt,0);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		int x,y;
		for(int i = 1;i <= n - 1;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x); 
		for(int i = 1;i <= m;i++) scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
		getanc(1);
		int now = 0;
		for(int i = 1;i <= n;i++)
			if(leaf[i])
				if(!now || dep[anc[i]] > dep[anc[now]]) now = i;
		getanc(anc[now]);
		int rch = 1;
		for(int i = 1;i <= n;i++)
		{
			if(!leaf[i]) continue;
			if(anc[i] != anc[now])
			{
				printf("NO\n%d %d\n",now,i);
				rch = 0;
				break;
			}
		}
		if(rch) printf("YES\n");
		for(int i = 1;i <= n;i++) head[i] = dfn[i] = anc[i] = leaf[i] = dep[i] = 0,G[i].clear();
		tot = 0;
	}
	return 0;
}