https://ac.nowcoder.com/acm/contest/375

B - 小A的排列

 

题意：给定 n,seedn,seed 以及 nn 的排列 p[]p[]，问 2×∑l=1n∑r=lnseed(l−1)∗n+rmidl,r2\times\sum\limits_{l=1}^n\sum\limits_{r=l}^nseed^{(l-1)*n+r}mid_{l,r}，其中 midl,rmid_{l,r} 为 区间 [l,r][l,r] 中数字的中位数。n≤104n\le 10^4

思维+链表

首先肯定是想着枚举区间，然后set或者线段树或者主席树之类的维护以下。但是这复杂度显然多了个 log⁡\log。

但区间还是要枚举的，在挪动到下一个区间时，需要 O(1)O(1) 更新中位数，所以需要一个维护权值的链表。

链表中 nxt 维护的是在当前区间中，比 xx 大的数中最小的那个数字（即当前区间排序后 xx 后一个数）。pre 维护的是，比 xx 小的数中最大的那个数字（即当前区间排序后 xx 前一个数字）。

然而如果是插入的话就必须要知道插入的位置，这样又不行，所以要变成删除，从大到小枚举区间，使得在上一个区间的基础上删除左端点得到下一个区间。

因此只要在挪动到下一个区间的时候分类讨论以下就能知道 两个中位数 变成了哪两个新的。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n; ll seed;
int p[N];
ll Pow[N];
struct X
{
	int pre, nxt;
}A[N], B[N];
void del(X a[], int i) {
	int pr = a[i].pre, nx = a[i].nxt;
	a[pr].nxt = nx;
	a[nx].pre = pr;
}
int main() {
	scanf("%d%lld", &n, &seed);
	for (int i = 1; i <= n; i++)A[i].pre = i - 1, A[i - 1].nxt = i;
	for (int i = 1; i <= n; i++)B[i].pre = i - 1, B[i - 1].nxt = i;
	Pow[0] = 1;
	for (int i = 1; i <= n; i++)Pow[i] = Pow[i - 1] * seed%mod;
	for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
	ll ans = 0;
	int M1 = (n + 1) / 2, M2 = (n + 2) / 2 , m1, m2;
	for (int r = n; r >= 1; r--) {
		ll sd = 1;
		for (int i = 1; i <= n; i++)A[i] = B[i];
		m1 = M1, m2 = M2;
		for (int l = 1; l <= r; l++) {
			ans = (ans + sd * Pow[r] % mod * (m1 + m2)) % mod;
			sd = sd * Pow[n] % mod;
			int x = p[l];
			if ((r - l + 1) & 1) {
				if (x == m1) {
					m1 = A[x].pre;
					m2 = A[x].nxt;
				}
				else if (x < m1) {
					m2 = A[m1].nxt;
				}
				else {
					m1 = A[m2].pre;
				}
			}
			else {
				if (x <= m1)m1 = m2;
				else m2 = m1;
			}
			del(A, x);
		}
		int x = p[r];
		if (r & 1) {
			if (x == M1) {
				M1 = B[x].pre;
				M2 = B[x].nxt;
			}
			else if (x < M1) {
				M2 = B[M1].nxt;
			}
			else {
				M1 = B[M2].pre;
			}
		}
		else {
			if (x <= M1)M1 = M2;
			else M2 = M1;
		}
		del(B, x);
	}
	printf("%lld\n", ans);
	return 0;
}