HDU 6315 Naive Operations（线段树+区间维护）多校题解

题意：a数组初始全为0，b数组题目给你，有两种操作：

思路：dls的思路很妙啊，我们可以将a初始化为b，加一操作改为减一，然后我们维护一个最小值，一旦最小值为0，说明至少有一个ai > bi，那么找出所有为0的给他的最终结果加上一并且重置为bi，维护一个区间和，询问时线段树求和。一开始updateMin没加判断，单个复杂度飙到nlog(n)，疯狂TLE...

代码：

#include<cstdio>

#include<vector>

#include<stack>

#include<queue>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#define ll long long

const int maxn = 100000+5;

const int maxm = 100000+5;

const int MOD = 1e7;

const int INF = 0x3f3f3f3f;

using namespace std;

int n,q;

ll Min[maxn<<2],lazy[maxn<<2],sum[maxn << 2],b[maxn];

void push_down(int rt){

    if(lazy[rt]){

        Min[rt << 1] -= lazy[rt];

        Min[rt << 1 | 1] -= lazy[rt];

        lazy[rt << 1] += lazy[rt];

        lazy[rt << 1 | 1] += lazy[rt];

        lazy[rt] = 0;

    }

}

void push_up(int rt){

    Min[rt] = min(Min[rt << 1],Min[rt << 1 | 1]);

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

}

void build(int l,int r,int rt){

    if(l == r){

        lazy[rt] = sum[rt] = 0;

        Min[rt] = b[l];

        return;

    }

    int m = (l + r) >> 1;

    build(l,m,rt << 1);

    build(m + 1,r,rt << 1 | 1);

    lazy[rt] = 0;

    push_up(rt);

}

void updateMin(int l,int r,int rt){

    if(l == r){

        if(Min[rt] == 0){

            Min[rt] = b[l];

            sum[rt]++;

        }

        return;

    }

    push_down(rt);

    int m = (l + r) >> 1;

    if(!Min[rt << 1])

        updateMin(l,m,rt << 1);

    if(!Min[rt << 1 | 1])

        updateMin(m + 1,r,rt << 1 | 1);

    push_up(rt);

}

void update(int L,int R,int l,int r,int rt){

    if(L <= l && R >= r){

        Min[rt]--;

        lazy[rt]++;

        while(!Min[rt]){

            updateMin(l,r,rt);

        }

        return;

    }

    push_down(rt);

    int m = (l + r) >> 1;

    if(L <= m)

        update(L,R,l,m,rt << 1);

    if(R > m)

        update(L,R,m + 1,r,rt << 1 | 1);

    push_up(rt);

}

ll query(int L,int R,int l,int r,int rt){

    if(L <= l && R >= r){

        return sum[rt];

    }

    //push_down(rt);

    ll ans = 0;

    int m = (l + r) >> 1;

    if(L <= m)

        ans += query(L,R,l,m,rt << 1);

    if(R > m)

        ans += query(L,R,m + 1,r,rt << 1 | 1);

    return ans;

}

int main(){

    while(~scanf("%d%d",&n,&q)){

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

            scanf("%lld",&b[i]);

        build(1,n,1);

        char s[20];

        int l,r;

        while(q--){

            scanf("%s%d%d",s,&l,&r);

            if(s[0] == 'a'){

                update(l,r,1,n,1);

            }

            else{

                ll ans = query(l,r,1,n,1);

                printf("%lld\n",ans);

            }

        }

    }

    return 0;

}

/*

5 12

1 5 2 4 3

add 1 4

query 1 4

add 2 5

query 2 5

add 3 5

query 1 5

add 2 4

query 1 4

add 2 5

query 2 5

add 2 2

query 1 5

*/

巴特西

HDU 6315 Naive Operations（线段树+区间维护）多校题解

最新文章

热门文章