洛谷P2048 【[NOI2010] 超级钢琴】题解

$\texttt{Description}$

给你一个长度为 $n$ 的序列，要求求出和前 $k$ 小的，长度在 $L,R$ 之间的不同子串的和。两个子串不同当且仅当他们的起点和终点至少有一个不同。

$\texttt{Data Range:} n\leq 5\times 10^5,k\leq 5\times 10^5$

$\texttt{Solution}$

直接枚举所有子串然后排序？当然可行，但是时间空间双爆炸。

对于这种只求前 $k$ 小/大的，先考虑把所有可能成为当前最小/大的值放入堆中。

我们把起点为 $i(1\le i\le n)$ 的最大的子串放入堆中。获取堆顶元素后，删除这个元素，然后插入以 $i$ 作为起点的第 $2$ 小的子串。如果下次再次取出了这个元素，那么删除后插入以 $i$ 作为起点的第 $3$ 小的子串，以此类推。

由于起点固定为 $i$，设 $s_i$ 表示序列 $a$ 的前缀和，即要求找出 $[i+L-1,min(n,i+R-1)]$ 区间中第 $k$ 小的前缀和。主席树即可。

好像很多神仙用的是其它常数远小于主席树的RMQ之类的玩意儿，反正我只知道时间复杂度 $O(nlogn)$ 的做法中主席树最无脑最好想

$\texttt{Code}$

#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
#define GetL(p) (ls[p] ? ls[p] : ls[p] = ++ nodetot)
#define GetR(p) (rs[p] ? rs[p] : rs[p] = ++ nodetot)

typedef std::pair<int, int> PII;
inline int min(const int x, const int y) {return x < y ? x : y;}
const int N = 500005;
int a[N], b[N], kth[N], nodetot, n;
std::priority_queue<PII> q;

struct Chairman_tree {
	int sum[N << 5], root[N], ls[N << 5], rs[N << 5], nodetot, x;
	
	inline void Update(int k, int p) {
		x = p, update(root[k] = ++ nodetot, 1, n, root[k - 1]);
	}
	inline int Query(int l, int r, int k) {
		return query(root[r], root[l - 1], 1, n, k);
	}
	void make_tree(int p, int x, int y) {
		if (x == y) return;
		make_tree(ls[p] = GetL(p), x, x + y >> 1),
		make_tree(rs[p] = GetR(p), (x + y >> 1) + 1, y);
	}
	void update(int p, int l, int r, int root) {
		if (l == r) {sum[p] = sum[root] + 1; return;}
		int mid(l + r >> 1);
		if (mid >= x) update(ls[p] = GetL(p), l, mid, ls[root]), rs[p] = rs[root];
		else update(rs[p] = GetR(p), mid + 1, r, rs[root]), ls[p] = ls[root];
		sum[p] = sum[ls[p]] + sum[rs[p]];
	}
	int query(int u, int v, int l, int r, int d) {
		if (l == r) return l;
		int mid(l + r >> 1), x(sum[ls[u]] - sum[ls[v]]);
		if (d <= x) return query(ls[u], ls[v], l, mid, d);
		else return query(rs[u], rs[v], mid + 1, r, d - x);
	}
} Tree;

signed main() {
	int k, L, R;
	long long ans(0LL);
	scanf("%lld%lld%lld%lld", &n, &k, &L, &R);
	Tree.make_tree(Tree.root[0] = Tree.nodetot = 1, 1, n);
	for (int i(1); i <= n; ++ i) {
		int x;
		scanf("%lld", &x);
		b[i] = a[i] = a[i - 1] + x;
	}
	std::sort(b + 1, b + n + 1);
	for (int i(1); i <= n; ++ i)
		Tree.Update(i, std::lower_bound(b + 1, b + n + 1, a[i]) - b);
	for (int i(1); i + L - 1 <= n; ++ i) {
		const int st(i + L - 1), ed(min(i + R - 1, n));
		q.push(std::make_pair(b[Tree.Query(st, ed, ed - st + 1)] - a[i - 1], i));
		kth[i] = ed - st + 1;
	}
	while (k --) {
		PII t(q.top());
		q.pop();
		ans += t.first;
		const int i(t.second);
		const int st(i + L - 1), ed(min(i + R - 1, n));
		if (-- kth[i]) q.push(std::make_pair(b[Tree.Query(st, ed, kth[i])] - a[i - 1], i));
	}
	printf("%lld", ans);
	return 0;
}