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;
}