CF992E Nastya and King-Shamans
题意翻译
给定一个序列 (a_i)，记其前缀和序列为 (s_i)，有 (q) 个询问，每次单点修改，询问是否存在一个 (i) 满足 (a_i=s_{i-1})，有多解输出任意一个，无解输出 (-1)。
输入输出格式
输入格式：
The first line contains two integers (n) and (q)
The second line contains n n integers (a_{1},...,a_{n}),where (a_{i})is the magic power of the (i)-th shaman.
After that (q) lines follow, the (i) -th of them contains two integers (p_{i}) and (x_{i})that mean that the new power of the (p_{i}).
输出格式：
Print (q) lines, the (i) -th of them should contain (-1) , if after the (i) -th change there are no shaman-kings, and otherwise a single integer (j) , where (j) is an index of some king-shaman after the (i) -th change.
If there are multiple king-shamans after each change, print the index of any of them.
数据范围
(1 le n,q le 10^5,0 le a_i le 10^9,1 le p_i le n,0 le x_i le 10^9)
注意一下数据范围，发现都是正整数。
所以前缀和按位置是不降的。
考虑一个暴力，找到每个(a_i ge s_{i-1})的位置，然后检查它是否合法。
考虑这样的一个位置最多有多少个，发现不超过(log 10^9)，所以这个暴力复杂度是对的。
至于实现，可以线段树维护(a_i-s_{i-1})的最大值，支持区间加全局查询就行了。
Code:
#include <cstdio>
#define ll long long
#define ls id<<1
#define rs id<<1|1
const int N=2e5+10;
ll max(ll x,ll y){return x>y?x:y;}
ll mx[N<<2],a[N],f[N],tag[N<<2],x;
int n,q;
void updata(int id){mx[id]=max(mx[ls],mx[rs]);}
void build(int id,int l,int r)
{
if(l==r)
{
mx[id]=a[l]-f[l-1];
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
updata(id);
}
void pushdown(int id)
{
if(tag[id])
{
tag[ls]+=tag[id],tag[rs]+=tag[id];
mx[ls]+=tag[id],mx[rs]+=tag[id];
tag[id]=0;
}
}
void change1(int id,int l,int r,int p,ll d)
{
if(l==r)
{
mx[id]+=d;
return;
}
pushdown(id);
int mid=l+r>>1;
if(p<=mid) change1(ls,l,mid,p,d);
else change1(rs,mid+1,r,p,d);
updata(id);
}
void change0(int id,int L,int R,int l,int r,ll d)
{
if(l>r) return;
if(l==L&&r==R)
{
tag[id]+=d,mx[id]+=d;
return;
}
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) change0(ls,L,Mid,l,r,d);
else if(l>Mid) change0(rs,Mid+1,R,l,r,d);
else change0(ls,L,Mid,l,Mid,d),change0(rs,Mid+1,R,Mid+1,r,d);
}
int query(int id,int l,int r)
{
if(l==r) return mx[id]==0?l:-1;
if(mx[id]<0) return -1;
pushdown(id);
int mid=l+r>>1;
int la=query(ls,l,mid);
return ~la?la:query(rs,mid+1,r);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",a+i),f[i]=f[i-1]+a[i];
build(1,1,n);
for(int p,i=1;i<=q;i++)
{
scanf("%d%lld",&p,&x);
change0(1,1,n,p+1,n,a[p]-x);
change1(1,1,n,p,x-a[p]);
a[p]=x;
printf("%d
",query(1,1,n));
}
return 0;
}
2018.10.9