https://codeforces.com/contest/1167

E. Range Deleting

 

题意：给定一个长为n，且每个数都小于等于x的数列a，设 f(l,r)f(l,r) 为删除数值大小在 [l,r][l,r] 的数之后剩下的数列，问有多少对 l,r 满足 f(l,r)f(l,r) 非递减。

设 L 为最大的满足1到L非递减的数。 R 为最小的满足R到x非递减的数。

则 l，r 必定位于如下位置。

所以只要先处理出 L，R ，再枚举 l ，找到对应的最小的 r，从 r 到 x 这一段都是可以与当前 l 配对的。

而最小的 r 必须要 r+1 最小出现的位置大于 l-1 最大出现的位置，也就是删除 l，r后 l -1 和 r+1 要能拼起来。可以二分找到大于 l-1 的最小的 r+1。

由于有一些数没有在数列中出现过，所以可以放在任意位置，为了使答案最大，在不同时候要放在不同位置，所以用 vi[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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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, x;
int a[N];
int l[N], r[N], vi[N], rr[N];
ll ans;
vector<int>vc;
int main() {
	scanf("%d%d", &n, &x);
	memset(l, 0x3f, sizeof(l));
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = max(r[a[i]], i);
	}
	for (int i = 1; i <= x; i++)if (r[i] == 0)vi[i] = 1;
	if (r[1] == 0)l[1] = r[1] = 1;
	for (int i = 2; i <= x; i++) {
		if (r[i] == 0)l[i] = r[i] = r[i - 1];
	}
	int L = 1, R = x;
	for (int i = 2; i <= x; i++) {
		if (l[i] >= r[i - 1])L = i;
		else break;
	}
	if (vi[x])l[x] = r[x] = n;
	for (int i = x - 1; i >= 1; i--) {
		if (vi[i])l[i] = r[i] = l[i + 1];
	}
	for (int i = x - 1; i >= 1; i--) {
		if (r[i] <= l[i + 1])R = i;
		else break;
	}
	
	for (int i = R; i <= x; i++)vc.push_back(l[i]);
	if (vi[1])l[1] = r[1] = 1;
	for (int i = 2; i <= x; i++) {
		if (vi[i])r[i] = l[i] = r[i - 1];
	}
	for (int i = 1; i <= L; i++) {
		auto p = lower_bound(vc.begin(), vc.end(), r[i]);
		if (p == vc.end())rr[i] = x + 1;
		else rr[i] = p - vc.begin() + R;
	}
	if (R == 1) {
		printf("%lld\n", 1ll * (x + 1)*x / 2);
		return 0;
	}
	ans += x - R + 2;
	ans += L + 1;
	ans--;
	for (int i = 2; i <= min(L + 1, x - 1); i++) {
		int tmp = rr[i - 1] - 1;
		if (tmp < i)continue;
		ans += x - tmp;
	}
	printf("%lld\n", ans);
	return 0;
}

 

双指针

向上面这么乱搞还是没用好已知条件，所以写起来很烦。

设 l[i] 为数值 i 最小的出现位置，r[i] 为数值 i 最大的出现位置。

则对于可行的一对 L,RL,R，必定满足

{l[x]>l[x−1]>⋯>r[R+1]r[1]<r[2]<⋯<l[L−1]r[1]<r[2]<⋯<r[L−1]<l[R+1]<l[R+2]<⋯<l[x]\begin{cases} l[x]>l[x-1]>\cdots>r[R+1]\\ r[1]<r[2]<\cdots<l[L-1]\\ r[1]<r[2]<\cdots<r[L-1]<l[R+1]<l[R+2]<\cdots<l[x]\\ \end{cases}

因此需要维护一个前缀的 r[i] 最大值 mxr[i]，以及后缀的 l[i] 最小值 mnl[i] 。

上面的条件就变为

{mnl[R+1]>r[L]mxr[L−1]<l[L]mxr[L−1]<mnl[R+1]\begin{cases} mnl[R+1]>r[L]\\ mxr[L-1]<l[L]\\ mxr[L-1]<mnl[R+1]\\ \end{cases}

由于有一些数没在数列中出现过，所以实际使用时要把大于小于号变成大于等于或小于等于。

由前两个式子得到和上一种方法相同的 L，R 所在的范围，由第三个式子得到每个 L 对应的最小的 R ，思路和上一种类似，但是实现上简单很多。

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
#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, x;
ll ans;
int a[N], l[N], r[N], mxr[N], mnl[N];
int main() {
	scanf("%d%d", &n, &x);
	memset(l, 0x3f, sizeof(l));
	memset(mnl, 0x3f, sizeof(mnl));
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		l[a[i]] = min(l[a[i]], i);
		r[a[i]] = i;
	}
	for (int i = 1; i <= x; i++)mxr[i] = max(mxr[i - 1], r[i]);
	for (int i = x; i >= 1; i--)mnl[i] = min(mnl[i + 1], l[i]);
	int R = x, L;
	while (R >= 1 && r[R] <= mnl[R + 1])R--;
	for (L = 1; L <= x && l[L] >= mxr[L - 1]; L++) {
		while (R < L || mxr[L - 1] > mnl[R + 1])R++;
		ans += x - R + 1;
	}
	if (L <= x) {
		while (R < L || mxr[L - 1] > mnl[R + 1])R++;
		ans += x - R + 1;
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Scalar Queries

 

题意：给定一个所有元素都不同的数列。一个区间的值为区间中所有数按照从小到大排序后，区间中每个数的值乘以它在区间中的下标，再求和。问所有区间的值之和。

树状数组+计数

对于位置 i ，有 i⋅(n−i+1)i\cdot(n-i+1) 个区间包含它。如果 a[i]a[i] 是整个数列的最小值，那么它的贡献就是 a[i]⋅i⋅(n−i+1)a[i]\cdot i\cdot (n-i+1)。

对于其它的数，对于一个区间 [l,r][l,r]，该区间中每多一个小于它的数，这个区间中它的贡献的系数就+1，所以对于每一个小于它的数，要计算它对这个数的系数的贡献，即有多少区间同时包含这两个数。最终把所有小于它的数对它系数的贡献求和，再加上本身的系数，就是它最终的系数。

离散化后树状数组维护权值作为下标的前缀和。从前往后遍历，对于当前位置 i，a[i]a[i] 对所有比它大的数做贡献，且包含它的区间左端点有 i 个。计算 a[i]a[i] 的系数时，就是树状数组中 a[i]a[i] 的前缀和乘右端点个数 n-i+1。这样就算出了所有位于 i 前面的数对 a[i]a[i] 的贡献，再从后往前遍历，算出后面的数对 a[i]a[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
38
39
40
41
42
43
44
45
#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;
int a[N], v[N];
ll sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i <= n; i+=lowbit(i))sum[i] += x;
}
ll qry(int r) {
	ll res = 0ll;
	for (int i = r; i > 0; i -= lowbit(i))res += sum[i];
	return res;
}
ll b[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); v[i] = a[i]; }
	sort(v + 1, v + n + 1);
	for (int i = 1; i <= n; i++)a[i] = lower_bound(v + 1, v + n + 1, a[i]) - v;
	for (int i = 1; i <= n; i++) {
		b[a[i]] = 1ll * i*(n - i + 1) % mod;
		b[a[i]] += qry(a[i])*(n - i + 1) % mod;
		b[a[i]] %= mod;
		add(a[i], i);
	}
	memset(sum, 0, sizeof(sum));
	for (int i = n; i >= 1; i--) {
		b[a[i]] += qry(a[i])*i%mod;
		b[a[i]] %= mod;
		add(a[i], n - i + 1);
	}
	ll ans = 0ll;
	for (int i = 1; i <= n; i++) {
		ans += 1ll * v[i] * b[i] % mod;
		ans%=mod;
	}
	printf("%lld\n", ans);
	return 0;
}