洛谷 P3380 【模板】二逼平衡树（树套树）

题面

题解

2019年AC的第一道题~~

函数名命名为rank竟然会ce

我写的是树状数组套值域线段树(动态开点)

操作1:询问\(k\)在\([l-r]\)这段区间有多少数比它小,再加\(1\)

操作2:前缀和思想得到\([l-r]\)区间的线段树,然后类似平衡树找第\(k\)大

操作3:直接修改

操作4/5:操作1+操作2

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

const int N = 50010;

using namespace std;

inline int gi() {

	RG int x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar();

	if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();

	return f ? -x : x;

}

int tot, A[N<<1], a[N], cnt, n;

int t1, t2, tmp1[N], tmp2[N];

struct question {

	int op, l, r, k;

}q[N];

struct node {

	int ls, rs, v;

}t[N<<7];

int rt[N];

#define lowbit(x) (x&(-x))

void Update(int &now, int l, int r, int pos, int k) {

	if (!now) now = ++cnt;

	t[now].v += k;

	if (l == r) return ;

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

	if (pos <= mid) Update(t[now].ls, l, mid, pos, k);

	else Update(t[now].rs, mid+1, r, pos, k);

}

void update(int x, int k) {

	for (int i = x; i <= n; i += lowbit(i)) Update(rt[i], 1, tot, a[x], k);

}

int query(int now, int l, int r, int pos) {

	if (l == r) return t[now].v;

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

	if (pos <= mid) return query(t[now].ls, l, mid, pos);

	return t[t[now].ls].v+query(t[now].rs, mid+1, r, pos);

}

int Rank(int l, int r, int k) {

	if (l > r) return 0;

	l--;

	int s = 0;

	for (int i = r; i; i -= lowbit(i)) s += query(rt[i], 1, tot, k);

	for (int i = l; i; i -= lowbit(i)) s -= query(rt[i], 1, tot, k);

	return s;

}

int Kth(int l, int r, int k) {

	if (l == r) return l;

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

	for (int i = 1; i <= t1; i++) s += t[t[tmp1[i]].ls].v;

	for (int i = 1; i <= t2; i++) s -= t[t[tmp2[i]].ls].v;

	if (s >= k) {

		for (int i = 1; i <= t1; i++) tmp1[i] = t[tmp1[i]].ls;

		for (int i = 1; i <= t2; i++) tmp2[i] = t[tmp2[i]].ls;

		return Kth(l, mid, k);

	}

	else {

		for (int i = 1; i <= t1; i++) tmp1[i] = t[tmp1[i]].rs;

		for (int i = 1; i <= t2; i++) tmp2[i] = t[tmp2[i]].rs;

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

	}

}

int kth(int l, int r, int k) {

	l--; t1 = t2 = 0;

	for (int i = r; i; i -= lowbit(i)) tmp1[++t1] = rt[i];

	for (int i = l; i; i -= lowbit(i)) tmp2[++t2] = rt[i];

	return A[Kth(1, tot, k)];

}

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi();

	int m = gi();

	for (int i = 1; i <= n; i++) A[++tot] = a[i] = gi();

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

		q[i].op = gi();

		if (q[i].op != 3) {

			q[i].l = gi(); q[i].r = gi(); q[i].k = gi();

			if (q[i].op != 2) A[++tot] = q[i].k;

		}

		else {

			q[i].l = q[i].r = gi();

			A[++tot] = q[i].k = gi();

		}

	}

	sort(A+1, A+1+tot);

	tot = unique(A+1, A+1+tot) - A - 1;

	for (int i = 1; i <= n; i++) a[i] = lower_bound(A+1, A+1+tot, a[i])-A;

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

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

		if (q[i].op != 2)

			q[i].k = lower_bound(A+1, A+1+tot, q[i].k)-A;

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

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

			printf("%d\n", Rank(q[i].l, q[i].r, q[i].k-1)+1);

		else if (q[i].op == 2) printf("%d\n", kth(q[i].l, q[i].r, q[i].k));

		else if (q[i].op == 3) {

			update(q[i].l, -1);

			a[q[i].l] = q[i].k;

			update(q[i].l, 1);

		}

		else if (q[i].op == 4) {

			int g = Rank(q[i].l, q[i].r, q[i].k-1);

			if (!g) puts("-2147483647");

			else printf("%d\n", kth(q[i].l, q[i].r, g));

		}

		else {

			int g = Rank(q[i].l, q[i].r, q[i].k);

			if (g == q[i].r-q[i].l+1) puts("2147483647");

			else printf("%d\n", kth(q[i].l, q[i].r, g+1));

		}

	}

	return 0;

}

巴特西

洛谷 P3380 【模板】二逼平衡树（树套树）

题面

题解

Code

最新文章

热门文章