ZR#985

解法：

可以先假设每个区间中所有颜色都出现，然后减掉多算的答案。对每种颜色记录它出现的位置，则相邻两个位置间的所有区间都要减去，时间复杂度 $ O(n) $ 。

其实可以理解为加法原理的逆过程，即减法原理。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

#define N 100010

LL las[N],n,ans,x;

inline LL calc(LL n) {

    return n * (n + 1) / 2;

}

int main() {

    scanf("%lld",&n);

    ans = calc(n) * n;

    for(int i = 1 ; i <= n ; i++) {

        scanf("%lld",&x);

        ans -= calc(i - las[x] - 1);

        las[x] = i;

    }

    for(int i = 1 ; i <= n ; i++)

        ans -= calc(n - las[i]);

    printf("%lld\n",ans);

    return 0;

}

巴特西

ZR#985

ZR#985

解法：

最新文章

热门文章