题目链接
题解
区间众数的个数 $>$ 区间长度一半 称这个区间有主元素，主元素就是这个众数；
题意：求数组中有多少个区间有主元素;
考虑一个子问题：每一种数作为主元素的贡献；
例如给定数组 $p = [3,2,1,3,3,2]$，并考虑 $3$ 作为主元素的贡献；
我们可以将是数字 $3$ 的记为 $1$ ，不是的记为 $-1$；
| $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | |
|---|---|---|---|---|---|---|
| $p$ | $3$ | $2$ | $1$ | $3$ | $3$ | $2$ |
| $w$ | $1$ | $-1$ | $-1$ | $1$ | $1$ | $-1$ |
于是子问题变成求 $w$ 中有多少个区间和大于 $0$，例如区间 $[3,5]$ 的和为 $1$ ，所以这个区间可行，而区间 $[2,5]$ 的和为 $0$，所以这个区间不可行；
我们对 $w$ 求一个前缀和，记为 $d$，如果 $d_r - d_{l-1} > 0$，也就是对于 $d_r$ 查找 $r$ 之前有多少个比 $d_r$ 小的数字，那么区间 $[l,r]$ 满足要求；
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | |
|---|---|---|---|---|---|---|---|
| $p$ | 无 | $3$ | $2$ | $1$ | $3$ | $3$ | $2$ |
| $w$ | $0$ | $1$ | $-1$ | $-1$ | $1$ | $1$ | $-1$ |
| $d$ | $0$ | $1$ | $0$ | $-1$ | $0$ | $1$ | $0$ |
例如对于 $r = 5$ ，$r$ 前比 $d_r$ 小的数字有 $4$ 个，分别是 $l-1 = [4,3,2,0]$ 的时候，也就是区间 $[5,5],[4,5],[3,5],[1,5]$ 满足要求；
于是可以对每一种数字，求出 $w$，求出 $d$，枚举 $d_i$，查找 $i$ 前有多少个比 $d_i$ 小的数字，用树状数组维护权值，显然这样的复杂度是 $O(n^2logn)$的，不可取；
我们记录下每一种数字在数组中的位置，例如数字 $3$，它的位置有 $pos_3 = [1,4,5]$，如果能在 $O(pos_i.size())$ 的时空复杂度下(可以加个$log$)求出这种数字的贡献，那么枚举每一种数字算贡献整体就是 $O(nlogn)$ 的了；
$d$ 是连续的，$pos_3 = [1,4,5]$ 可以将 $d$ 分为 $4$ 个部分，分别是 $[0,0],[1,3],[4,4],[5,6]$ ，这四个部分都是等差数列，对于$[1,3]$区间内的每个值，在该值前且比该值小的数字只能来自于$[1,3]$这部分之前，不能来自于 $[1,3]$ 这部分本身；
设法将每一部分同时处理，如有一部分 $P_i$，$P_i$这部分的答案来自于 $P_i$ 之前的部分，对 $P_i$ 这部分是一个等差数列 $[y,y-1,y-2, \dots,x]$，那么 $P_i$ 部分插入到树状数组中就是区间 $[x,y]$ 加 $1$；
设 $B_i$ 为权值的前缀和，$B_i = \sum_{j=1}^{i}C_j$，那么对于 $P_i$ 部分内的每一个值 $d_i$，$d_i$ 的贡献就等于 $B_{d_i-1}$，那么对于这一整个部分 $P_i$，值为 $[x,y]$，整体贡献就是 $\sum_{i=x-1}^{y-1}B_i$，设 $A_i$ 为权值的前缀和的前缀和，也就是 $B_i$ 的前缀和 $\sum_{j=1}^{i}B_j$，那么整体贡献就是 $A_{y-1} - A_{x-2}$；
于是将问题转变为了，区间 $[x,y]$ 加 $1$，和求二阶前缀和；
区间 $[x,y]$加一个数，求一阶前缀和就是区间加数，区间求和的洛谷线段树模板题1，当然可以用树状数组实现；
和模板题同样将权值 $C_i$差分，差分后的数组位 $D_i$，于是问题转变为单点修改，求三阶前缀和；
$A_x = \sum_{i=1}^{x} \sum_{j=1}^{i} \sum_{k=1}^{j} D_k$
$A_x$
$= B_1 + B_2 + B_3 + \dots + B_x$
$= C_1 + (C_1+C_2) + (C_1+C_2+C_3) + \dots + (C_1+C_2+C_3+\dots+C_x)$
$= xC_1+(x-1)C_2+(x-2)C_3+\dots+(x-n+1)C_n+\dots+C_x$
$= xD_1+(x-1)(D_1+D_2)+(x-2)(D_1+D_2+D_3)+\dots+(x-n+1)(D_1+D_2+\dots+D_n)+\dots+(D_1+D_2+D_3+\dots+D_n)$
$= \frac{(x+1)x}{2}D_1+\frac{x(x-1)}{2}D_2+\frac{(x-1)(x-2)}{2}D_3+\dots+\frac{(x-n+2)(x-n+1)}{2}D_n+\dots+D_x$
$= \sum_{n=1}^{x}\frac{(x-n+2)(x-n+1)}{2}D_n$
$= \sum_{n=1}^{x}n^2D_n + \frac{-2x+3}{2}\sum_{n=1}^{x}nD_n + \frac{x^2+3x+2}{2}\sum_{n=1}^{x}D_n$
用三个树状数组维护 $i^2D_i$，$iD_i$，$D_i$即可；
1 |
|