夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

某金牌训练营Day11

2021-02-25 17 min read

A

首先我们有一类转移是继承最大的一个子串

然后第二类转移就变成了

对于一个k级字符串,开头和结尾有一个k-1级字符串,然后我们要找到这样一个满足条件k-1级字符串

考虑rightpos集合,那么我们一定有k-1级的字符串rightpos完全包含第k级字符串的rightposrightpos

具体怎么做呢?

考虑在树上dp,对于u的父亲f,查找这个串是否合法

即查找这个串的所有rightpos中有没有一个是父亲节点代表的串,这个可以直接树上dfs实现,复杂度还是O(n2)O(n^2)

或者说是可以卡到n2n^2,举例bbbbbbbba(重复2e4次)

你会发现每个点的查询都会尽量先查小的,然后再去查询大的,但是因为有些没有

但是仔细一想,我们只需要使用每个串的一个rightposrightpos判断即可,因为不管从哪个位置开始,串都是一样的

如果不合法,相当于u要继承f的答案

然后我们就能发现这里有坑...我们要查找的是最高的祖先f同时其等级为k-1,因为串越短越可能出现

所以要用并查集缩点

使用线段树合并维护rightpos即可,可持久化形式

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int n;
char s[MAXN];

int rt[MAXN], rc, f[MAXN];
const int MAXT = 1e7 + 7;
namespace seg {
#define mid ((l+r)>>1)
	int ls[MAXT], rs[MAXT], T;
	inline void mdf(int &k, int l, int r, int P) {
		if(!k)k = ++T;
		if(l == r)return ;
		if(P <= mid)mdf(ls[k], l, mid, P);
		else mdf(rs[k], mid + 1, r, P);
		return ;
	}
	inline int qry(int k, int l, int r, int L, int R) {//查询区间L,R是否有数
		if(!k)return 0;
		if(L <= l && r <= R)
			return 1;
		if(R <= mid)return qry(ls[k], l, mid, L, R);
		else if(L > mid)return qry(rs[k], mid + 1, r, L, R);
		return qry(ls[k], l, mid, L, R) | qry(rs[k], mid + 1, r, L, R);
	}
	inline int dfs(int k, int l, int r, int p, int g, int o) {
		if(!k)return 0;
		if(l == r)
			return qry(p, 1, n, l - g + o, l - 1);
		return dfs(ls[k], l, mid, p, g, o) == 1 ? 1 : dfs(rs[k], mid + 1, r, p, g, o);
	}
	inline int merge(int x, int y) {
		if(!x || !y)return x | y;
		int k = ++T;
		ls[k] = merge(ls[x], ls[y]);
		rs[k] = merge(rs[x], rs[y]);
		return k;
	}
#undef mid
}

int T, lst, ch[MAXN][26], len[MAXN], fa[MAXN], c[MAXN], a[MAXN], dp[MAXN];

inline void ins(int c) {
	int p = lst, np = lst = ++T;
	int q, nq;
	len[np] = len[p] + 1;
	seg::mdf(rt[np], 1, n, rc);//这个节点挂去
	for(; p && !ch[p][c]; p = fa[p])ch[p][c] = np;
	if(!p) {
		fa[np] = 1;
		return ;
	}
	q = ch[p][c];
	if(len[q] == len[p] + 1) {
		fa[np] = q;
		return ;
	}
	nq = ++T;
	len[nq] = len[p] + 1;
	fa[nq] = fa[q];
	memcpy(ch[nq], ch[q], sizeof(ch[q]));
	fa[np] = fa[q] = nq;
	for(; ch[p][c] == q; p = fa[p])ch[p][c] = nq;
}

inline void solve() {
	for(int i = 1; i <= T; ++i)c[len[i]]++;
	for(int i = 1; i <= n; ++i)c[i] += c[i - 1];
	for(int i = 1; i <= T; ++i)a[c[len[i]]--] = i;
	for(int i = T; i >= 1; --i) {
		int u = a[i];
		rt[fa[u]] = seg::merge(rt[fa[u]], rt[u]);//直接合并!!!
	}
	int ans = 0;
	for(int i = 2; i <= T; ++i) {
		int u = a[i];
		dp[u] = dp[fa[u]];
		if(fa[u] == 1) {
			dp[u] = 1;
			f[u] = u;//操操操
			continue;
		}
		if(seg::dfs(rt[u], 1, n, rt[f[fa[u]]], len[u], len[f[fa[u]]]))dp[u] = dp[fa[u]] + 1, f[u] = u;//操操操
		else f[u] = f[fa[u]];
		ans = max(ans, dp[u]);
	}
	printf("%d\n", ans);
	return;
}

int main() {
	freopen("level2.in", "r", stdin);
	freopen("level1.out", "w", stdout);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	lst = T = 1;
	for(int i = 1; i <= n; ++i) {
		rc = i;
		ins(s[i] - 'a');
	}
	solve();
	return 0;
}

B

我不能操作一整个连通块,然后最小化删掉每个点之后最大连通块大小

max为最大的大小,max'为次大大小,min为最小的大小

每次操作一定是从最大的拿出来放到最小的,操作后能成为答案的只有max,max',min

不难发现我们要分出最接近(max−min)/2(max-min)/2同时不超过(max−max′)(max-max')大小的子树

但是这实际上是萎的,我们考虑二分答案mid,范围在[max′,max][max',max],然后想让最小子树和最大子树都不超过mid,要去除的子树大小就是r=max−mid,l=min+midr=max-mid,l=min+mid

如果存在一个子树在这个范围内就合法了,现在就想看这个子树存不存在

  1. 最大连通块在下面

直接预处理即可

线段树合并得到子树内的值域线段树,然后每个都查询一次即可,复杂度O(nlog2n)O(nlog^2n)

当然也可以主席树,相当于二维数点,查询区间[l,r][l,r]有没有一个数

最大连通块在上面

坏了啊

  1. 这条链的信息都会被修改,2. 都会减少这个点子树的大小

同时这个点子树内的信息都不能使用

建立值域线段树,然后dsu on tree去除掉子树信息就能解决掉子树内信息不能用

但是这条链坏掉了...

我们dfs的过程中栈中一直保留了这条链,因此我们在整体的值域线段树扣掉很简单

但是这一部分要单独查询,容易发现相当于全局修改标记,即查询[l+siz(x),r+siz(x)][l+siz(x),r+siz(x)],只有这样的才是合法的!

因此我们可以开一个set类似的结构维护dfs栈内信息就可以支持了

老师说树状数组,因为要支持区间,也行吧

因为本质上我们要最小化的过程在于找到最接近(max+min)/2(max+min)/2的一个数,因此找前驱后继也是可得

C

S(ij)=∑x∣i∑y∣j[(x,yj)==1]S(ij)=\sum_{x|i} \sum_{y|j} [(x,\frac{y}{j})==1]

不难发现我们对于所有素数幂都能有唯一的对应形式,比如a+b=算a次+算b次,同时都不取也有唯一的对应形式

约数和是

Sd(ij)=∑x∣i∑y∣j[(x,yj)==1]xjySd(ij)=\sum_{x|i}\sum_{y|j}[(x,\frac{y}{j})==1]x\frac{j}{y}

推式子

ans=∑i=1N∑j=1MS(i2)S(j2)S(ij)=∑i=1N∑j=1MS(i2)S(j2)∑x∣i,y∣j[(x,y)==1]=∑i=1N∑j=1MS(i2)S(j2)∑x∣i,y∣j∑k∣x,k∣yμ(k)=∑i=1N∑j=1MS(i2)S(j2)∑k∣i,k∣jμ(k)∑x∣ik,y∣jk=∑k=1min(N,M)μ(k)∑i=1Nk∑j=1MkS(i2k2)S(j2k2)S(i)S(j)=∑k=1min(N,M)μ(k)(∑i=1NSS(i2k2)S(i))(∑j=1MSS(j2k2)S(j))ans=\sum_{i=1}^N\sum_{j=1}^MS(i^2)S(j^2)S(ij)\\ =\sum_{i=1}^N\sum_{j=1}^MS(i^2)S(j^2)\sum_{x|i,y|j}[(x,y)==1]\\ =\sum_{i=1}^N\sum_{j=1}^M S(i^2)S(j^2) \sum_{x|i,y|j}\sum_{k|x,k|y}\mu(k)\\ =\sum_{i=1}^N\sum_{j=1}^M S(i^2)S(j^2) \sum_{k|i,k|j}\mu(k)\sum_{x|\frac{i}{k},y|\frac{j}{k}}\\ =\sum_{k=1}^{min(N,M)}\mu(k)\sum_{i=1}^{\frac{N}{k}}\sum_{j=1}^{\frac{M}{k}}S(i^2k^2)S(j^2k^2)S(i)S(j)\\ =\sum_{k=1}^{min(N,M)}\mu(k)(\sum_{i=1}^\frac{N}{S}S(i^2k^2)S(i))(\sum_{j=1}^\frac{M}{S}S(j^2k^2)S(j))\\

不难发现设h(x)=S(x2)h(x)=S(x^2),这个东西也是积性函数,可以线性筛出来然后直接暴力统计O(nlogn)O(nlogn)

预处理方法就是考虑那个约数的计算式子

∏p(k+1)\prod_{p} (k+1)

现在每次多一个质因数x,k会多2

突然发现我们能够预处理:

f(d,⌊Nd⌋)=∑i=1Ndh(id)S(i)f(d,\lfloor\frac{N}{d}\rfloor)=\sum_{i=1}^{\frac{N}{d}}h(id)S(i)

这个式子预处理方法就是枚举一个d,然后枚举d的倍数,然后我们发现和上一个d的倍数只差O(1)O(1)项,直接前缀和即可

然后回答询问直接暴力O(n)O(n)即可

为什么不能整除分块?因为我们k的取值对于内层是有影响的,而如果想合并起来,要n=mn=m才行

这样还是不太行

考虑设定一个阈值k,对于小于阈值的我们直接暴力处理,O(k)O(k)

然后对于大于阈值的,我们可以发现Nd∗Md\frac{N}{d}*\frac{M}{d}不会很多,可以直接暴力处理

gi,j(l)=∑max(i,j)∗d≤n,d≤lμ(d)f(d,i)f(d,j)g_{i,j}(l)=\sum_{max(i,j)*d\leq n,d\leq l}\mu(d)f(d,i)f(d,j)

这个怎么处理?考虑枚举i,j,然后对于一个l,你会发现这个l可以暴力计算

这样的复杂度在枚举i,j时是n2k2\frac{n^2}{k^2}再乘上一个k就是O(n2k)O(\frac{n^2}{k})

紧接着我们会发现对于一次询问枚举一下i,j的取值就能单次O(n2k2)O(\frac{n^2}{k^2})

钦定k=N2/3k=N^{2/3},可以得到O(QN2/3+N4/3)O(QN^{2/3}+N^{4/3})的复杂度做法

期望100pts

实际上我们对于后面的部分整除分块可以做到

O(QN+Qk+N2k)O(Q\sqrt N + Qk + \frac{N^2}{k})

但是这玩意还是k取n2/3n^{2/3}最快??应该是QQ太小了吧,如果Q,N同阶就是O(n)O(\sqrt n)最快了吧

看看代码吧,没啥细节...但是你要想到整除分块后面一部分挺难的

//O(Qk+Q\sqrt n+ n^2/k)
#include<bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int P = (1 << 30);
const int MAXN = 2e5 + 7;
const int N = 2e5;
const int B = 3200;
int n, m;
int d[MAXN], d2[MAXN], pri[MAXN], tot, num[MAXN], isp[MAXN], q, mu[MAXN], ans;
vi mp[N / B + 1][N / B + 1];//冲
vi v[MAXN];
//死亡开数组方法:
//pair映射vi,命秒没
inline int add(int x, int y) {
	x += y;
	if(x >= P)x -= P;
	return x;
}

inline void init() {
	d[1] = 1;
	mu[1] = 1;
	d2[1] = 1;
	for(int i = 2; i <= N; ++i) {
		if(!isp[i]) {
			pri[++tot] = i;
			d[i] = 2;
			d2[i] = 3;
			num[i] = 1;//!!!2
			mu[i] = -1;
		}
		for(int j = 1; j <= tot && i * pri[j] <= N; ++j) {
			isp[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				d[i * pri[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
				d2[i * pri[j]] = d2[i] / (2 * num[i] + 1) * (2 * num[i] + 3);
				num[i * pri[j]] = num[i] + 1;
				break;
			}
			d[i * pri[j]] = d[i] * d[pri[j]];
			d2[i * pri[j]] = d2[i] * d2[pri[j]];
			num[i * pri[j]] = 1;
			mu[i * pri[j]] = -mu[i];
		}
	}
	for(int p = 1; p <= N; ++p) {
		mu[p] = (mu[p] + P) % P;
		v[p].pb(1ll * d2[p] * d[1] % P);
		for(int n = 2; n * p <= N; n ++) {
			v[p].pb(add(v[p][v[p].size() - 1], 1ll * d2[n * p] * d[n] % P));
		}
	}
}

inline void init2() {
	for(int i = 1; i <= N / B; ++i) {
		for(int j = i; j <= N / B; ++j) {//这个也要-1...
			ll lst = 1ll * mu[B + 1] * v[B + 1][i - 1] % P * v[B + 1][j - 1] % P, as = 0;
			mp[j][i].pb(lst);
			for(int d = B + 2; d * j <= N; ++d) {
				as = (lst + 1ll * mu[d] * v[d][i - 1] % P * v[d][j - 1] % P) % P;
				mp[j][i].pb(as);
				lst = as;
			}
		}
	}
	return;
}

inline void solve1() {
	for(int i = 1; i <= min(m, B); ++i) {
		ans = add(ans, 1ll * v[i][n / i - 1] * mu[i] % P * v[i][m / i - 1] % P); //直接得到!!
	}
}

inline void solve2() {
	for(int r = B + 1, l = B + 1; l <= m; l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		if(l - 2 - B == -1)ans = add(ans, mp[(n / l)][(m / l)][r - B - 1]);
		else ans = add(ans, (mp[(n / l)][(m / l)][r - B - 1] - mp[(n / l)][(m / l)][l - 2 - B] + P) % P);
	}
	return ;
}

signed main() {
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);
	init();
	init2();
	scanf("%d", &q);
	while(q-- > 0) {
		scanf("%d%d", &n, &m);
		ans = 0;
		if(n < m)swap(n, m);
		solve1();
		if(m <= B) {
			printf("%d\n", ans);
			continue;
		}
		solve2();
		printf("%d\n", ans);
	}
	return 0;
}

莫队做法

这个和EI那个组合数区间和很像,用莫队规划路径然后O(small)O(small)移动

懂了,我k取N(Q)\frac{N}{\sqrt(Q)}

Powered by Gridea RSS