题目大意
有 (n) 个非负整数 (a_1,a_2,dots,a_n) ，求有多少个区间 ([l,r]) ，满足 (a_l,a_{l+1},dots,a_r) 中的众数出现次数大于 (dfrac{r-l+1}{2})。
其中， (1 leq n leq 5 imes 10^5) ， (0 leq a_i leq n - 1) 。
题解
一、根号做法
来自初二dalao (color{black}{ extbf{l}}color{red}{ extbf{by}}) 的巧妙做法OrzOrzOrz。
真·比你小还比你强。
观察部分分，当 (type = 2) 时，容易发现，满足条件的子区间长度不超过 (2 imes 15)。
于是我们可以从 (1) 到 (n) 枚举 (l) ，在从 (l) 到 (l + 30 - 1) 枚举 (r) ，枚举时不断更新当前子区间的众数，并判断是否满足条件。
时间复杂度为 (O(30n)) 。
继续观察部分分，当 (type = 3) 时（ (type = 1) 的情况实际上是 (type = 3) 的情况的子集），不同 (a_i) 的数量很少，最多只有 (8) 种。
思考若一个区间众数为 (m) ，众数的数量为 (c(m)) ，若这个区间满足要求，则必须保证 (c(m)) 大于区间长度的一半，即 (c(m) > (r - l + 1) - c(m)) 。
移项，得 (2c(m) > r - l + 1) 。
我们设区间 ([1,i]) 中出现 (m) 的数量为 (s(i)) ，代入上式，得 (2left(s(r) - s(l - 1)
ight) > r - l + 1) 。
移项，得 (2s(r) - r > 2s(l - 1) - (l - 1)) 。
显然我们可以用树状数组等数据结构维护 (2s(i) - i) 。
所以我们可以先从 (0) 到 (7) 枚举，设当前枚举到的数为 (num)，再从 (1) 到 (n) 枚举 (a_i) ，算出当前的 (2s(i) - i) 并 insert ，每次贡献的答案为 (2s(j) - j) 的数量，其中 (0 leq j < i) 且 (2s(j) - j < 2s(i) - i) 。
时间复杂度为 (O(8nlog n))
然而上面的做法貌似不能过部分分，所以还要继续优化。
观察得 (2s(i) - i = egin{cases} 2s(i - 1) - (i - 1) + 1 & a_i = m \ 2s(i - 1) - (i - 1) - 1 & a_i
ot = m end{cases})
所以我们可以不用树状数组来维护。
我们设 (sum = sumlimits_{j = 1}^{i}left[2s(j) - j leq 2s(i) - i
ight]) ，设 (t(2s(i) - i) = sumlimits_{j = 1}^{i}left[2s(j) - j = 2s(i) - i
ight]) 。
显然，每枚举一个 (a_i) ， (t(2s(i) - i) gets t(2s(i) - i) + 1) 。
当 (a_i = m) 时， (sum gets sum + t(2s(i) - i)) ；
当 (a_i
ot = m) 时， (sum gets sum - t(2s(i - 1) - (i - 1)) + 1) 即 (sum gets sum - t(2s(i) - i + 1) + 1) 。
显然时间复杂度为 (O(8n)) 。
此时我们考虑 (type = 0) 的情况即正解。 (type = 2) 时满足条件的子区间长度较短， (type = 3) 时满足条件的子区间内众数的种类较少。
设满足条件的子区间的最大长度为 (p) ，则按照 (type = 2) 的做法来做时间复杂度为 (O(pn)) 。
设满足条件的子区间的众数最多数量为 (q) ，其实就是不同 (a_i) 的数量，则按照 (type = 3) 做法来做时，时间复杂度为 (O(qn)) 。
考虑正解，我们是否可以综合两种做法的优点？
直接说正解，我们设 (a_i) 在序列里出现的次数为 (C(a_i)) ，则我们可以先做一次 (type = 2) 的做法，只计算 (m) 满足 (C(m) leq sqrt{n}) 的贡献，显然 (p leq 2sqrt{n}) ，则这一次操作的复杂度为 (O(2nsqrt{n})) 。
然后我们从 (0) 到 (n - 1) 枚举数 (num) ，若 (C(num) > sqrt{n}) ，则做一次 (type = 3) 的做法。
因为 (sum C(num)left[C(num) > sqrt{n}
ight] leq n) 且我们只有满足 (C(num) > sqrt{n}) 时才进行操作，所以 $ q leq dfrac{n}{sqrt{n}} = sqrt{n}$ 。所以做 (type = 3) 的做法的时间复杂度为 (O(nsqrt{n})) 。
综合起来，总的时间复杂度为 (O(nsqrt{n})) 。
（不过我的常数太大了，在洛谷上会T一个点。。。）
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAX_N (500000 + 5)
using std::sqrt;
using std::memset;
int n;
int a[MAX_N];
int cnt[MAX_N], vis[MAX_N];
int t[MAX_N * 2];
long long ans;
int Read()
{
int res = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res;
}
int main()
{
n = Read();
Read();
for (int i = 1; i <= n; ++i)
{
a[i] = Read();
++cnt[a[i]];
}
const int plus = n + 1;
const int sqrtn = sqrt(n);
int num, mode;
for (int i = 1; i <= n; ++i)
{
num = 0;
for (int j = i; j <= n && j - i + 1 <= sqrtn + sqrtn; ++j)
{
++vis[a[j]];
if (vis[a[j]] > num) num = vis[a[j]], mode = a[j];
if (num + num - (j - i + 1) > 0 && cnt[mode] <= sqrtn) ++ans;
}
for (int j = i; j <= n && j - i + 1 <= sqrtn + sqrtn; ++j)
{
--vis[a[j]];
}
}
int cur, sum;
for (int i = 0; i < n; ++i)
{
if (cnt[i] <= sqrtn) continue;
memset(t, 0, sizeof t);
cur = plus;
sum = 1;
t[cur] = 1;
for (int j = 1; j <= n; ++j)
{
if (a[j] == i)
{
++cur;
++t[cur];
sum += t[cur];
}
else
{
--cur;
++t[cur];
sum = sum - t[cur + 1] + 1;
}
ans += sum - t[cur];
}
}
printf("%lld", ans);
return 0;
}
更多做法？见下！
二、分治做法
来自初一dalao (color{black}{ extbf{c}}color{red}{ extbf{zz}}) 的巧妙做法OrzOrzOrz。
真·比你小还比你强。
我们先证明下面的结论：
- 对于 ([l,r]) , 若 (exists k in [l,r)) ， ([l,k]) 中不存在出现次数大于 (dfrac{k-l+1}{2}) 的众数，且 ((k,r]) 中不存在出现次数大于 (dfrac{r - k}{2}) 的众数，则 ([l,k]) 中不存在出现次数大于 (dfrac{r- l+1}{2}) 的众数。
证明：
设 ([l,r]) 中 (a_i) 的出现次数为 (c_{[l,r]}(a_i)) 。
由上得 (forall c_{[l,k]}(a_i) leq dfrac{k - l + 1}{2},c_{(k,r]}(a_i) leq dfrac{r - k}{2}) 。
两个加起来得到 (forall c_{[l,r]}(a_i) leq dfrac{r - l + 1}{2}) 。
故命题得证。
对于 ([l,r]) , 若 (exists k in [l,r)) ， ([l,k]) 中存在出现次数大于 (dfrac{k-l+1}{2}) 的众数，且 ((k,r]) 中不存在出现次数大于 (dfrac{r - k}{2}) 的众数，则 ([l,k]) 中可能存在出现次数大于 (dfrac{r- l+1}{2}) 的众数，这个众数若存在，一定为 ([l,k]) 中的众数。
对于 ([l,r]) , 若 (exists k in [l,r)) ， ([l,k]) 中不存在出现次数大于 (dfrac{k-l+1}{2}) 的众数，且 ((k,r]) 中存在出现次数大于 (dfrac{r - k}{2}) 的众数，则 ([l,k]) 中可能存在出现次数大于 (dfrac{r- l+1}{2}) 的众数，这个众数若存在，一定为 ((k,r]) 中的众数。
对于 ([l,r]) , 若 (exists k in [l,r)) ， ([l,k]) 中存在出现次数大于 (dfrac{k-l+1}{2}) 的众数，且 ((k,r]) 中存在出现次数大于 (dfrac{r - k}{2}) 的众数，则 ([l,k]) 中可能存在出现次数大于 (dfrac{r- l+1}{2}) 的众数，这个众数若存在，一定为 ([l,k]) 或 ((k,r]) 中的众数。
下三条证明过程与第一条类似，这里就不写了（其实是懒）
所以我们可以设这个 (k) 为 (mid) 即 (leftlceildfrac{r - l + 1}{2}
ight
ceil) ，然后先分治处理 ([l,mid]) 和 ((mid,r]) ，再处理 ([l,r]) 。
处理 ([l,r]) 的具体过程如下。
我们先分别从 (mid) 向 (l) 枚举，从 (mid + 1) 向 (r) 枚举，记录 ([i,mid]) 和 ((mid,i]) 中出现次数大于区间长度一半的众数。
然后枚举刚刚记录的每一个众数 (q_i)，从 (mid) 向 (l) 枚举，用一个桶记录 (2c_{[i,mid]}(q_i) - (mid - i + 1)) 出现次数，然后从 (mid + 1) 向 (r) 枚举，算出当前的 (2c_{(mid,i]}(q_i) - (i - mid)) ，然后贡献答案，做法与上面的根号做法中的 (type=3) 部分相似。
#include <cstdio>
#define MAX_N (500000 + 5)
int n;
int a[MAX_N];
int cnt[MAX_N];
int q[MAX_N], vis[MAX_N], len;
int s[MAX_N * 2], t[MAX_N * 2];
long long ans;
int Read()
{
int res = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res;
}
void Solve(int l, int r)
{
if (l == r)
{
++ans;
return;
}
int mid = l + r >> 1;
Solve(l, mid);
Solve(mid + 1, r);
for (int i = mid; i >= l; --i)
{
++cnt[a[i]];
if (cnt[a[i]] + cnt[a[i]] > mid - i + 1 && !vis[a[i]])
{
q[++len] = a[i];
vis[a[i]] = 1;
}
}
for (int i = mid; i >= l; --i)
{
--cnt[a[i]];
}
for (int i = mid + 1; i <= r; ++i)
{
++cnt[a[i]];
if (cnt[a[i]] + cnt[a[i]] > i - mid && !vis[a[i]])
{
q[++len] = a[i];
vis[a[i]] = 1;
}
}
for (int i = mid + 1; i <= r; ++i)
{
--cnt[a[i]];
}
const int plus = n + 1;
int p, cur;
for (int i = 1; i <= len; ++i)
{
p = q[i];
vis[p] = 0;
cur = plus;
s[cur] = 0;
for (int j = mid; j >= l; --j)
{
if (a[j] == p) ++cur;
else --cur;
++t[cur];
if (cur >= plus) ++s[plus];
}
cur = plus;
for (int j = mid + 1; j <= r; ++j)
{
if (a[j] == p)
{
--cur;
s[cur] = s[cur + 1] + t[cur];
}
else
{
++cur;
s[cur] = s[cur - 1] - t[cur - 1];
}
ans += s[cur] - t[cur];
}
cur = 0 + plus;
for (int j = mid; j >= l; --j)
{
if (a[j] == p) ++cur;
else --cur;
--t[cur];
}
}
len = 0;
}
int main()
{
n = Read();
Read();
for (int i = 1; i <= n; ++i)
{
a[i] = Read();
}
Solve(1, n);
printf("%lld", ans);
return 0;
}
还要更多做法？见下！
三、线段树做法
来自 (color{grey}{huge{ ext{蒟蒻}}}) 自己yy出来的sb做法。。。
然而在考场上想到了，结果以为是个暴力就懒得打，考后才发现是正解。
马上就高一了，被上面两位初中dalao爆踩，要努力啊。
（待填坑）
真没了。