洛谷 P11012 颜料
题意
给出长度为 \(n\) 的序列 \(a\)。定义一段区间 \([l,r]\) 的绚丽程度 \(X_{l,r}\) 为 \(\sum_{i=1}^{W}\sum_{j=i+1}^W\min(c_i,c_j)\)，其中 \(W\) 是值域，\(c_i\) 表示 \(a\) 序列 \([l,r]\) 中 \(i\) 出现的次数，求绚丽程度至少为 \(k\) 的区间长度最小值。
思路
考虑固定右端点 \(r\)，对于 \(l_1<l_2\) 有 \(X_{l_1,r} \ge X_{l_2,r}\)。
考虑固定左端点 \(l\)，对于 \(r_1<r_2\) 有 \(X_{l,r_1} \le X_{l,r_2}\)。
可以使用双指针求出最短的区间 \([l,r]\)。
对于每个 \(r\)，若当前 \([l,r]\) 绚丽程度大于 \(k\)，\(l\) 向右移动直到不能再动，统计答案后，\(r\) 向右移动。
我们需要一种快速的方式更新区间的绚丽程度。
由于双指针每次只删除或增加一个数，我们考虑如何快速统计增加或删除一个数的贡献。
对于一个数 \(x\)，记 \(s\) 为小于 \(x\) 的数的和，记 \(C\) 为在 \([x,W]\) 内的数的个数。
则 \(x\) 对绚丽程度的贡献为 \(s + (C-1)x\)。
因为小于 \(x\) 的数和 \(x\) 取 \(\min\) 结果为本身，大于等于 \(x\) 的数和 \(x\) 取 \(\min\) 结果为 \(x\)，减 \(1\) 是减去 \(x\) 本身。
动态维护这些值可以使用权值树状数组或权值线段树。
加入一个数 \(num\) 时，删除 \(c_{num}\) 的贡献，将 \(c_{num}\) 加一，加入 \(c_{num}\) 的贡献。
删除一个数 \(num\) 时，删除 \(c_{num}\) 的贡献，将 \(c_{num}\) 减一，加入 \(c_{num}\) 的贡献。
同时动态维护上面的所有值。
开两棵树状数组，一棵维护和，一棵维护个数即可。
时间复杂度：\(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 5;
int n, W, k, a[N], c[N], val;
template <typename T> inline void read(T& x) {
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
struct BIT {
int t[N];
void clear() {
memset(t, 0, sizeof(t));
}
void add(int x, int y) {
for (int i = x; i <= W; i += i & (-i)) t[i] += y;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= i & (-i)) res += t[i];
return res;
}
int query(int x, int y) {
return query(y) - query(x - 1);
}
} T1, T2;
// T1 维护和
// T2 维护个数
int calc(int num) { // num 的贡献
int res = 0;
res += T1.query(num - 1);
res += num * (T2.query(num, W) - 1);
return res;
}
void del(int num) { // 删数
val -= calc(c[num]); // 删除旧贡献
T1.add(c[num], -c[num]); // 维护树状数组
T2.add(c[num], -1);
c[num] --; // 更改 c[num]
if (c[num]) { // 加入新贡献
T1.add(c[num], c[num]);
T2.add(c[num], 1);
val += calc(c[num]);
}
}
void add(int num) { // 加数
if (c[num]) { // 删除旧贡献
val -= calc(c[num]); // 维护树状数组
T1.add(c[num], -c[num]);
T2.add(c[num], -1);
}
c[num] ++; // 更改 c[num]
T1.add(c[num], c[num]); // 加入新贡献
T2.add(c[num], 1);
val += calc(c[num]);
}
signed main() {
read(n), read(k);
for (int i = 1; i <= n; i ++) read(a[i]), W = max(a[i], W);
int l = 1, res = 1e9;
for (int i = 1; i <= n; i ++) {
add(a[i]); // 加入 i
while (val >= k) { // 向右移动 l
del(a[l ++]);
if (val < k) { // 移不动了
add(a[-- l]);
break;
}
}
if (val >= k) res = min(res, i - l + 1); // 统计答案
}
if (res == 1e9) cout << -1;
else cout << res;
return 0;
}