Codeforces Round 966 (Div. 3) H(SimpleSegmentTree)

佚名 / 2024-09-18 / 原文

题目链接

题意

$T(1 \le T \le 10^4)$ 组数据，每组数据给定一个由 $n$ 个不同正整数 $a_1、a_2、a_3 \cdot\cdot\cdot、a_n$ 组成的集合。

题解

线段树。

点击查看代码

#include <bits/stdc++.h>

using i64 = long long;

const int N = 4E6 + 10;

struct Node {
	int L, R, max, len;
	Node(int L_ = 0, int R_ = 0, int max_ = 0, int len_ = 0) {
		L = L_; R = R_; max = max_; len = len_;
	}
};

Node SGT[N * 4 + 1];

Node operator + (const Node lson, const Node rson) {
	int L = lson.L + (lson.L == lson.len ? rson.L : 0);
	int R = rson.R + (rson.R == rson.len ? lson.R : 0);
	int max = std::max({lson.max, rson.max, lson.R + rson.L});
	int len = lson.len + rson.len;
	return Node(L, R, max, len);
}

void build(int p, int l, int r) {
	if (l == r) {
		SGT[p] = Node(1, 1, 1, 1);
		return ;
	}
	
	int mid = (l + r) / 2;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	SGT[p] = SGT[p << 1] + SGT[p << 1 | 1];
}

void update(int p, int l, int r, int x, int v) {
	if (l == r) {
		SGT[p].L = SGT[p].R = SGT[p].max = v;
		return ;
	}
	
	int mid = l + r >> 1;
	if (x <= mid) {
		update(p << 1, l, mid, x, v);
	} else {
		update(p << 1 | 1, mid + 1, r, x, v);
	}
	SGT[p] = SGT[p << 1] + SGT[p << 1 | 1];
}

int query(int p, int l, int r, int k) {
	if (l == r) {
		return l;	
	}
	
	int mid = l + r >> 1;
	if (SGT[p << 1].max >= k) {
		return query(p << 1, l, mid, k);
	} else if (SGT[p << 1].R + SGT[p << 1 | 1].L >= k) {
		return mid - SGT[p << 1].R + 1;
	} else {
		return query(p << 1 | 1, mid + 1, r, k);
	}
}

void solve() {
	int n;
	std::cin >> n;
	
	std::vector<int> a(n + 1);
	std::set<int> set;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		set.insert(a[i]);
		update(1, 1, N, a[i], 0);
	}
	
	int m;
	std::cin >> m;
	
	while (m--) {
		char c;
		std::cin >> c;
		
		if (c == '?') {
			// query
			int k;
			std::cin >> k;
			
			std::cout << query(1, 1, N, k) << " ";
		} else {
			// add or delete
			int x;
			std::cin >> x;
			
			if (c == '-') {
				set.erase(x);
				update(1, 1, N, x, 1);
			} else {
				set.insert(x);
				update(1, 1, N, x, 0);
			}
		}
	}
	
	std::cout << "\n";
	for (auto x : set) {
		update(1, 1, N, x, 1);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	build(1, 1, N);
	
	int T;
	std::cin >> T;
	
	while (T--) {
		solve();
	}
	
	return 0;
}