CF992E Nastya and King-Shamans
题目大意
给定一个序列 \(a_i\) ，记其前缀和序列为 \(s_i\) ，有 \(q\) 个询问，每次单点修改，询问是否存在一个 \(i\) 满足 \(a_i=s_{i-1}\) ，有多解输出任意一个，无解输出 \(-1\) 。
分析
这里，以一贯的习惯，提供一下我整个的思维过程，希望有些启示作用。
首先看到，\(a_i=s_{i-1}\)，立马就想要转换一下式子\(s_i=2s_{i-1}\)。
所以我就想，直接维护前缀和数组就好啦，加个标记表示该区间有符合该式子的位置，查询的时候，直接线段树上二分。
但是，问题也出现在这里，我们的单点修变为了区间修。此时我们可以很容易的发现，区间修的时候，我们除非暴力扫描区间内的每一个值，去重新比对，才能更新我们的标记。那时间铁铁T掉了。
因此接下来，我们有两个思考方向。
- 考虑能不能再转换一下式子，以及需要维护的东西，使得我们可以重新单点修，单点考虑。
- 或者，我们考虑变换一下式子，以及要维护的东西，看看能不能找找性质，使得暴力判断的次数可以被接受，即考虑能否转换为势能线段树
我们再次观察原来的式子\(a_i=s_{i-1}\)，其中的\(s_{i-1}\)，导致我们操作的时候，一定要考虑前缀和，则我们单点修\(a_i\)时，势必会影响区间[i+1,n]前缀和。那我们就放弃第一个方向，准头考虑一下第二个方向。
我们注意到第二个式子\(s_i=2s_{i-1}\)。我们刚遇到的一大问题就是，每次需要暴力的比对才能知道有没有倍数存在。但我们可以等价转化一下为\(s_i-2s_{i-1}=0\)，也为合法情况存在的等价条件。则，我们考虑线段树里，不维护前缀和了，维护\(s_i-2s_{i-1}\)。单点修也比较容易，单点修\(a_i\)为y时，设d为\(y-a_i\)。我们只需要将i单点的值+d，区间[i+1,n]的值-d即可。这个很好推，自己试一试。此时我们需要考虑的就是，整个区间内单点值为0的下标是什么。
这个好像也很暴力。但是我们注意两个性质。
- \(s_i>=s_{i-1}\)
- 我们维护的值是\(s_i-2s_{i-1}\)。同时，我们要求的值为
0。
因此，我们可以很容易的发现，每次如果当前下标i对应的值需要大于0，则\(s_i\)相对于\(s_{i-1}\)翻一倍。
所以我们可以发现，线段树中中大于0的点不超过\(O(logna)\)，则若每次我们只考虑这个区间最大值>=0时，才去扫这个区间。
就结束啦，看看代码。
Ac_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
struct Node
{
int l,r;
LL mx;
LL add;
}tr[N<<2];
int n,q;
int a[N];
LL s[N];
void pushup(int u)
{
tr[u].mx = max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u] = {l,r,s[l]-2*s[l-1],0};
return ;
}
tr[u] = {l,r};
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void pushdown(int u)
{
auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
if(root.add)
{
left.mx += root.add;left.add += root.add;
right.mx += root.add;right.add += root.add;
root.add = 0;
}
}
void modify(int u,int l,int r,int k)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].mx += k;
tr[u].add += k;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
int query(int u)
{
if(tr[u].l==tr[u].r)
{
if(!tr[u].mx) return tr[u].l;
return -1;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = -1;
if(tr[u<<1].mx>=0) res = query(u<<1);
if(res!=-1) return res;
if(tr[u<<1|1].mx>=0) res = query(u<<1|1);
return res;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i] = a[i] + s[i-1];
}
build(1,1,n);
while(q--)
{
int x,y;cin>>x>>y;
int d = y - a[x];
a[x] = y;
modify(1,x,x,d);
if(x+1<=n) modify(1,x+1,n,-d);
cout<<query(1)<<endl;
}
return 0;
}