Infinite Fraction Path(ICPC 2017 Shenyang)

这不是我们 SA 基数排序的倍增法嘛！怎么出板子，而且似乎两只 log⁡\log 就可以跑过，所以可以把我经常写错的基排扔掉。

对于没有接触过 SA 的同学，讲讲倍增法是怎样运行的。先处理出每一个节点长度为 11 的字符串的排名，然后下一步求出长度为 22 的字符串的排名，具体地，相当于把一些两个长度为 11 的，已经排名过的字符串接起来然后字典序排序。唉，这不就是双关键字排序嘛！前面的字符串第一关键字，后面字符串第二关键字，然后排序完重新更新一下每个节点出发长度为 22 字符串的排名。

扩展一下，对于节点 ii，设移动 2k2^k 步后的节点为 (i,k)(i,k)，从 ii 出发的长度为 2k2^k 的字符串为 S(i,k)S(i,k)。已经求出了 S(i,k−1)S(i,k-1) 的排名，要求 S(i,k)S(i,k) 的排名，即将两个字符串 S(i,k−1),S((i,k−1),k−1)S(i,k-1),S((i,k-1),k-1) 首尾相接在一起。排序的时候根据 rkS(i,k−1)rk_{S(i,k-1)} 为第一关键字，rkS((i,k−1),k−1)rk_{S((i,k-1),k-1)} 为第二关键字进行排序，就可以求出 rkS(i,k)rk_{S(i,k)} 了。然后 kk 可以取到 ⌈lg⁡n⌉\lceil\lg n\rceil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
REP(i,0,n-1)st[0][i]=(1ll*i*i+1)%n;
REP(i,0,n-1)f[i]=s[i];
REP(j,1,K-1){
	REP(i,0,n-1){
		st[j][i]=st[j-1][st[j-1][i]]; // 倍增求出 (i,k) 的节点编号
		a[i+1]=node{f[i],f[st[j-1][i]],i};
	}
	sort(a+1,a+n+1);
	int rk=0;
	REP(i,1,n){
		int id=a[i].id;
		++rk;
		if(a[i].v1==a[i-1].v1&&a[i].v2==a[i-1].v2)--rk; // 求排名，相等就复制前面的
		g[id]=rk; // 记录排名
	}
	REP(i,0,n-1)f[i]=g[i];
}
int p=0;
REP(i,1,n-1)if(f[i]==1)p=i; // 求出对应字符串字典序最小的节点编号
REP(i,1,n){
	putchar(s[p]);
	p=st[0][p];
}

精灵对战(SCCPC 2026)

小模拟也好 ** 恶心。

直接扫过一遍序列。贪心地考虑问题，如果第 i−1i-1 只最多战斗到 jj，那么第 ii 只尽可能延长对局局数。由于没有后效性，所以局部最优解等同于全局最优解。

接下来考虑第 ii 只从 ll 出发最大能到达的 rr 是多少。首先我们希望前面的尽可能打败对手，维护一个集合 SS 存储前面所有局能战胜对方的种类的交集，处理第 jj 个对手的时候也是与对手的压制集合取交。

当交集为空集的时候，当前就无法做到赢对方，那么剩下两个结果，两败俱伤和输掉尽可能选择两败俱伤。能做到两败俱伤必须是当前集合至少存在一个元素的压制集合不包含对手 jj。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
REP(i,1,m){
	vector<int>vec;
	for(auto v:E[a[i]])if(s.count(v))vec.push_back(v); // vec 是两个集合的交集
	if(vec.empty()){ // 交集为空，赢不了了
		if(s.empty()){ // 己方精灵刚刚开始比赛，s 必定为空
			++res;
			for(auto v:E[a[i]])s.insert(v);
		}else{
			if(check(s,a[i])){ // 判断是否能平局
				s.clear();
			}else{
				s.clear();
				for(auto v:E[a[i]])s.insert(v);
				++res; // 不能平局
			}
		}
	}else{
		s.clear();
		for(auto v:vec)s.insert(v); // 取交
	}
}

时间复杂度 Θ(nk)\Theta(nk)。把这份代码的 set 改成 vector 就可以实现了，但是有些麻烦。

Reverse Permutation

来源：AT_abc465_c

难度：443

这个入想着要去噗叽组炸街，所以有了这篇题解。这题讲思路好像没啥意义，所以直接上做法。

提供一个简单的双指针做法。倒序扫描 SS 数组，对于答案数组 AA 会有一段可能为空的后缀 p,p+1,…,np,p+1,\dots,n。当扫描到第一个 SkS_k 为 o 时，说明 [1,k][1,k] 作为一个整体最后被翻转。由于 kk 只被翻转过一次，所以 kk 必然填在下标为 11 的位置上，即：

A[]={k,empty,…,empty,k+1,k+2,…,n}A[]=\{k,\text{empty},\dots,\text{empty},k+1,k+2,\dots,n\}

。其中，empty\text{empty} 表示这个位置暂时不确定位置。然后由于 [1,k][1,k] 做了一次翻转，所以原先填充 [k+1,n][k+1,n] 时是从右往左填充，现在要换个方向，从左往右填充。当第二次遇到 SpS_p 为 o 时，需要再次翻转填充的顺序，从左往右变为从右往左。那么只需要维护左右两个指针，初始移动右指针从大到小填充 [1,n][1,n]。遇到 o 时则换成另外一个指针，即：

A[]={k,k−1,…,p+1,empty,…,empty,p,k+1,k+2,…,n}A[]=\{k,k-1,\dots,p+1,\text{empty},\dots,\text{empty},p,k+1,k+2,\dots,n\}

。依此递推，只要是在倒序扫描 SS 的过程中出现 o，则变换扫描方向。如果是从左到右，变为从最右边开始往左扫描；如果是从右到左，变为从最左边开始往右扫描。

1
2
3
4
5
6
bool flag=0;int p=1,q=n; // flag = 0 移动右指针，= 1 移动左指针，p,q 分别代表左、右指针
PER(i,n,1){ // 记得倒序
	if(s[i]=='o')flag^=1; // 换一个指针
	if(flag)a[p++]=i; // 左指针从左到右填充值
	else a[q--]=i; // 右指针从右到左填充值
}

Carpets Removal(ICPC 2018 Jiaozuo R)

这是题啊？唉我场上竟然不会吗？那看来很是题了。

考虑两条地毯删去的贡献。贡献指的是仅被这两条地毯覆盖的方格数。可能仅被其中一条地毯覆盖，或者被两条地毯均覆盖。分成两种情况讨论。

第一类是所有贡献格均只被一条地毯覆盖，那么可以算单条地毯贡献。前缀和求出每个格子被多少条地毯覆盖，然后找到所有仅被覆盖 11 次的贡献格，这个信息再做一次前缀和。然后对于每个地毯可以单独求出有多少个格子仅被这条地毯覆盖。

第二类是存在两条地毯均覆盖的贡献格的情况。这时候可以找到所有只被覆盖两次的格子，然后对于每条地毯，找到所有这条地毯覆盖的，且恰好被两条地毯覆盖的格子，标记编号。这个可以二分+前缀和去找。Θ(n+m2log⁡m)\Theta(n+m^2\log m)。做完这些，重新遍历网格中恰好被两条地毯覆盖的格子，拎出两个地毯编号计算贡献。这一部分是 Θ(m2)\Theta(m^2)。

取两类情况最大值就好。记得拿被覆盖的格子数减去这个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
void dfs(int x1,int y1,int x2,int y2,int id){ // 找到限定区域内所有恰好被两条地毯覆盖的格子
	if(!query(2,x1,y1,x2,y2))return; // 区域内没有，直接跳过，保证时间复杂度
	if(x1==x2&&y1==y2){ // 只剩单个网格
		E[x1][y1].push_back(id); // 标记编号
		return;
	}
	if(x1==x2){ // 对第二维进行二分
		int mid=(y1+y2)>>1;
		dfs(x1,y1,x2,mid,id);
		dfs(x1,mid+1,x2,y2,id);
	}else{ // 对第一维进行二分
		int mid=(x1+x2)>>1;
		dfs(x1,y1,mid,y2,id);
		dfs(mid+1,y1,x2,y2,id);
	}
}
int getans(int u,int v){
	int res=g[u]+g[v];
	int x1=max(a[u],a[v]),y1=max(b[u],b[v]);
	int x2=min(c[u],c[v]),y2=min(d[u],d[v]);
	if(x1>x2||y1>y2)return res;
	res+=query(2,x1,y1,x2,y2);
	return res;
}
int solve(){
	n=read(),m=read();
	REP(i,1,m)REP(j,1,m){ // 初始化
		f[0][i][j]=f[1][i][j]=f[2][i][j]=0;
		E[i][j].clear();
	}
	REP(i,1,n){
		a[i]=read(),c[i]=read(),b[i]=read(),d[i]=read();
		++f[0][a[i]][b[i]];
		--f[0][a[i]][d[i]+1];
		--f[0][c[i]+1][b[i]];
		++f[0][c[i]+1][d[i]+1];
	}
	init_f(0); // 求出每个格子被几条地毯覆盖
	int sum=0;
	REP(i,1,m)REP(j,1,m){ // 分别表示恰好被 1/2 条地毯覆盖的格子数
		if(f[0][i][j]==1)++f[1][i][j];
		if(f[0][i][j]==2)++f[2][i][j];
		sum+=f[0][i][j]>0;
	}
	init_f(1);
	init_f(2);
	int maxn=0,max2=0;
	REP(i,1,n){
		g[i]=query(1,a[i],b[i],c[i],d[i]);
		if(g[i]>maxn)max2=maxn,maxn=g[i];
		else Max(max2,g[i]);
	}
	int res=maxn+max2; // 第一种情况
	REP(i,1,n)dfs(a[i],b[i],c[i],d[i],i);
	REP(i,1,m)REP(j,1,m){
		if(E[i][j].empty())continue;
		Max(res,getans(E[i][j][0],E[i][j][1])); // 第二种情况
	}
	return sum-res;
}