526互联

Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round) E. Monsters (hard version) 线段树二分

发布时间 2023-04-19 20:32:00作者: qdhys

传送门
详细题解传送门

  抄的ygg代码，向在这里说一下刚开始没看懂的部分。

  求答案的时候是把所有的当前为止的所有数值加起来减去一个从1开始并且公差为1的等差数列的前size项和。其中size是当前最多能用到哪个位置，满足前size项能构成1,2,3，....,sz这样的形式。

  假设我们的a[] = {1, 4, 4, 4, 3}，在i等于4的时候答案是3，在i等于5的时候答案是2，由于我们给线段树上每个为i的位置插入了-i，当i = 4的时候线段树叶子结点[0, -1, -2, 0, -1]，当i == 5时候线段树的叶子结点为[0, -1, -1, 1, 0]。这个时候我们就可以找出到i为止多余的数字，并且减去他所造成的影响。

#include <bits/stdc++.h>

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define ls u << 1
#define rs u << 1 | 1

int n, m;

int a[N];

struct node {
	int lazy;
	int v;
}tr[N << 2];

inline void pushup(int u) {
	tr[u].v = std::max(tr[ls].v, tr[rs].v);
}

inline void pushdown(int u) {
	if (tr[u].lazy) {
		int &v = tr[u].lazy;
		tr[ls].lazy += v;
		tr[ls].v += v;
		tr[rs].lazy += v;
		tr[rs].v += v;
		v = 0;
	} 
}

inline void build(int u, int L, int R) {
	tr[u].lazy = tr[u].v = 0;
	if (L == R) return ;
	
	
	int mid = L + R >> 1;
	build(ls, L, mid);
	build(rs, mid + 1, R);
	
	pushup(u);
}

inline void modify(int u, int L, int R, int l, int r, int v) {
	if (L >= l && R <= r) {
		tr[u].lazy += v;
		tr[u].v += v;
		return ;
	}
	
	pushdown(u);
	
	int mid = L + R >> 1;
	if (l <= mid)	modify(ls, L, mid, l, r, v);
	if (r > mid)	modify(rs, mid + 1, R, l, r, v);
	
	pushup(u);
}

inline int query(int u, int L, int R) {
	if (L == R)	return L;
	
	pushdown(u);
	
	int mid = L + R >> 1;
	
	if (tr[ls].v > 0)	return query(ls, L, mid);
	return query(rs, mid + 1, R);
}

inline void solve() {
	std::cin >> n;
	
	for (int i = 1; i <= n; i ++) std::cin >> a[i];
	
	build(1, 1, n);
	for (int i = 1; i <= n; i ++) {
		modify(1, 1, n, i, i, -i);
	}
	ll sum = 0, sz = 0;
	for (int i = 1; i <= n; i ++) {
		sum += a[i], sz ++;
		
		modify(1, 1, n, a[i], n, 1);
		if (tr[1].v > 0) {
			int now = query(1, 1, n);
			sz --, sum -= now;
			modify(1, 1, n, now, n, -1);
		}
		
		std::cout << sum - sz * (sz + 1) / 2 << ' ';
	}
	std::cout << '\n';
}

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int _;
	_ = 1;
	std::cin >> _;
	
	while (_ --) solve();
	
	return 0;
}