Codeforces 992 E. Nastya and King-Shamans

$>Codeforces\space992 E. Nastya and King-Shamans<$

题目大意 : 给你一个长度为 $n$ 的序列，有 $q$ 次操作，每一次操作将一个数 $A_i$ 改为另外一个数。每一次操作结束时，你需要找出一个位置 $x$ 满足 $A_x = sum_{x-1}$ 其中 $sum$ 表示前缀和

$n , q \leq 2 \times 10^5 \ 0 \leq A_i \leq 10^9 $

解题思路 :

博主亲测分块加均摊分析的做法会因为常数太大 $TLE$ 掉，在此就不多讨论了

问题要求出满足 $A_x = sum_{x-1}$ 的位置，这个可以转化为 $sum_x = 2 \times sum_{x-1}$

我们考虑从 $A_{p=1}$ 开始跳，每一次跳到其后面一个最小的 $k - 1$ ，满足$sum_k \geq 2 \times sum_p$

可以证明如果有答案且 $sum_{ans} > 0$，那么答案一定在所有的 $k$ 之中产生

不妨用反证法来证明，假设当且跳到点 $k$ ，接下来选取的点是 $k' \ (k < k')$ ，对于 $k < i < k' - 1$

如果说 $i$ 是答案的话，设 $y$ 为第一个满足 $ sum_y \geq 2 \times sum_i$ 的点。

因为$sum_y \geq sumk$ 所以必然有 $ y \geq k' $ ，如果 $i < k' - 1$ 那么 $ y - i > 1$ , $i$ 不是答案

所以证明了这样跳，如果有答案的话答案必然在跳到的点上

所以可以用树状数组维护前缀和，每一次暴力二分跳，跳 $log$ 次就能跳完，总复杂度是$O(nlog^3n)$

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

    int f = 0, ch = 0; x = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

    if(f) x = -x;

}

#define N (300005)

#define int ll

ll c[N], a[N], n, q;

inline void add(int x, ll y){ for(int i = x; i <= n; i += i & -i) c[i] += y; }

inline ll sum(int x){ ll ans = 0; for(int i = x; i; i -= i & -i) ans += c[i]; return ans; }

inline void solve(){

	int x = 1;

	if(sum(1) == 0) return (void)( puts("1") );

	while(x < n){

		int l = x + 1, r = n, k = x, now = 2 * sum(x);

		if(sum(x + 1) == now) return (void) (printf("%d\n", x + 1));

		while(l <= r){

			int mid = l + r >> 1;

			if(sum(mid) < now) k = mid, l = mid + 1; else r = mid - 1;

		}

		if(k + 1 > n) break;

		x = (k == x) ? k + 1 : k;

	}

	puts("-1");

}

main(){

	read(n), read(q);

	for(int i = 1; i <= n; i++) read(a[i]), add(i, a[i]);

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

		int x, y; read(x), read(y);

		add(x, y - a[x]), a[x] = y, solve();

	}

	return 0;

}

巴特西

Codeforces 992 E. Nastya and King-Shamans

解题思路 :

最新文章

热门文章