题目链接：传送门

Description

给你一个长度为nn的序列aia_i，有qq次操作，每次操作(x,y)(x, y)将第xx个数改为yy，求在每次操作后是否存在ii，使得ai=sumi−1a_i=sum_{i-1} 若存在则输出任意一个即可，否则输出-1

Hint

n,q≤105n,q \leq 10^5

ai≤109a_i \leq 10^9

Solution

从i=1=1开始，首先求出sumisum_{i}，然后在[i+1,n][i+1, n]中找到第一个aj≥sumia_j\ge sum_i

如果aj==sumj−1a_j==sum_{j-1}结束搜索，否则令i=ji=j，循环过程

因为每次做完一次之后sum会至少增大一倍，所以每次查询的复杂度为O(log2(max(ai)))O(log_2(max(a_i)))

然后用线段树维护区间和以及区间最大值（用来二分查找aj≥sumia_j\ge sum_i）

总时间复杂度为O(n⋅log2n⋅log2(max(ai))O(n\cdot log_2n\cdot log_2(max(a_i))

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	T fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

const int Maxn = 2e5 + 100;

int N, M, A[Maxn];

struct tree
{
	int Max, sum, val;
}Tree[Maxn << 2];

namespace SEG
{
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
	inline void push_up (int root)
	{
		Tree[root].Max = max(Tree[root << 1 | 1].Max, Tree[root << 1].Max);
		Tree[root].sum = Tree[root << 1 | 1].sum + Tree[root << 1].sum;
	}

	inline void build (int root, int l, int r)
	{
		if (l == r)
		{
			Tree[root].Max = Tree[root].sum = Tree[root].val = A[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build (lson), build (rson);
		push_up (root);
	}

	inline int query_sum (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return Tree[root].sum;
		int mid = (l + r) >> 1, ans = 0;
		if (x <= mid) ans += query_sum (lson, x, y);
		if (y > mid) ans += query_sum (rson, x, y);
		return ans;
	}

	inline int query_max (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return Tree[root].sum;
		int mid = (l + r) >> 1, ans = 0;
		if (x <= mid) Chkmax(ans, query_sum (lson, x, y));
		if (y > mid) Chkmax(ans, query_sum (rson, x, y));
		return ans;
	}

	inline void update (int root, int l, int r, int x, int v)
	{
		if (l == r)
		{
			Tree[root].sum = Tree[root].val = Tree[root].Max = v;
			return ;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) update (lson, x, v);
		else update (rson, x, v);
		push_up (root);
	}

	int ANS;

	inline void find (int root, int l, int r, int x, int y, int val)
	{
		if (ANS != -1) return ;
		if (l == r) { ANS = l; return ; }
		int mid = (l + r) >> 1;
		if (Tree[root << 1].Max >= val && x <= mid) find (lson, x, y, val);
		if (Tree[root << 1 | 1].Max >= val && y > mid) find (rson, x, y, val);
	}

}

main()
{
#ifdef hk_cnyali
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
	SEG :: build (1, 1, N);
	while (M--)
	{
		int x = read<int>(), y = read<int>();
		SEG :: update (1, 1, N, x, y);
		A[x] = y;
		if (A[1] == 0) { puts("1"); continue; }
		int i = 1, j, fl = 0;
		while (1)
		{
			if (i == N) break;
			int sum = SEG :: query_sum (1, 1, N, 1, i);
			int MAX = SEG :: query_max (1, 1, N, i + 1, N);
//			cout<<i<<" "<<sum<<" "<<MAX<<endl;
			if (MAX < sum) break;
			SEG :: ANS = -1;
			SEG :: find (1, 1, N, i + 1, N, sum);
			j = SEG :: ANS;
			if (j == -1) break;
			if (A[j] == SEG :: query_sum (1, 1, N, 1, j - 1)) { fl = 1; break; }
			i = j;
		}
		if (!fl) puts("-1");
		else printf("%lld\n", j);
	}
	return 0;
}