小 Ad-Hoc——AT_abc484D

· · 题解

0x01 思路

不那么难的 Ad-Hoc。

稍作观察，思考怎样才能使其产生本质不同之排列。

如果每个数都不同，那么显然每种操作方式都可以造就独特的排列。

那么有相同的数怎么办？

摆弄摆弄样例就可以发现，对于每个 a_i，如果移到和它相同位置或者之前的 a_j=a_i(j≤i)，就不会产生新的排列方式；而如果它前面的 a_{i-1} 和 a_i 相等，则 a_i 也不会对答案产生贡献。

譬如说 1\,4\,{\color{violet}1}，把 {\color{violet}1} 移动使序列变成 {\color{violet}1}\,1\,4 和 1\,{\color{violet}1}\,4 本质是相同的，则前者即可不计入计算。而如果放回原位也不会有任何收益。

再如 9\,{\color{#11FF88}1}\,{\color{cyan}1}，{\color{cyan}1} 移动使序列变成 {\color{cyan}1}\,9\,{\color{#11FF88}1}、{\color{#11FF88}1} 移动使序列变成 {\color{#11FF88}1}\,9\,{\color{cyan}1} 本质也无区别。所以可以只处理前者。

所以开一个桶 sum，表示处理到每个 a_i 时共遇到多少个和 a_i 相等的数。

顺序处理 a_i 时，先往 sum_{a_i} 加 1，接着如果 a_i≠a_{i - 1} 则将答案增加「此前遇到的与 a_i 不等的数的个数」。

如何求此前遇到的与 a_i 不等的数的个数？这个问题相较而言就略显「白痴」了：i-sum_{a_i}。

记得原序列也是一个合法答案。

0x02 代码呈现

代码超短。

#include "bits/stdc++.h"
using namespace std;
#define ch(opt, tar, ...) (tar = opt({tar, __VA_ARGS__}))
#define inlfc __attribute__((always_inline)) inline
#define isz(x) ((int)x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll ans = 1;
    cin >> n;
    vector<int> a(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[a[i]] ++;
        if (a[i] != a[i - 1]) ans += i - sum[a[i]];
    }
    cout << ans;
    return 0;
}

可惜 C 题耗费了过多时间，并且不会平衡树。