Codeforces Round #489 (Div. 2) E - Nastya and King-Shamans

题目大意：有n个数，每一次操作更改一个数，每次操作之后问你是否有一个数等于其前面所有数的和。

思路：好题，想了很久没想出来，看了题解，主要思想就是满足条件的数会成倍增长，如我们知道了

1 - i 里面没有满足条件的数，那么我们找一个最小的 j 满足 a[ j ] >= sum(1, i)，j就可能成为一个答案，

我们check一下，如果可以就是这个点，如果不行那么不可能前缀就从 1 - i 变成了 1 - j，这个过程最多

执行log(max(a[ i ])) 次，因为前缀和每次操作至少×2，这样我们用线段树维护区间和，区间最大值就好了。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

using namespace std;

const int N = 2e5 + ;

const int M = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

LL mx[N << ], sum[N << ];

int n, q;

void update(int pos, int v, int l, int r, int rt) {

    if(l == r) {

        sum[rt] = v;

        mx[rt] = v;

        return;

    }

    int mid = l + r >> ;

    if(pos <= mid) update(pos, v, l, mid, rt << );

    else update(pos, v, mid + , r, rt <<  | );

    sum[rt] = sum[rt << ] + sum[rt <<  | ];

    mx[rt] = max(mx[rt << ], mx[rt <<  | ]);

}

LL getSum(int L,int R, int l, int r, int rt) {

    if(l >= L && r <= R) return sum[rt];

    int mid = l + r >> ;

    LL ans = ;

    if(L <= mid) ans += getSum(L, R, l, mid, rt << );

    if(R > mid) ans += getSum(L, R, mid + , r, rt <<  | );

    return ans;

}

void getMxId(int L, int R, LL v, int l, int r, int rt, LL &ret, LL &id) {

    if(mx[rt] < v || id != -) return;

    if(l == r) {

        id = l;

        ret = mx[rt];

        return;

    }

    int mid = l + r >> ;

    if(L <= mid) getMxId(L, R, v, l, mid, rt << , ret ,id);

    if(R > mid) getMxId(L, R, v, mid + , r, rt <<  | , ret, id);

}

int cal() {

    if(getSum(, , , n, ) == ) return ;

    int now = ;

    while(now < n) {

        LL sum = getSum(, now, , n, ), ret = -, id = -;

        getMxId(now + , n, sum, , n, , ret, id);

        if(id == -) return -;

        sum = getSum(, id - , , n, );

        if(sum == ret) return id;

        now = id;

    }

    return -;

}

int main() {

    scanf("%d%d", &n, &q);

    for(int i = ; i <= n; i++) {

        int x; scanf("%d", &x);

        update(i, x, , n, );

    }

    while(q--) {

        int pos, v; scanf("%d%d", &pos, &v);

        update(pos, v, , n, );

        printf("%d\n", cal());

    }

    return ;

}

/*

*/

巴特西

Codeforces Round #489 (Div. 2) E - Nastya and King-Shamans

最新文章

热门文章