Indeedなう(予選B) D問題: 高橋くんと数列

補集合を思いつくのに時間がかかった。

問題:http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4

解法:「その数を1つでも含む連続する部分列」ではなく、「その数をひとつも含まない連続する部分列」を考え、それを可能な部分列の合計から引く。
連続する部分列と、列から左端と右端を選ぶのは1対1に対応し、その数は列がp個であったとすると、重複を許してp個から2個選ぶ場合の数になるから、通りとなる。本番書いたコードはかなり汚くてもうちょいキレイになりそう。
以下ソースコード

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)n; i++)

using namespace std;
typedef long long ll;

const int MAXN = 100100;
int a[MAXN];
vector<int> pos[MAXN];

int main(void) {
    int N, C;
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    ll all = (ll)(N+1) * N / 2;
    for (int i = 1; i <= C; i++) {
        int p = pos[i].size();
        ll minus = 0;
        if (p == 1) {
            ll n = pos[i][0];
            minus += (n+1)*n/2;
            n = N-pos[i][0]-1;
            minus += (n+1)*n/2;
        } else {
            for (int j = 0; j < p; j++) {
                if (j == 0) {
                    ll n = pos[i][j];
                    minus += (n+1)*n/2;
                } else if (j < p-1) {
                    ll n = pos[i][j] - pos[i][j-1] - 1;
                    minus += (n+1)*n/2;
                } else {
                    ll n = pos[i][j] - pos[i][j-1] - 1;
                    minus += (n+1)*n/2;
                    n = N-pos[i][j]-1;
                    minus += (n+1)*n/2;
                }
            }
        }
        cout << all-minus << endl;
    }
    return 0;
}