CF992ENastyaAndKing-Shamans题解--神奇复杂度+线段树

CF992ENastyaAndKing-Shamans题解—神奇线段树

题目链接

https://cn.vjudge.net/problem/CodeForces-992E

分析

首先我们从$p=1$开始找比大于等于$[1,p]$这个前缀的元素下标$x$,同时判断$a[x]$是否合法,若不合法$p=x$继续找.但是有个性质就是$sum(1,x)>= 2 * sum(1,p) $.非常显然因为$a[x]>=sum(1,p)$

所以每次我们下一个要找的前缀都大于等于上一次的两倍,只用查找$ \log$ $max_w$次,同时线段树维护单点修改元素,区间查询前缀,时间复杂度$O(N log N$ $logMaxw)$

注意开long long ,查了好久的错

代码

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
int n,q;ll a[maxn];
ll sum[maxn<<2],mx[maxn<<2];
void build(int now,int l,int r){
if(l==r){
sum[now]=mx[now]=a[l];return ;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
mx[now]=max(mx[now<<1],mx[now<<1|1]);
sum[now]=sum[now<<1]+sum[now<<1|1];return ;
}
int t;ll dta;
void update(int now,int l,int r){
if(l==r){
a[l]=dta;
mx[now]=sum[now]=dta;return ;
}
int mid=(l+r)>>1;
if(t<=mid)update(now<<1,l,mid);
else update(now<<1|1,mid+1,r);
mx[now]=max(mx[now<<1],mx[now<<1|1]);
sum[now]=sum[now<<1]+sum[now<<1|1];return ;
}
ll ans=0;
int L,R;
void query_sum(int now,int l,int r){
if(L<=l&&r<=R){
ans+=sum[now];return ;
}
int mid=(l+r)>>1;
if(L<=mid)query_sum(now<<1,l,mid);
if(mid<R)query_sum(now<<1|1,mid+1,r);
return ;
}
void query_exi(int now,int l,int r){
//printf("%d\n",mx[now]);
if(mx[now]<dta)return ;
if(l==r){
//printf("%d\n",l);
ans=l;
return ;
}
int mid=(l+r)>>1;
//printf("%d %d\n",mx[now<<1],l);
if(L<=mid&&mx[now<<1]>=dta)query_exi(now<<1,l,mid);
if(ans!=-1)return ;
if(mid<R&&mx[now<<1|1]>=dta)query_exi(now<<1|1,mid+1,r);
return ;
}
int main(){
read(n),read(q);
for(ri i=1;i<=n;i++)read(a[i]);
build(1,1,n);
while(q--){
read(t),read(dta);
update(1,1,n);
int p=1;
if(a[1]==0){
puts("1");
}
else while(1){
ans=0;
L=1,R=p;
query_sum(1,1,n);//puts("ss");
dta=ans,ans=-1;//printf("%d %d %d\n",p,ans,dta);
L=p+1,R=n;
query_exi(1,1,n);
if(ans==-1){
puts("-1");
break;
}
if(ans==p+1){
p=ans;ans=0;
}
else {
L=p+1,R=ans-1;
p=ans,ans=0;query_sum(1,1,n);
}
if(a[p]==dta+ans){
printf("%d\n",p);
break;
}
if(p==n){puts("-1");break;}
}
}
return 0;
}