转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/problemset/problem/992/E


题意:给一个序列a,q次操作。每次操作单点修改。每次操作后,询问序列a中有没有一个位置满足a[i]=bit[i-1],如果有,随便输出一个位置,如果没有输出-1。其中bit为前缀和数组。


题解:
容易想到建立线段树维护a[i]-bit[i-1],问题就转化成查询线段树内值为0的位置。记录一个区间最大值maxx,查询时,如果这个区间maxx小于0,说明这个区间内的数全都不满足,直接剪枝,否则一直查询到叶子节点。

看上去很暴力,其实想想是可行的。因为如果要避开这个剪枝,a[i]-bit[i-1]必须大于0(如果等于0的话,也能很快走到叶子节点),那么这个序列假设a[1]=0,那么a[1]就至少为1,a[2]至少为2,a[3]至少为4,以此类推。也就是说,最多走过log个叶子节点,一定能得出答案。

代码:

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
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
typedef long long ll;
typedef unsigned long long ull;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define VI vector<int>
#define VL vector<ll>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=998244353;
ll a[MAX],bit[MAX];
struct Segment_Tree
{
#define ls (id<<1)
#define rs (id<<1|1)
int n,ql,qr;
ll a[MAX],tag[MAX<<2],maxx[MAX<<2],qv;
void pushup(int id)
{
maxx[id]=max(maxx[ls],maxx[rs]);
}
void pushdown(int id)
{
if(!tag[id]) return;
maxx[ls]+=tag[id];
maxx[rs]+=tag[id];
tag[ls]+=tag[id];
tag[rs]+=tag[id];
tag[id]=0;
}
void build(int l,int r,int id)
{
tag[id]=0;
maxx[id]=0;
if(l==r)
{
maxx[id]=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
pushup(id);
}
void update(int l,int r,int id)
{
if(l>=ql&&r<=qr)
{
tag[id]+=qv;
maxx[id]+=qv;
return;
}
pushdown(id);
int mid=(l+r)>>1;
if(ql<=mid) update(l,mid,ls);
if(qr>mid) update(mid+1,r,rs);
pushup(id);
}
int query(int l,int r,int id)
{
int res=-1;
if(maxx[id]<0) return -1;
if(l==r)
{
if(maxx[id]==0) return l;
return -1;
}
pushdown(id);
int mid=(l+r)>>1;
if(ql<=mid) res=query(l,mid,ls);
if(res!=-1) return res;
if(qr>mid) res=query(mid+1,r,rs);
return res;
}
void build(int _n){n=_n;build(1,n,1);}
}tr;
int main()
{
int n,i,q;
ll x;
while(~scanf("%d%d",&n,&q))
{
bit[0]=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
bit[i]=bit[i-1]+a[i];
tr.a[i]=a[i]-bit[i-1];
}
tr.build(n);
while(q--)
{
scanf("%d%lld",&tr.ql,&x);
tr.qv=x-a[tr.ql];
a[tr.ql]=x;
tr.qr=tr.ql;
tr.update(1,n,1);
tr.qv*=-1;
tr.ql++;
tr.qr=n;
if(tr.ql<=n) tr.update(1,n,1);
tr.ql=1;
printf("%d\n",tr.query(1,n,1));
}
}
return 0;
}