\(\text{Problem}\)

动态区间第 \(k\) 小

Dynamic Rankings

\(\text{Analysis}\)

整体二分

原本一个询问可二分，但多个询问效率太低

考虑离线，把修改和询问扔到一起

二分答案，运用树状数组之类的东西处理完修改操作

依次检查询问，划分左右，初步确定每个询问的答案值域，修改操作相应地划分到有必要的一边（左右）

\(\text{Code}\)

#include<cstdio>

using namespace std;

const int N = 1e5 + 5;

int n, m, cnt, a[N], ans[N], T[N];

struct node{

	int ty, l, r, k, id;

}q[N * 3], q1[N * 3], q2[N * 3];

inline void read(int &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();

}

inline int lowbit(int x){return x & (-x);}

inline void add(int x, int v){for(; x <= n; x += lowbit(x)) T[x] += v;}

inline int query(int x)

{

	int ret = 0;

	for(; x; x -= lowbit(x)) ret += T[x];

	return ret;

}

void solve(int l, int r, int ql, int qr)

{

	if (ql > qr) return;

	if (l == r)

	{

		for(int i = ql; i <= qr; i++) ans[q[i].id] = l;

		return;

	}

	int ct1 = 0, ct2 = 0, mid = (l + r) >> 1;

	for(int i = ql; i <= qr; i++)

	{

		if (q[i].ty == 1)

		{

			if (q[i].l <= mid) add(q[i].r, q[i].k), q1[++ct1] = q[i];

			else q2[++ct2] = q[i];

		}

		else{

			int sum = query(q[i].r) - query(q[i].l - 1);

			if (sum >= q[i].k) q1[++ct1] = q[i];

			else q[i].k -= sum, q2[++ct2] = q[i];

		}

	}

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

	if (q1[i].ty == 1) add(q1[i].r, -q1[i].k);

	for(int i = 1; i <= ct1; i++) q[ql + i - 1] = q1[i];

	for(int i = 1; i <= ct2; i++) q[ql + ct1 + i - 1] = q2[i];

	solve(l, mid, ql, ql + ct1 - 1);

	solve(mid + 1, r, ql + ct1, qr);

}

int main()

{

	read(n), read(m);

	for(int i = 1; i <= n; i++) read(a[i]), q[++cnt] = node{1, a[i], i, 1};

	char op[3];

	for(int i = 1, l, r, k; i <= m; i++)

	{

		scanf("%s", op), read(l), read(r);

		if (op[0] == 'C') q[++cnt] = node{1, a[l], l, -1}, q[++cnt] = node{1, a[l] = r, l, 1};

		else read(k), q[++cnt] = node{2, l, r, k, i};

	}

	solve(0, 1e9, 1, cnt);

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

	if (ans[i]) printf("%d\n", ans[i]);

}

当然可以树状数组套权值线段树

\(\text{Code}\)

#include <cstdio>

#include <algorithm>

#include <iostream>

#define re register

using namespace std;

const int N = 1e5 + 5;

int n, m, len, a[N], b[N * 2], ct1, ct2, tmp1[50], tmp2[50];

struct que{int o, l, r, k;}q[N];

inline void read(int &x)

{

	x = 0; char ch = getchar();

	while (!isdigit(ch)) ch = getchar();

	while (isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();

}

int size, rt[N], sum[N * 400], ls[N * 400], rs[N * 400];

void modify(int &p, int l, int r, int x, int v)

{

	if (!p) p = ++size;

	sum[p] += v;

	if (l == r) return;

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

	if (x <= mid) modify(ls[p], l, mid, x, v);

	else modify(rs[p], mid + 1, r, x, v);

}

int query(int l, int r, int k)

{

	if (l == r) return l;

	int s = 0, mid = (l + r) >> 1;

	for(re int i = 1; i <= ct1; i++) s += sum[ls[tmp1[i]]];

	for(re int i = 1; i <= ct2; i++) s -= sum[ls[tmp2[i]]];

	if (k <= s)

	{

		for(re int i = 1; i <= ct1; i++) tmp1[i] = ls[tmp1[i]];

		for(re int i = 1; i <= ct2; i++) tmp2[i] = ls[tmp2[i]];

		return query(l, mid, k);

	}

	else{

		for(re int i = 1; i <= ct1; i++) tmp1[i] = rs[tmp1[i]];

		for(re int i = 1; i <= ct2; i++) tmp2[i] = rs[tmp2[i]];

		return query(mid + 1, r, k - s);

	}

}

inline int lowbit(int x){return x & (-x);}

inline void Modify(int x, int val, int v)

{

	val = lower_bound(b + 1, b + len + 1, val) - b;

	for(; x <= n; x += lowbit(x)) modify(rt[x], 1, len, val, v);

}

inline int Query(int l, int r, int k)

{

	ct1 = ct2 = 0;

	for(; r; r -= lowbit(r)) tmp1[++ct1] = rt[r];

	for(l = l - 1; l; l -= lowbit(l)) tmp2[++ct2] = rt[l];

	return b[query(1, len, k)];

}

int main()

{

	read(n), read(m);

	for(re int i = 1; i <= n; i++) read(a[i]), b[++len] = a[i];

	int l, r, k; char op[3];

	for(re int i = 1; i <= m; i++)

	{

		scanf("%s", op), read(l), read(r);

		if (op[0] == 'Q') read(k), q[i] = que{1, l, r, k};

		else q[i] = que{0, l, r}, b[++len] = r;

	}

	sort(b + 1, b + len + 1);

	len = unique(b + 1, b + len + 1) - b - 1;

	for(re int i = 1; i <= n; i++) Modify(i, a[i], 1);

	for(re int i = 1; i <= m; i++)

		if (q[i].o == 1) printf("%d\n", Query(q[i].l, q[i].r, q[i].k));

		else Modify(q[i].l, a[q[i].l], -1), Modify(q[i].l, a[q[i].l] = q[i].r, 1);

}

巴特西

LG P2617 Dynamic Rankings

\(\text{Problem}\)

\(\text{Analysis}\)

\(\text{Code}\)

\(\text{Code}\)

最新文章

热门文章