题意

一个序列
要你支持单点修改
然后每一次问你是否存在一个位置，使得这个位置的值等于他前一位的前缀和

分块！

如果我们把每一个位置上的值前去他前面所有的数，那么问题就等价于找是否存在0
那么问题就是要支持区间修改，然后询问是否存在0这个数字
容易想到分块维护。和loj6187的维护方法是一样的
在块内维护一个hash表。
时间复杂度可以视为是$O(q\sqrt{n})$的
然而这样T了。可能常数较大
卡了一手常但是并没有卡过去

寻找别的方法！

所谓的寻找别的方法其实就是看题解
我们考虑，不这么转化模型。。
我们把模型转化成，找一个$sum_i=sum_{i-1}*2$，其中sum表示前缀和
发现这个*2的形式
想到可以暴力跳。。
考虑到sum是递增的，那么我们现在在一个点$i$，那么答案必须满足$sum_x>=sum_i*2$
发现这样最多只会跳$loga_i$次
于是用树状数组来维护即可
跳的过程用二分加速
其实如果你用倍增的话，应该会更快
时间复杂度是$O(nlog^2nloga)$
看起来并不比分块优秀，但是常数较小，所以跑得飞快

分块的代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=200005;
const int P=100003;
int p,x;
int n,q;
LL a[N];
LL g[N];
int get_hash(LL x)  {
   x<<=1;return (x%P+P)%P;}
int read ()
{char ch=getchar();int x=0;while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9')    {
   x=x*10+ch-'0';ch=getchar();}return x;
}
bool tf;
int ans;
struct qq {int cnt;LL lzy;int q[450],ed;int last[P],lst[450];pair<LL,int> s[450];qq () {lzy=0;cnt=0;ed=0;}void insert (int x,int id){//printf("insert:%d %d\n",x,id);int xx=get_hash(x);int now;if (ed!=0)  now=q[ed--];else now=++cnt;s[now].first=x;s[now].second=id;lst[now]=last[xx];last[xx]=now;}void del (int x,int id){int xx=get_hash(x);//  printf("del:%d %d %d\n",x,xx,id);int ll=0,now;for (int u=last[xx];u!=0;u=lst[u]){if (s[u].first==x&&s[u].second==id) {now=u;break;}ll=u;}//printf("%d %d\n",now,ll);if (ll==0) last[xx]=lst[now];else lst[ll]=lst[now];q[++ed]=now;}void find (LL x){x-=lzy;int xx=get_hash(x);for (int u=last[xx];u!=0;u=lst[u])if (s[u].first==x){tf=true;ans=s[u].second;return ;}}
}T[450];
int siz;
void change (int l,int r,LL x)//这一段加这么多 
{if (l>r) return ;
//  printf("l:%d r:%d x:%d\n",l,r,x);int L=l/siz,R=r/siz;if (L==R){for (int u=l;u<=r;u++){T[L].del(g[u],u);g[u]+=x;T[L].insert(g[u],u);}return ;}for (int u=L+1;u<R;u++) T[u].lzy+=x;//printf("begin:\n");for (int u=l;u<(L+1)*siz;u++){//printf("%d\n",u);T[L].del(g[u],u);//  printf("next:");g[u]+=x;T[L].insert(g[u],u);}//printf("mid\n");for (int u=R*siz;u<=r;u++){T[R].del(g[u],u);g[u]+=x;T[R].insert(g[u],u);}//printf("end\n");
}
void solve ()
{if (ans!=-1)    return ;tf=false;int nn=n/siz;ans=-1;int xx=p/siz;for (int u=xx;u<=nn;u++){T[u].find(0);if (tf) break;}
}
int main()
{n=read();q=read();siz=sqrt(n);for (int u=1;u<=n;u++)a[u]=read();int sum=0;for (int u=1;u<=n;u++) {g[u]=a[u]-sum;T[u/siz].insert(a[u]-sum,u);sum=sum+a[u];}/*for (int u=1;u<=n;u++)    printf("%d ",g[u]);printf("\n");*/ans=-1;solve();for (int u=1;u<=q;u++){p=read();x=read();change(p,p,x-a[p]);change(p+1,n,a[p]-x);if (p<=ans) ans=-1;solve();a[p]=x;printf("%d\n",ans);}return 0;
}

log^3的代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=200005;
int n,q;
int a[N];
LL f[N];
int lb (int x)  {
   return x&(-x);}
void change (int x,int y)   {
   while (x<=n){f[x]=f[x]+y;x+=lb(x);}}
LL get (int x)  {LL lalal=0;while (x>0) {lalal=lalal+f[x];x-=lb(x);}return lalal;}
void solve ()
{int now=1;LL now1=get(1);if (now1==0)    {
   printf("1\n");return ;}while (now<=n){int l=now+1,r=n,lalal=-1;while (l<=r){int mid=(l+r)>>1;LL x=get(mid);if (x>=now1*2)  {lalal=mid;r=mid-1;}else l=mid+1;}if (lalal==-1) break;now=lalal;now1=get(lalal);if (now1==get(lalal-1)*2){printf("%d\n",lalal);return ;}}printf("-1\n");
}
int read ()
{char ch=getchar();int x=0;while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9')    {x=x*10+ch-'0';ch=getchar();}return x;
}
int main()
{n=read();q=read();for (int u=1;u<=n;u++)  {a[u]=read();change(u,a[u]);}for (int u=1;u<=q;u++){int x,p;p=read();x=read();change(p,x-a[p]);a[p]=x;solve();}return 0;
}