K个串

题目链接

题解

看完题目后可以立刻想到：先算出最大值，然后把最大值剔除掉，再找此时的最大值也就是次大值。这样重复\(k\)边即可找到第\(k\)大值。

于是我们只需要考虑找最大值了

我们可以维护后缀和中的最大值（这里的和是指题目中的不统计重复数字的求和）

具体来说，我们可以建\(n\)课线段树，第\(i\)颗存的是以\(i\)为结尾的所有后缀和，那么，我们可以把每颗线段树的最大值全部扔进一个大根堆，这样我们就能每次得到当前的最大值。

接着，我们从堆中取出当前最大值，设这个最大值是在第\(i\)棵树的\([l, r]\)区间内取得的，位置为\(p\)，那么我们分别在第\(i\)棵树的\([l, p)\)和\((p, r]\)两区间内找最大值，然后把它们放入堆中。

显然，我们可以用主席树优化空间\((\)pushdown一定要记得复制节点！！！！！\()\)

注意：由于不统计重复数字，那么在建主席树时，设当前数字\(a_i\)上次出现位置为\(l\)，那么它的贡献区间为\((p, i)\)

代码

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

using namespace std;

typedef long long LL;

#define fi first

#define se second

typedef pair <LL, int> pr;

const LL INF = 1e14;

const int N = 100010;

int root[N];

struct SegmentTree

{

	int ls[N * 400], rs[N * 400], sz;

	LL addv[N * 400];

	pr maxv[N * 400];

	int cpyNode(int x)

	{

		int cur = ++sz;

		ls[cur] = ls[x];

		rs[cur] = rs[x];

		maxv[cur] = maxv[x];

		addv[cur] = addv[x];

		return cur;

	}

	inline int downtag(int x, LL v)

	{

		int cur = cpyNode(x);

		addv[cur] += v;

		maxv[cur].fi += v;

		return cur;

	}

	inline void pushdown(int cur)

	{

		if (addv[cur])

		{

			if (ls[cur]) ls[cur] = downtag(ls[cur], addv[cur]);

			if (rs[cur]) rs[cur] = downtag(rs[cur], addv[cur]);

			addv[cur] = 0;

		}

	}

	void build(int & cur, int l, int r)

	{

		cur = ++sz;

		addv[cur] = 0;

		if (l == r) { maxv[cur] = make_pair(0, -l); return; }

		int mid = (l + r) >> 1;

		build(ls[cur], l, mid);

		build(rs[cur], mid+1, r);

		maxv[cur] = max(maxv[ls[cur]], maxv[rs[cur]]);

	}

	void update(int & cur, int pre, int l, int r, int ql, int qr, LL v)

	{

		if (ql == l && qr == r)

			cur = downtag(pre, v);

		else

		{

			pushdown(pre);

			cur = cpyNode(pre);

			int mid = (l + r) >> 1;

			if (qr <= mid)

				update(ls[cur], ls[pre], l, mid, ql, qr, v);

			else if (ql > mid)

				update(rs[cur], rs[pre], mid+1, r, ql, qr, v);

			else

				update(ls[cur], ls[pre], l, mid, ql, mid, v),

				update(rs[cur], rs[pre], mid+1, r, mid+1, qr, v);

			maxv[cur] = max(maxv[ls[cur]], maxv[rs[cur]]);

		}

	}

	pr query(int cur, int l, int r, int ql, int qr)

	{

		if (ql == l && qr == r)

			return maxv[cur];

		pushdown(cur);

		int mid = (l + r) >> 1;

		if (qr <= mid)

			return query(ls[cur], l, mid, ql, qr);

		else if (ql > mid)

			return query(rs[cur], mid+1, r, ql, qr);

		else

			return max(query(ls[cur], l, mid, ql, mid),

					   query(rs[cur], mid+1, r, mid+1, qr));

	}

} seg;

int n, k;

LL a[N]; int last[N];

map <LL, int> pos;

struct Data

{

	int id, pl, pr, pos; LL val;

	Data() { }

	Data(int _1, int _2, int _3, int _4, LL _5) : id(_1), pl(_2), pr(_3), pos(_4), val(_5) { }

	bool operator < (const Data & rhs) const { return val < rhs.val; }

};

priority_queue <Data> q;

int main()

{

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++)

	{

		scanf("%lld", &a[i]);

		last[i] = pos[a[i]];

		pos[a[i]] = i;

	}

	seg.build(root[0], 1, n);

	for (int i = 1; i <= n; i++)

		seg.update(root[i], root[i-1], 1, n, last[i]+1, i, a[i]);

	for (int i = 1; i <= n; i++)

	{

		pr res = seg.query(root[i], 1, n, 1, i);

		q.push(Data(i, 1, i, -res.se, res.fi));

	}

	Data res;

	for (int i = 1; i <= k; i++)

	{

		res = q.top(); q.pop();

		if (res.pl < res.pos)

		{

			pr now = seg.query(root[res.id], 1, n, res.pl, res.pos-1);

			q.push(Data(res.id, res.pl, res.pos-1, -now.se, now.fi));

		}

		if (res.pr > res.pos)

		{

			pr now = seg.query(root[res.id], 1, n, res.pos+1, res.pr);

			q.push(Data(res.id, res.pos+1, res.pr, -now.se, now.fi));

		}

	}

	printf("%lld\n", res.val);

	return 0;

}

巴特西

K个串

题目链接

题解

代码

最新文章

热门文章