25.CF992E Nastya and King-Shamans 转化+线段树二分

25.CF992E Nastya and King-Shamans 转化+线段树二分

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持单点修改，查询序列中 $a[i]=s[i-1]$ 的点(SPJ)

线段树维护$a_i-s_{i-1}$的区间最大值，然后树上二分查询即可

洛谷传送门：CF992E Nastya and King-Shamans - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Nastya and King-Shamans (codeforces.com)

题目分析

首先考虑暴力解决：每次暴力检查所有的$a[i]$，需要检查$n$个数字。

发现对于所有的$i$，满足条件的一定不超过$\log s_n$个：

• 因为对于满足条件的$i,a_i-s_{i-1}\ge 0$, 因此$s_i\ge 2s_{i-1}$

• 故每有一个满足条件的$i$，$s$就会翻倍。因此总共满足条件的不超过$\log s_n$个

用线段树维护$a_i-s_{i-1}$的区间最大值，由于查询的叶子节点不会超过$\log s_n$故复杂度正确

• 单点修改操作等同于对前缀和后缀序列的区间修改及对原序列的单点修改，线段树支持区间修改即可

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6 + 10, MOD = 1e9 + 7;

namespace ffastIO {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}

using ffastIO::read;

int a[N], b[N], s[N];

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    int tree[N << 2], lazy[N << 2];

    inline void push_up(int rt){ tree[rt] = max(tree[ls], tree[rs]); }

    inline void push_down(int rt, int m){
        if(!lazy[rt]) return;
        tree[ls] += lazy[rt], tree[rs] += lazy[rt];
        lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
        lazy[rt] = 0; 
    }

    void build(int rt, int l, int r){
        lazy[rt] = 0;
        if(l == r) return (void)(tree[rt] = a[l] - s[l - 1]);
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int L, int R, int val){
        if(l >= L && r <= R){
            tree[rt] += val;
            lazy[rt] += val;
            return;
        }
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        if(mid >= L) update(lson, L, R, val);
        if(mid < R) update(rson, L, R, val);
        push_up(rt);
    }

    int ans = -1;

    void query(int rt, int l, int r){
        if(ans != -1) return;
        if(l == r){
            if(tree[rt] == 0) ans = l;
            return;
        } 
        push_down(rt, r - l + 1);
        int mid = l + r >> 1;
        if(tree[ls] >= 0) query(lson);
        if(tree[rs] >= 0) query(rson);
    }
}


inline void solve(){
    int n = read(), q = read();
    for(int i = 1; i <= n; i++) a[i] = read(), s[i] = s[i - 1] + a[i];
    // for(int i = 1; i <= n; i++) b[i] = a[i] - s[i - 1];  
    SegTree::build(1, 1, n);
    for(int i = 1; i <= q; i++){
        int p = read(), x = read();
        int det = x - a[p]; a[p] = x;
        SegTree::update(1, 1, n, p, p, det);
        if(p != n) SegTree::update(1, 1, n, p + 1, n, -det);
        SegTree::ans = -1;
        SegTree::query(1, 1, n);
        printf("%d\n", SegTree::ans);
    }
}

signed main(){
    solve();
    return 0;
}
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