CF992E 题解
简化题意：单点修改，设序列的前缀和序列是 $s_i$，查询是否存在一个 $i$ 满足 $a_i=s_{i-1}$。
思路：
观察满足条件的数的个数。在不考虑 $0$ 的情况下，如果一个 $a_i$ 满足条件，那么对于一个比他小的满足条件的数 $a_j$，一定会有 $a_j=s_{j-1}$，而 $s_{j-1}+a_j=s_j\leqslant s_{i-1}=a_i$，这就说明 $2\times a_j\leqslant a_i$，因此满足条件的数至多有 $O(\log V)$ 个。如果考虑 $0$，那么任意一个在全零前缀里的数都满足条件，随便选一个就可以了。
因此，我们就可以暴力来找可能满足条件的数，即不断地找区间内最大的满足 $s_{i-1}\leqslant a_i$ 的 $i$ ，常规做法是线段树上二分。而在本题中这个区间是一段前缀，可以直接在树状数组上二分，非常好写。
复杂度 $O(n\log n\log V)$。
const int N=200501; int n,Q; int a[N],Lg; ll c[N]; inline void add(int x,int y){for(;x<=n;x+=x&(-x))c[x]+=y;} inline pair<int,int> query(int x){ int k=0; ll sum=0; for(int i=Lg;~i;i--){ int cur=k|(1<<i); if(cur<=n&&sum+c[cur]<=x)sum+=c[cur],k=cur; } return make_pair(k,sum); } inline int query(){ if(a[1]==0)return 1; int cur=2e9; do{ cur>>=1; pair<int,int> tmp=query(cur); if(tmp.second==a[tmp.first+1]){ return tmp.first+1; } }while(cur); return -1; } int main(){ n=read(),Q=read(); Lg=log2(n); for(int i=1;i<=n;i++)a[i]=read(),add(i,a[i]); while(Q--){ int p=read(),x=read(); add(p,x-a[p]); a[p]=x; write(query());putchar('\n'); } return 0; }