【题解】HDU-4455 Substrings

Posted on In Disqus:

题目

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
#include <bits/stdc++.h>
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 << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(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("%lld\n", ans);
        }
    }
}