Učiteljica

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAX 100002
int N, K;
int a[MAX];

vector<int> pos[MAX];

struct Event {
    int t, r1, r2;
};

vector<Event> events[MAX];

struct Segtree {
    struct Node {
        int range_min = 0, lazy = 0, count_min = 1;
    };

    int n;
    Node t[4 * MAX];

    Segtree() { }

    void build(int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = { 0, 0, 1 };
            return;
        }
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        t[v] = combine(t[2 * v], t[2 * v + 1]);
    }

    Node combine(const Node &a, const Node &b) {
        if (a.range_min == b.range_min) {
            return { a.range_min, 0, a.count_min + b.count_min };
        } else if (a.range_min < b.range_min) {
            return { a.range_min, 0, a.count_min };
        } else {
            return { b.range_min, 0, b.count_min };
        }
    }

    void push(int v)
    {
        t[2 * v].range_min += t[v].lazy;
        t[2 * v].lazy += t[v].lazy;
        t[2 * v + 1].range_min += t[v].lazy;
        t[2 * v + 1].lazy += t[v].lazy;
        t[v].lazy = 0;
    }

    void update(int v, int tl, int tr, int l, int r, int d)
    {
        if (r < tl || tr < l || l > r) {
            return;
        }
        if (l <= tl && tr <= r) {
            t[v].lazy += d;
            t[v].range_min += d;
            return;
        }
        push(v);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, r, d);
        update(2 * v + 1, tm + 1, tr, l, r, d);
        t[v] = combine(t[2 * v], t[2 * v + 1]);
    }

    Node query(int v, int tl, int tr, int l, int r)
    {
        if (r < tl || tr < l || l > r) {
            return { INT_MAX, 0, 0 };
        }
        if (l <= tl && tr <= r) {
            return t[v];
        }
        push(v);
        int tm = (tl + tr) / 2;
        return combine(
            query(2 * v, tl, tm, l, r),
            query(2 * v + 1, tm + 1, tr, l, r)
        );
    }

    ll count_zeros(int l, int r) {
        Node t = query(1, 1, n, l, r);
        return (t.range_min == 0 ? t.count_min : 0);
    }
} s[17];

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        pos[i].push_back(0);
    }
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= N; i++) {
        pos[i].push_back(N + 1);
    }

    for (int x = 1; x <= N; x++) {
        for (int j = 1; j <= K; j++) {
            for (int i = 1; i + j < pos[x].size(); i++) {
                events[pos[x][i-1] + 1].push_back({+j, pos[x][i+j-1], pos[x][i+j] - 1});
                events[pos[x][i]].push_back({-j, pos[x][i+j-1], pos[x][i+j] - 1});
                // events[pos[x][i-1] + 1].push_back({+j, 0, 0});
                // events[pos[x][i]].push_back({-j, 0, 0});
            }
        }
        /*
        for (int i = 1; i < pos[x].size() - 2; i++) {
            events[pos[x][i-1] + 1].push_back({+2, pos[x][i], pos[x][i+2] - 1});
            events[pos[x][i]].push_back({-2, pos[x][i], pos[x][i+2] - 1});
        }
        for (int i = 1; i < pos[x].size() - 3; i++) {
            events[pos[x][i-1] + 1].push_back({+3, pos[x][i], pos[x][i+3] - 1});
            events[pos[x][i]].push_back({-3, pos[x][i], pos[x][i+3] - 1});
        }
        for (int i = 1; i < pos[x].size() - 4; i++) {
            events[pos[x][i-1] + 1].push_back({+4, pos[x][i], pos[x][i+4] - 1});
            events[pos[x][i]].push_back({-4, pos[x][i], pos[x][i+4] - 1});
        }
        */
    }

    for (int i = 1; i < (1 << K); i++) {
        s[i].n = N;
        s[i].build(1, 1, N);
    }

    ll ans = N;
    ans *= ans + 1;
    ans /= 2;

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

        for (auto &[t, r1, r2] : events[i]) {
            if (t > 0) {
                for (int j = 1; j < (1 << K); j++) {
                    if (j & ((1 << t) >> 1)) {
                        s[j].update(1, 1, N, r1, r2, +1);
                    }
                }
            }
        }

        // cout << "l = " << i << '\n';
        for (int j = 1; j < (1 << K); j++) {
            if (__builtin_popcount(j) & 1) {
                // cout << j << ' ' << -s[j].count_zeros(i, N) << '\n';
                ans -= s[j].count_zeros(i, N);
            } else {
                // cout << j << ' ' << s[j].count_zeros(i, N) << '\n';
                ans += s[j].count_zeros(i, N);
            }
        }
        // cout << "\n";

        for (auto &[t, r1, r2] : events[i]) {
            if (t < 0) {
                for (int j = 1; j < (1 << K); j++) {
                    if (j & ((1 << -t) >> 1)) {
                        s[j].update(1, 1, N, r1, r2, -1);
                    }
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}