CF 807 E. mark and Professor Koro (weight segment tree)

Problem - E - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1705/problem/E Here you are. n Sequence of Numbers , Here you are m Operations , Each operation gives you two numbers k,x

Will be the first k The number is changed to x, And ask you to choose to appear after you change 2 The number of times is merged into this number +1 Number of numbers , Find the maximum value of the sequence after these operations .

Suppose a number is x, If it occurs more than twice x, Then we can merge into x+1, You can think of binary addition , When a binary number is 00011, If first +1, Then the number becomes 00100, Just like the situation above , So we can convert it into binary addition , And then maintain it with a line tree .

const int N = 2e5 + 106;
struct node {
	int l, r;
	int add;
	int sum;
} tr[MAXN * 3];
int cnt[MAXN], a[MAXN];

void push_up(int q) {
	tr[q].sum = tr[q << 1].sum + tr[q << 1 | 1].sum;
}

void update(int q, int add) {
	tr[q].sum += (tr[q].r - tr[q].l + 1) * add;
	tr[q].add += add;
}

void push_down(int q) {
	if (tr[q].add) {
		update(q << 1, tr[q].add), update(q << 1 | 1, tr[q].add);
		tr[q].add = 0;
	}
}

void build(int q, int l, int r) {
	tr[q].l = l, tr[q].r = r;
	if (l == r)
		return void(tr[q].sum = cnt[r]);
	int mid = l + r >> 1;
	build(q << 1, l, mid);
	build(q << 1 | 1, mid + 1, r);
	push_up(q);
}

void modify(int q, int l, int r, int add) {
//	printf("2\n");
	if (tr[q].l >= l && tr[q].r <= r) {
		update(q, add);
		return;
	}
	push_down(q);
	int mid = tr[q].l + tr[q].r >> 1;
	if (l <= mid)
		modify(q << 1, l, r, add);
	if (r > mid)
		modify(q << 1 | 1, l, r, add);
	push_up(q);
}

int query0(int q, int l) {
//	printf("3\n");
	if (tr[q].r < l || tr[q].sum == tr[q].r - tr[q].l + 1)
		return -1;
	if (tr[q].l == tr[q].r)
		return tr[q].r;
	push_down(q);
	int t = query0(q << 1, l);
	if (~t)
		return t;
	return query0(q << 1 | 1, l);
}

int query1(int q, int l) {
//	printf("4\n");
	if (tr[q].r < l || !tr[q].sum)
		return -1;
	if (tr[q].l == tr[q].r)
		return tr[q].r;
	push_down(q);
	int t = query1(q << 1, l);
	if (~t)
		return t;
	return query1(q << 1 | 1, l);
}

int querymax(int q) {
//	printf("5\n");
	if (tr[q].l == tr[q].r)
		return tr[q].r;
	push_down(q);
	if (tr[q << 1 | 1].sum)
		return querymax(q << 1 | 1);
	return querymax(q << 1);
}

int query(int q, int x) {
	if (tr[q].l == tr[q].r)
		return tr[q].r;
	push_down(q);
	int mid = tr[q].l + tr[q].r >> 1;
	if (x <= mid)
		return query(q << 1, x);
	return query(q << 1 | 1, x);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for (int i = 1; i <= N; i++) {
		cnt[i + 1] += cnt[i] / 2;
		cnt[i] %= 2;
	}
	build(1, 1, N);
	while (m--) {
		int k, x;
		cin >> k >> x;
		int pos = query1(1, a[k]);
		modify(1, pos, pos, -1);
		if (pos != a[k])
			modify(1, a[k], pos - 1, 1);
		a[k] = x;
//		printf("===\n");
		pos = query0(1, a[k]);
		modify(1, pos, pos, 1);
		if (pos != a[k])
			modify(1, a[k], pos - 1, -1);
		cout << querymax(1) << '\n';
	}
	return 0;
}