【题解】HDU

题目

http://acm.hdu.edu.cn/showproblem.php?pid=4455

题意

给定一个数组,对于每次询问,求所有长度为给定值的区间的不同数字个数之和。

题解

  • 考虑每个数的贡献,如果一个数在区间内出现了多次,那么只记第一次有贡献。

  • 考虑每个数,对于长度为 w 的区间,当区间左端点在 [l, r] 之间时产生了贡献。

  • 设 last[p] 为上一个与 p 这个位置上的数相同的数的位置

  • l[p] = max{last[p] + 1, p - w + 1}, r[p] = min{p, n - w + 1}

  • 令 r[p] = p,最后把多算的减掉(长度为 1 ~ w - 1 的后缀的不同数的个数之和)。

  • p 的贡献为 r[p] - l[p] + 1 = min{p - last[p], w},只要预处理 p - last[p] 并进行排序再求前缀和就行了。

  • 如果采用基数排序,那么可以省一个 log。

  • 看了看别人的题解,好像多为 dp,但是算法本质是一样的。

代码

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

using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "33[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void () { cout << "33[39;0m" << endl; }
template<typename T, typename... Args>
void (T a, Args... args) { cout << a << ' '; err(args...); }

const int maxn = 1E6 + 100;
int a[maxn], pos[maxn], up[maxn];
LL sum[maxn], ss[maxn], n, k;
bool vis[maxn];

int main() {
while (cin >> n && n) {
FOR (i, 0, n) scanf("%d", &a[i]);

memset(vis, 0, sizeof vis);
LL cnt = 0;
FORD (i, n - 1, -1) {
if (!vis[a[i]]) { vis[a[i]] = 1; ++cnt; }
ss[n - i] = ss[n - i - 1] + cnt;
} // ss[k] 为前 k 个后缀的不同数的个数和

memset(pos, -1, sizeof pos);
FOR (i, 0, n) {
up[i] = i - pos[a[i]]; // up[p] 为 p 这个位置上的数字的贡献的上限
pos[a[i]] = i; // 记录 a[i] 上一次出现的位置
}
sort(up, up + n);
FOR (i, 0, n) sum[i + 1] = sum[i] + up[i];

LL Q; cin >> Q;
while (Q--) {
scanf("%lld", &k);
LL len = upper_bound(up, up + n, k) - up; // len 为 up 中不大于 w 的个数
LL ans = sum[len] + (n - len) * k;
ans -= ss[k - 1];
printf("%lldn", ans);
}
}
}