Maximum Rating

#数据结构 #线段树 #块状链表 #贪心

题目描述

A rating system, usually used in sports, games, and competitive programming platforms, is a method to rank the skill level of their players or users in relatively impartial ways. The rating of an individual is the numerical evaluation of competitive performance, which is directly comparable even at different times.

Sulfox is an ICPC contestant who has participated in $n$ AtForces rounds, where the rating change for the $i$-th round is $a_i$. The initial rating and maximum rating are both $0$. After each round, the rating is increased by the rating change for that round. If the rating at that point is strictly greater than the current maximum rating, the maximum rating will be updated to the current rating.

Now Sulfox has hacked into AtForces’ back-end database, which enables him to arrange these $n$ rounds in any order. He wonders how many values of $k$ exist satisfying that there is at least an arrangement of the $n$ rounds that updates the maximum rating exactly $k$ times. Additionally, he wants to know the result each time after some updates that modify the rating change for one of the $n$ rounds.

输入格式

The first line contains two integers $n$ and $q$ ($1\le n,q\le 2\times 10^5$), denoting the number of AtForces rounds and the number of updates respectively.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9$), denoting the rating changes for each round.

Then $q$ lines follow, each containing two integers $x$ ($1\le x\le n$) and $v$ ($-10^9\le v\le 10^9$), denoting an update that modifies the rating change for the $x$-th round to $v$.

输出格式

After each update, output a line containing an integer, representing the number of $k$ satisfying that there exists at least an arrangement of the $n$ rounds where the maximum rating is updated exactly $k$ times.

样例 #1

样例输入 #1

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

样例输出 #1

1
2
2
2
3

解法

解题思路

首先这题的思路很简单，我们把正数和负数分开，例如$[1,2,4,5,-1,-5]$这个数列，能更新多少次最大得分呢？

我们贪心的考虑，让负数都集中在一起，正数从大到小放：
$(1)$ $[5,4,2,1,-6]$ 更新四次最大成绩
$(2)$ $[5,4,2,-6,1]$ 更新三次最大成绩
$(3)[5,4,-6,2,1]$ 更新两次最大成绩

可以发现，有三种不同的次数，并且这样是最优的。

答案就是正数从小到大的前缀和大于等于负数绝对值之和的第一个位置（设为$pos$），那么答案就是$pos-1$，例如在$[1,2,4,5]$中，$1+2+4+5>8$，因此答案为$4-1=3$。

因此我们需要维护一个数据结构，能够快速求出前缀和小于某个数的具体个数，并且支持单点修改。

由于值域很大，容易想到使用动态开点的值域线段树，在线段树上二分即可找到第一个位置，时间复杂度在$qlo{g}_2(1e18)$。

当然，由于这题$n\le 1e5$，也可以使用块状链表来维护，时间复杂度在$q\sqrt{n}lo{g}_2(\sqrt{n})$

代码（动态开点线段树二分）

namespace SegmentTree {
	int tot = 0;
 
	struct node {
		int l, r, cnt, sum;
	} tree[N * 32];
 
 
	void update(int& u, int l, int r, int pos, int val) {
		if (!u) u = ++tot;
		tree[u].cnt += val; tree[u].sum += val * pos;
 
		if (l == r) return;
 
		int mid = l + r >> 1;
 
		if (pos <= mid) update(tree[u].l, l, mid, pos, val);
 
		else {
			update(tree[u].r, mid + 1, r, pos, val);
		}
	}
 
	int query(int u, int l, int r, int sum) {
 
		if (l == r) return (sum <= 0 ? 0 : (sum + l - 1) / l);
 
		int mid = l + r >> 1;
 
		if (tree[tree[u].l].sum >= sum) return query(tree[u].l, l, mid, sum);
 
		else {
			return query(tree[u].r, mid + 1, r, sum - tree[tree[u].l].sum) + tree[tree[u].l].cnt;
		}
	}
};
int a[N];
void solve() {
	
	int n, q, rt = 0;
	int sum = 0;
 
	std::cin >> n >> q;
	for (int i = 1; i <= n; ++i){
		std::cin >> a[i];
		if (a[i] > 0) SegmentTree:: update(rt, 1, inf, a[i], 1);
		if (a[i] <= 0) sum += a[i];
	}
 
	while (q--){
		int x, v;
		std::cin >> x >> v;
 
		if (a[x] > 0) SegmentTree::update(rt, 1, inf, a[x], -1);
		if (v > 0) SegmentTree::update(rt, 1, inf, v, 1);
 
		if (a[x] <= 0) sum -= a[x];
		if (v <= 0) sum += v;
		a[x] = v;
	
		std::cout << SegmentTree::query(1, 1, inf, -sum + 1) << "\n";
	}
}
 
signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
 
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
};

代码（块状链表）

const int N = 2e5 + 10;
 
int len, n, q;
namespace block_list {
	struct node {
		vector<int> data;
		int sum = 0;
	};
 
	list<node>List;
	list<node>::iterator find(int x) {
		for (auto it = List.begin(); it != List.end(); ++it) {
			if (it->data.back() >= x) { //找到块尾大于x的数
				return it;
			}
		}
	}
 
	void insert(int x) { // 插入一个数
		auto it = find(x);
		it->data.emplace(lower_bound(it->data.begin(), it->data.end(), x), x);
		it->sum += x;
 
 
		if (it->data.size() > len) {
			vector<int> tmp(it->data.begin() + len / 2, it->data.end());
 
			// 计算新节点的 sum
			int s = std::accumulate(tmp.begin(), tmp.end(), 0LL);
 
			// 插入新节点
			List.insert(next(it), { tmp, s });
 
			// 更新当前节点的数据
			it->data.erase(it->data.begin() + len / 2, it->data.end());
 
			// 重新计算当前节点的 sum
			it->sum = std::accumulate(it->data.begin(), it->data.end(), 0LL);
		}
	}
	void erase(int x) { //删除一个数
		auto it = find(x);
		it->data.erase(lower_bound(it->data.begin(), it->data.end(), x));
		it->sum -= x;
		if (it->data.empty()) {
			List.erase(it);
		}
	}
	int query(int s) {
		int res = 1, S = 0;
		for (auto& it : List) {
			if (S + it.sum <= s) {
				S += it.sum;;
				res += it.data.size();
			}
			else {
				for (auto& x : it.data) {
					if (S + x > s) return res;
					res++;
					S += x;
				}
			}
		}
		return -1;
	}
};
 
int a[N];
void solve() {
	cin >> n >> q;
	len = 350;
	vector<int>tmp;
	tmp.emplace_back(inf); //哨兵，保证什么时候都有最大值，可以插入
	block_list::List.emplace_back(tmp,inf);
 
	int s = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (a[i] > 0) block_list::insert(a[i]);
		else s += -a[i];
	}
 
	while (q--) {
		int idx, val;
		cin >> idx >> val;
 
		if (a[idx] > 0) {
			block_list::erase(a[idx]);
			a[idx] = val;
			if (val > 0) block_list::insert(val);
			else  s += -val;
		}
		else {
			s -= -a[idx];
			a[idx] = val;
 
			if (val > 0) block_list::insert(val);
			else  s += -val;
		}
 
		int res = block_list::query(s);
 
		std::cout << res << "\n";
	}
}
 
signed main() {
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
};