[Code+#1] Yazid 的新生舞会
经典老题，洛谷原题链接：https://www.luogu.com.cn/problem/P4062。
线性做法！
由于出现次数严格大于 (dfrac{r-l+1}2)，所以一个区间最多被一个众数贡献。因此考虑求出每个数作为符合题意的众数出现的区间个数之和即答案。
我们设序列 (s_k) 表示 (k) 的出现次数前缀和，即 (s_{k,i}=sum_{j=1}^i[a_j=k])。根据题意，一个区间 ([l+1,r]) 被 (k) 贡献当且仅当 (s_{k,r}-s_{k,l}>dfrac{r-l}2)。稍作变形得 (2s_{k,r}-r>2s_{k,l}-l)。这就很显然了，即求 (2s_{k,i}-i) 的逆序对数。
但是我们不能对每个 (k) 都 (nlog n) 求一遍逆序对。注意到出现次数总数为 (n)，也就是说对于固定的 (k) 可能有一大串 (s_k)（(s_{k,p}sim s_{k,q})）都相同，注意到计算贡献其实就是询问 (q-p+1) 段前缀和，且右端点递减，即矩形 + 等腰直角三角形。这个显然可以线段树维护区间 (sum v_i)（矩形）以及 (sum i imes v_i)（用梯形减去矩形就得到了等腰直角三角形）。在线段树中加入这些值（(s_{k,p}-psim s_{k,q}-q)）就是区间加了。
此外清空不能直接 memset 否则复杂度会退化为 (n^2)，需要记录做过的操作然后撤销。时间复杂度 (mathcal{O}(nlog n))。
用线段树被卡常了怎么办？还有树状数组。注意到一次修改实际上是在差分数组上区间加，即对于每个 (iin [p,q])，都给 (s_{k,p}-isim mathrm{upperbound}) 加上 (1)，一次修改是差分数组单点加，两次就是区间加。考虑维护差分数组的差分数组，那么区间求和就是求三次前缀和：我们维护的东西的前缀和是差分数组，差分数组的前缀和是原数组，原数组的前缀和就是我们要单点求的东西。
对于这种树状数组维护高阶前缀和的问题，一般考虑在 (p) 处加上 (1) 对 (q) 的贡献：(sum_{i=p}^{q}i-p+1)：一阶差分数组在 (p) 处 (+1) 会在原数组前缀和的 (q) 处贡献 (q-p+1)，而二阶差分数组在 (p) 处 (+1) 会在一阶差分数组的 (psim q) 处都加上 (1)，故有此式。先乘以 (2)（因为有等差数列求和，计算除以 (2) 不方便）稍作化简得到 ((p+q)(q-p+1)+2(1-p)(q-p+1))，这里出现了 (q) 的 (0,1,2) 次项，分别维护其系数即 ((p^2-3p+2)q^0+(-2p+3)q+q^2)，最后答案除以 (2) 即可。
const int N = 5e5 + 5;
ll n, type, ans;
vint buc[N];
struct BIT {
ll a0[N << 1], a1[N << 1], a2[N << 1];
void add(ll x, int v) {
ll c0 = (x * x - 3 * x + 2) * v, c1 = (3 - 2 * x) * v;
while(x <= n * 2 + 1) a0[x] += c0, a1[x] += c1, a2[x] += v, x += x & -x;
}
void add(int l, int r, int v) {add(l + n + 1, v), add(r + n + 2, -v);}
ll query(int x) {
ll t = x, c0 = 0, c1 = 0, c2 = 0;
while(x) c0 += a0[x], c1 += a1[x], c2 += a2[x], x -= x & -x;
return c0 + c1 * t + c2 * t * t;
}
ll query(int l, int r) {return query(r + n + 1) - query(l + n);}
} tr;
vpii d;
void doit(int l, int r) {tr.add(l, r, 1), d.pb(l, r);}
void discard() {for(pii it : d) tr.add(it.fi, it.se, -1); d.clear();}
void solve(vint &cur) {
for(int i = 1; i < cur.size(); i++) {
int pre = cur[i - 1], now = cur[i], s = i - 1 << 1;
if(pre + 1 < now) {
int l = s - now + 1, r = s - pre - 1;
if(i > 1) ans += tr.query(l - 1, r - 1);
doit(l, r);
}
if(i < cur.size() - 1) {
int p = i * 2 - now;
ans += tr.query(p - 1, p - 1), doit(p, p);
}
}
discard();
}
int main(){
cin >> n >> type;
for(int i = 0; i < n; i++) buc[i].pb(0);
for(int i = 1; i <= n; i++) buc[read()].pb(i);
tr.add(0, 0, 1);
for(int i = 0; i < n; i++) buc[i].pb(n + 1), solve(buc[i]);
cout << ans / 2 << endl;
return 0;
}
能不能再给力一点啊？可以。
不妨设 (d_i) 表示 (2s_{k,i}-i)。
observation 1：对于固定的众数 (k)，最多有 (2s_{k,n}) 个位置对答案有贡献。即对于所有 (k)，使得 (d_p>min_{i=1}^{p-1}d_i) 的 (p) 个数之和是 (mathcal{O}(n)) 的。感性理解即若出现的 (0 (a_i eq k)) 足够多，无论左端点怎么往左扩展都无法使 (k) 符合条件。
上述结论使我们不需要求原数组的区间和，只需要对于连续递减的一段 (d_i)，查询单点即求出二阶差分数组的二阶前缀和，直到当前的 (d_i) 小于 (d_i) 的前缀最小值，因为再枚举下去对答案的贡献为 (0)（注意到我们是给 ([d_i+1,infty]) 区间加 (1) ），直接忽略。可以显著减小常数。但问题仍不弱于求逆序对个数。
observation 2：(|d_i-d_{i-1}|leq 1)。
上述结论保证了每次查询的间隔不超过 (1)，除了对于连续递减的一段 (d_{lsim r}) 的最后一次查询（不妨设为位置 (p)）与 (d_{r+1}) 之间会有一个间隔，但是忽略这个间隔这并不影响结果，因为 (d_{r+1}-1sim d_p-1) 这一段并没有进行任何修改：它小于 (d_l) 的前缀最小值，自然不会产生任何贡献。那么由于指针的移动距离之和是 (mathcal{O}(n)) 的，因此直接维护二阶差分数组，一阶差分（基于二阶差分数组修改）和当前位置的值（基于一阶差分修改）即可做到线性。
const int N = 5e5 + 5;
int n, type, add[N << 1], del[N << 1], s[N];
int cnt, hd[N], nxt[N << 1], val[N << 1];
void link(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, val[cnt] = v;}
void modify(int l, int r, int v) {add[l + N] += v, del[r + N + 1] += v;}
ll ans;
int main(){
cin >> n >> type, modify(1, 1, 1);
for(int i = 1; i <= n; i++) link(read(), i);
for(int p = 0; p < n; p++) {
if(!hd[p]) continue;
int minp = 0, id = 1;
static int tmp[N]; tmp[0] = 0, tmp[1] = n + 1;
for(int i = hd[p]; i; i = nxt[i]) tmp[++id] = val[i];
reverse(tmp + 1, tmp + id + 1);
ll dc = 0, c = 0;
for(int i = 1; i <= id; i++) {
int pre = tmp[i - 1], cur = tmp[i];
int r = s[i - 1] - 1, l = r - (cur - pre) + 2;
if(l <= r && pre) {
int lim = max(minp, l);
for(int j = r; j >= lim; j--) {
c -= dc, ans += c;
dc += del[j + N + 1] - add[j + N + 1];
}
}
if(i == id) break;
modify(l + 1, r + 1, 1);
dc += add[l + N + 1] - del[l + N + 1];
c += dc, ans += c, s[i] = l + 1;
modify(s[i] + 1, s[i] + 1, 1), cmin(minp, l);
}
for(int i = 1; i < id; i++)
modify(s[i], s[i - 1], -1),
modify(s[i] + 1, s[i] + 1, -1);
}
cout << ans << endl;
return cerr << clock() << endl, flush(), 0;
}