（22杭电多校二）Two Permutation (dp)，Package Delivery (贪心)

Two Permutations

题意
给定长度为 n 的全排列 $a[],b[]$，长度为 2n 的数列 $c[]$。
现在要用 2n 次操作构造一个长度为 2n 的数列，每次操作从全排列 $a[]$ 或 $b[]$ 的最前端取一个数字，将其从该数列删掉，然后加到构造数列的末端。
问，构造数列最终变为数列 $c[]$ 共有多少种构造方案？

$1\le n\le 300000，方案数\mathrm{mod}998244353$

思路
考虑 dp。
分别定义 f1[i, j] 表示，构造数列 $c[]$ 的前 i 个位置，末位置为全排列 $a[]$ 的 $j$ 位置 的方案数；
f2[i, j] 表示，构造数列 $c[]$ 的前 i 个位置，末位置为全排列 $b[]$ 的 $j$ 位置 的方案数。

状态转移：
从前到后遍历 c数列 每个位置 i，对于当前值找到其在 a数列 中出现的位置 pos，该位置的方案数从上一个位置方案数来转移，加上上一个位置的方案数。
第 i-1 个位置可能在 a数列 的 pos-1 位置，如果是的话 f1[i, pos] 就加上 f1[i-1, pos-1]；
还可能在 b数列 的 i-pos 位置，如果是的话 f1[i, pos] 加上 f2[i-1, i-pos]。

同样方式处理在 b数列 中出现的位置。

预处理：
预处理出第一个位置 f1[1,1], f2[1, 1]，后面遍历转移从第二个位置。

所以转移方程为：

int t = i-pos1;
if(a[pos1-1] == c[i-1]) f1[i][pos1] += f1[i-1][pos1-1];
if(b[t] == c[i-1]) f1[i][pos1] += f2[i-1][t];

t = i-pos2;
if(b[pos2 - 1] == c[i-1]) f2[i][pos2] += f2[i-1][pos2-1];
if(a[t] == c[i-1]) f2[i][pos2] += f1[i-1][t];
1
2
3
4
5
6
7

注意到 n 的大小，如果开两维的话，二维数组不能存，只能用 map，时间复杂度较高。
而观察状态转移，每次都从上一个位置转移，所以可以用滚动数组优化，二维压缩到一维。

int w = 0;
if(a[pos1-1] == c[i-1]) w += f1[pos1-1];
if(b[t] == c[i-1]) w += f2[t];
f1[pos1] = w % mod;

int w = 0;
if(b[pos2 - 1] == c[i-1]) w += f2[pos2-1];
if(a[t] == c[i-1]) w += f1[t];
f2[pos2] = w % mod;
1
2
3
4
5
6
7
8
9

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 300010, mod =  998244353;
int T, n, m;
int a[N], b[N], c[N*2];
int p1[N], p2[N];
map<int, int> f1[2*N], f2[2*N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p1[a[i]] = i;
		for(int i=1;i<=n;i++) cin >> b[i], p2[b[i]] = i;
		
		for(int i=1;i<=2*n;i++) cin >> c[i];
		
		for(int i=1;i<=2*n;i++) f1[i].clear(), f2[i].clear();
		
		if(a[1] == c[1]) f1[1][1] = 1;
		if(b[1] == c[1]) f2[1][1] = 1;
		
		for(int i=2;i<=2*n;i++)
		{
			int pos1 = p1[c[i]], t = i-pos1;
			if(pos1 <= i && t <= n)
			{
				if(a[pos1-1] == c[i-1]) f1[i][pos1] += f1[i-1][pos1-1];
				if(b[t] == c[i-1]) f1[i][pos1] += f2[i-1][t];
				f1[i][pos1] %= mod;
			}
			int pos2 = p2[c[i]]; t = i-pos2;
			if(pos2 <= i && t <= n)
			{
				int w = 0;
				if(b[pos2 - 1] == c[i-1]) f2[i][pos2] += f2[i-1][pos2-1];
				if(a[t] == c[i-1]) f2[i][pos2] += f1[i-1][t];
				f2[i][pos2] %= mod;
			}
		}
		
		int ans = 0;
		if(a[n] == c[2*n]) ans += f1[2*n][n];
		if(b[n] == c[2*n]) ans += f2[2*n][n];
		cout << ans % mod << endl;	
	}
	
	return 0;
}
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

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 300010, mod =  998244353;
int T, n, m;
int a[N], b[N], c[N*2];
int p1[N], p2[N];
int f1[N], f2[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p1[a[i]] = i;
		for(int i=1;i<=n;i++) cin >> b[i], p2[b[i]] = i;
		
		for(int i=1;i<=2*n;i++) cin >> c[i];
		
		for(int i=1;i<=n;i++) f1[i] = f2[i] = 0;
		
		if(a[1] == c[1]) f1[1] = 1;
		if(b[1] == c[1]) f2[1] = 1;
		
		for(int i=2;i<=2*n;i++)
		{
			int pos1 = p1[c[i]], t = i-pos1;
			if(pos1 <= i && t <= n)
			{
				int w = 0;
				if(a[pos1-1] == c[i-1]) w += f1[pos1-1];
				if(b[t] == c[i-1]) w += f2[t];
				f1[pos1] = w % mod;
			}
			int pos2 = p2[c[i]]; t = i-pos2;
			if(pos2 <= i && t <= n)
			{
				int w = 0;
				if(b[pos2 - 1] == c[i-1]) w += f2[pos2-1];
				if(a[t] == c[i-1]) w += f1[t];
				f2[pos2] = w % mod;
			}
		}
		
		int ans = 0;
		if(a[n] == c[2*n]) ans += f1[n];
		if(b[n] == c[2*n]) ans += f2[n];
		cout << ans % mod << endl;
	}
	
	return 0;
}
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

经验
以当前位置结尾的方案数 从 以上一位置结尾的方案数来转移，上一位置可能有多种情况，将这几种情况的方案数相加便是当前位置的方案数。

---

Package Delivery

题意
给定 n 个区间，每个区间有范围 $[l_i,r_i]$。
每次操作可以选择一个位置，然后消掉包括该位置的最多 m 个区间。
问，最少多少次操作能消掉所有区间？
$1\le m\le n\le 100000,1\le l_i\le r_i\le 10^9$

思路
很明显是贪心问题，考虑如何贪心。

每次只在区间的最后一个位置操作，在当前区间操作时，尽可能带走尽量多的区间。这样用的操作次数就最少。

考虑朴素做法：
首先按照右端点排序，从前到后遍历所有区间。
如果当前区间没有被消掉的话，就要用一次操作将当前区间消掉，为了尽可能带走更多区间，就把这个操作位置放到当前区间右端点，后面的左端点在此位置前面的所有区间都可以被带走。

• 如果说能带走的区间个数一共不超过 m 个，因为当前枚举的区间一定要消掉，所以一定要操作一次，将这些区间都带走。
• 但是如果能带走的区间个数超过 m 个了，是不是都要带走呢？
  一开始是这样想的，为了不浪费操作次数，每次就带走 m 的倍数个，剩下的区间不带走。剩哪些区间呢，剩右端点靠右的，也就是当前位置靠后的。
  这样想是比都带走更优的，但并不是最优的。
  如果当前位置能拿走 2m 个，但是后面有 m 个 能带走 m-1 个的区间，如果当前位置用两次操作带走的话，后面 m 个分别用 1 次操作。而如果当前位置用一次操作，把剩下的 m 个分别分给 后面的 m 个区间，这样后面的 m 个仍然是分别用 1 次操作，这样就少用了一次操作。
  所以，每次操作最多带走 m 个区间。
  这样的话，就往后找 m-1 个左端点小于等于当前区间右端点的区间，将其一起带走。

也就是，遍历每个没有被标记的区间，每次标记后面 m-1 个左端点不超过当前区间右端点的区间。

但是，无法在 O(nlogn) 的复杂度内实现上面的操作。

正着想是从前往后包，每次包最前面满足的 m 个。但是正着不好实现。
那不妨反着来，每次看当前区间是被前面哪个区间包着了。

用一个集合 set 来存储执行操作的区间。
按右端点排序，从前往后遍历所有区间：

• 找到集合中区间右端点第一个大于等于当前区间左端点的区间，那个区间就是包当前区间的区间。判断该区间是否已经包了 m 个区间了，如果是，将其从集合中删掉。
• 如果没找到，说明前面没有区间能包住自己，那么就要在当前区间执行操作，操作次数++，把当前区间放到集合中，包的集合个数置为 1。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
map<int,int> cnt;

const int N = 200010, mod = 1e9+7;
int T, n, m;
PII a[N];
int f[N];

bool cmp(PII a, PII b){
	if(a.se != b.se) return a.se < b.se;
	return a.fi < b.fi;
}

set<int> st;

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		for(int i=1;i<=n;i++) cin >> a[i].fi >> a[i].se;
		
		sort(a+1, a+n+1, cmp);
		
		st.clear(), cnt.clear();
		
		int ans = 0;
		for(int i=1;i<=n;i++)
		{
			auto it = st.lower_bound(a[i].fi);
			if(it == st.end())
			{
				ans ++;
				cnt[a[i].se] ++;
				st.insert(a[i].se);
				
				if(cnt[a[i].se] == m) cnt[a[i].se] = 0, st.erase(a[i].se); //m可能为1 
			}
			else
			{
				int x = *it;
				cnt[x]++;
				if(cnt[x] == m) cnt[x] = 0, st.erase(x);
			}
		}
		cout << ans << endl;
	}
	return 0;
}
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