校内赛-T1-元素平衡

题目描述

有一个序列 $a$，序列中每个元素有一个属性 $a_i$，其中 $1\le a_i\le m$

求所有区间 $[l,r]$，满足区间中所有属性的元素均有出现，且每种属性的元素数量相等

$n\le 10^5,m\le 50$

Solution

我们考虑维护一个有 $m-1$ 位 $vector$ 来记录一个前缀和

对于元素 $a_i$，如果 $a_i<m$，那么我们将 $vector$ 的 $a_i$ 位加 $1$，如果 $a_i=m$，那么我们将整个 $vector$ 减 $1$

可以发现前缀和相同的位置 $i$ 和 $j$ 所形成的区间 $[i,j]$ 一定满足条件，至于如何维护 $vector$ 的前缀和，直接扔到 $map$ 里就行

时间复杂度 $O(nm\log n)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#define gc getchar
#define ll long long
#define cn const node
#define cQ const Queue
#define maxn 300010
#define maxm 51
using namespace std;

int read() {
    int x = 0, f = 0; char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
}

int n, m, a[maxn];

vector<int> b;

map<vector<int>, int> ma; 

ll ans;
int main() {
    n = read(); m = read();
    for (int i = 1; i <= m; ++i) b.push_back(0); ma[b] = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        if (a[i] == m) {
            for (int j = 1; j <= m; ++j) --b[j];
            ans += ma[b]++;
            continue ;
        }
        b[a[i]]++; ans += ma[b]++; 
    } cout << ans << endl; 
    return 0;
}