https://codeforces.com/contest/1175

E. Minimal Segment Cover

 

题意：在一条直线上给定了 n 个区间，m次询问，每次给出一个区间，问至少需要多少个区间能够覆盖询问区间。注意是覆盖区间中的所有实数点，不只是整数点。

倍增

这种问题好像是经典的倍增。

mx[i][j]mx[i][j] 表示从坐标 ii ，经过 2j2^j 个区间，最远到达的坐标。

可以通过二分来确定，但是由于进制数可以贪心，所以只要贪心地从大到小遍历 jj ，每当 mx[i][j]<ymx[i][j]<y 时跳 jj。注意由于不是小于等于并且在同一个区间内也要跳，所以最后还要跳一次 mx[i][0]mx[i][0]。

可以通过dp得到 mx[i][0]mx[i][0]，对于每个区间，左端点 mx[i][0]=max(mx[i][0],r)mx[i][0]=max(mx[i][0],r)，再遍历坐标，mx[i][0]=max(mx[i][0],max(mx[i−1][0],i))mx[i][0]=max(mx[i][0],max(mx[i-1][0],i))。

也可以按照右端点排序后贪心遍历。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m;
int mx[N][20];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		mx[l][0] = max(mx[l][0], r);
	}
	for (int i = 1; i < N; i++)mx[i][0] = max(mx[i][0], max(mx[i - 1][0], i));
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < N; j++) {
			mx[j][i] = mx[mx[j][i - 1]][i - 1];
		}
	}
	while (m--) {
		int x, y, ans = 0;
		scanf("%d%d", &x, &y);
		for (int i = 19; i >= 0; i--) {
			if (mx[x][i] < y) {
				x = mx[x][i];
				ans += (1 << i);
			}
		}
		x = mx[x][0]; ans++;
		if (x < y)puts("-1");
		else printf("%d\n", ans);
	}
	return 0;
}

 

贪心+二分

时间长了一倍，不得不说cf的时间是真的松。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m;
typedef pair<int, int>pii;
int mx[N][20];
vector<pii>vc;
bool cmp(const pii& a, const pii& b) {
	return a.second > b.second;
}
bool ck(int s, int t, int x) {
	int res = s;
	for (int i = 0; i < 20; i++) {
		if ((x >> i) & 1)res = mx[res][i];
	}
	return res >= t;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		vc.push_back(pii(l, r));
	}
	sort(vc.begin(), vc.end(), cmp);
	int t = INF;
	for (pii p : vc) {
		t = min(t, p.second);
		while (t >= p.first)mx[t][0] = p.second, t--;
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < N; j++) {
			mx[j][i] = mx[mx[j][i - 1]][i - 1];
		}
	}
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		int L = 1, R = n + 1;
		while (L < R) {
			int mid = (L + R) / 2;
			if (ck(x, y, mid))R = mid;
			else L = mid + 1;
		}
		if (L == n + 1)puts("-1");
		else printf("%d\n", L);
	}
	return 0;
}

 

F. The Number of Subpermutations

 

题意：给定一个数列，问有几个区间满足是1到子数列长度的排列。

暴力枚举+哈希

是排列说明包含1到数列长度所有的数，也就说明必定包含1。所以考虑枚举 1 的位置，从该位置开始找到满足条件的区间，用哈希+异或可以确定是否包含所有数。

从为1的位置向右遍历作为区间的右端点，直到遇到下一个1。并假设排列中的最大值在1的右边，这样每遍历到一个位置，就可以通过已有的最大值确定排列长度，再确定这一段长度的异或值是否等于预处理出的长度前缀的异或值，也就能知道这一段是否合法。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int n;
int a[N], ans;
#define ull unsigned ll
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
ull v[N], tmp[N], pre[N];
void cal() {
	for (int i = 1; i <= n; i++) {
		if (a[i] != 1)continue;
		int t;
		for (t = i - 1; t >= 1 && a[t] != 1; t--) {
			tmp[i - t] = tmp[i - t - 1] ^ v[a[t]];
		}
		int len = i - t - 1, mx = 1;
		ull now = v[1];
		for (int j = i + 1; j <= n && a[j] != 1; j++) {
			mx = max(mx, a[j]);
			now ^= v[a[j]];
			if (mx <= j - i + len + 1 && mx > j - i && (now^tmp[mx - j + i - 1]) == pre[mx])ans++;
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		v[i] = mt();
		pre[i] = (pre[i - 1] ^ v[i]);
		ans += (a[i] == 1);
	}
	cal();
	reverse(a + 1, a + n + 1);
	cal();
	printf("%d\n", ans);
	return 0;
}