CodeForces992E 二分 + 树状数组（线段树）

时间：2022-05-16 07:33:44

http://codeforces.com/problemset/problem/992/E

题意：给定一个序列 ai​ ，记其前缀和序列为 si​ ，有 q 个询问，每次单点修改，询问是否存在一个 i 满足 ai​=si−1​，有多解输出任意一个，无解输出 -1。

思路一：构造一个b[i] = a[i] - s[i - 1]的序列，答案就是在其中寻找为0的位置，对每一次操作进行一个线段树的单点修改和区间修改之后对一整个区间寻找是否存在0的位置，但是最坏的情况下能达到N * Q * lnN，虽然据说可过但是觉得并不靠谱

思路2：ai = si - 1，考虑转化一下就变成了si = 2 * s(i - 1)，所以对于起始位置x，下一个可能符合答案ans - 1的位置的就是最大的sk < 2 * sx,因为x到k中间的位置很显然前一个数的s会比sx大，后一个数的位置会比sk小，很显然并不满足。

所以可以考虑用树状数组维护前缀和之后用一个类似跳的算法加一个二分寻找ans，时间复杂度是QlnNlnNlnN,有点慢但依然可以过。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 2e5 + ;

const int maxm = 1e6 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,Q;

LL a[maxn];

LL tree[maxn];

void add(int x,int t){for(;x <= N ; x += x & -x) tree[x] += t;}

LL getsum(int x){LL ans = ; for(;x >  ; x -= x & -x) ans += tree[x]; return ans;}

void solve(){

    if(a[] == ) return (void)puts("");

    int x = ;

    while(x < N){

        LL sum = getsum(x) * ;

        if(getsum(x + ) == sum) return (void)printf("%d\n",x + );

        int ans = x,l = x + ,r = N;

        while(l <= r){

            int m = (l + r) >> ;

            if(getsum(m) < sum){

                ans = m;

                l = m + ;

            }else{

                r = m - ;

            }

        }

        if(ans > N) break;

        x = (x == ans)?ans + :ans;

    }

    puts("-1");

}

int main()

{

    Sca2(N,Q);

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

        Scl(a[i]); add(i,a[i]);

    }

    while(Q--){

        int x; LL p;

        scanf("%d%lld",&x,&p);

        add(x,p - a[x]); a[x] = p;

        solve();

    }

    return ;

}

思路2

思路3：将跳的思路改为寻找一个最小的大于si的位置，考虑用线段树维护一下区间最大值，树状数组维护前缀和，可以优化掉一个ln

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 2e5 + ;

const int maxm = 1e6 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,Q;

LL fa[maxn],a[maxn];

void add(int p,int t){

    for(;p <= N ; p += p & -p) fa[p] += t;

}

LL getsum(int p){

    LL ans = ;

    for(;p > ; p -= p & -p) ans += fa[p];

    return ans;

}

struct Node{

    int pos;

    LL MAX;

    Node(int pos = ,LL MAX = ):pos(pos),MAX(MAX) {}

};

Node operator + (Node a,Node b){

    if(a.MAX >= b.MAX) return a;

    return b;

}

Node operator - (Node a,Node b){

    if(a.pos >= b.pos) return b;

    return a;

}

struct Tree{

    int l,r;

    Node MAX;

}tree[maxn << ];

void Build(int t,int l,int r){

    tree[t].l = l; tree[t].r = r;

    if(l == r){

        tree[t].MAX.MAX = a[l];

        tree[t].MAX.pos = l;

        return;

    }

    int m = (l + r) >> ;

    Build(t << ,l,m); Build(t <<  | ,m + ,r);

    tree[t].MAX = tree[t << ].MAX + tree[t <<  | ].MAX;

}

void update(int t,int pos,LL val){

    if(tree[t].l == tree[t].r){

        tree[t].MAX.MAX = val;

        return;

    }

    int m = (tree[t].l + tree[t].r) >> ;

    if(pos <= m) update(t << ,pos,val);

    else update(t <<  | ,pos,val);

    tree[t].MAX = tree[t << ].MAX + tree[t <<  | ].MAX;

}

Node query(int t,int l,int r,LL sum){

    if(l <= tree[t].l && tree[t].r <= r){

        if(tree[t].MAX.MAX < sum) return Node(INF,1e18);

        if(tree[t].l == tree[t].r) return tree[t].MAX;

        int m = (tree[t].l + tree[t].r) >> ;

        if(tree[t << ].MAX.MAX >= sum) return query(t << ,l,m,sum);

        return query(t <<  | ,m + ,r,sum);

    }

    int m = (tree[t].l + tree[t].r) >> ;

    if(r <= m) return query(t << ,l,r,sum);

    else if(l > m) return query(t <<  | ,l,r,sum);

    else return query(t << ,l,m,sum) - query(t <<  | ,m + ,r,sum);

}

int solve(){

    if(getsum() == ) return ;

    int s = ;

    while(s < N){

        LL now = getsum(s);

        Node MAX = query(,s + ,N,now);

        if(MAX.pos == INF) return -;

        if(getsum(MAX.pos - ) == MAX.MAX) return MAX.pos;

        s = MAX.pos;

    }

    return -;

}

int main()

{

    Sca2(N,Q);

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

        Scl(a[i]);

        add(i,a[i]);

    }

    Build(,,N);

    while(Q--){

        int x; LL p;

        scanf("%d%lld",&x,&p);

        update(,x,p);

        add(x,p - a[x]); a[x] = p;

        Pri(solve());

    }

    return ;

}

相关文章