给你一个序列,支持三种操作:

0 x y t :将 [x,y] 内大于 t 的数变为 t ;
1 x y :求 [x,y] 内所有数的最大值;
2 x y :求 [x,y] 内所有数的和。

多组测试数据,∑n,∑m≤106

参考代码

#include <bits/stdc++.h>
#define long long long
using namespace std;
const long N = 1e6 + 10;
long sum[N<<2];
long max1[N<<2], max2[N<<2], cnt[N<<2], flag[N<<2];
void pushup(long p, long l, long r) {
    sum[p] = sum[p<<1] + sum[p<<1|1];

    if(max1[p<<1] > max1[p<<1|1]) {
        max1[p] = max1[p<<1];
        cnt[p] = cnt[p<<1];
    } else if(max1[p<<1] < max1[p<<1|1]) {
        max1[p] = max1[p<<1|1];
        cnt[p] = cnt[p<<1|1];
    } else {
        max1[p] = max1[p<<1];
        cnt[p] = cnt[p<<1] + cnt[p<<1|1];
    }
    
    max2[p] = max(max2[p<<1], max2[p<<1|1]);
    if(max1[p<<1] != max1[p<<1|1])
        max2[p] = max(max2[p], min(max1[p<<1], max1[p<<1|1]));
    //printf("[%lld, %lld] %lld\n", l, r, max2[p]);
}
void change(long p, long x) {
    sum[p] -= (max1[p] - x) * cnt[p];
    max1[p] = flag[p] = x;
}
void pushdown(long p) {
    if(flag[p] == -1) return;
    if(max1[p<<1] > flag[p]) change(p<<1, flag[p]);
    if(max1[p<<1|1] > flag[p]) change(p<<1|1, flag[p]);
    flag[p] = -1;
}
void build(long p, long l, long r) {
    if(l == r) {
        scanf("%lld", &sum[p]);
        max1[p] = sum[p];
        cnt[p] = 1;
        max2[p] = -1;
        return;
    }
    long mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    pushup(p, l, r);
    flag[p] = -1;
}
long queryMax(long p, long l, long r, long L, long R) {
    if(L <= l && r <= R) return max1[p];
    long ans = 0;
    long mid = (l + r) >> 1;
    pushdown(p);
    if(L <= mid) ans = max(ans, queryMax(p<<1, l, mid, L, R));
    if(R > mid) ans = max(ans, queryMax(p<<1|1, mid+1, r, L, R));
    return ans;
}
long querySum(long p, long l, long r, long L, long R) {
    if(L <= l && r <= R) return sum[p];
    long mid = (l + r) >> 1;
    long sum = 0;
    pushdown(p);
    if(L <= mid) sum += querySum(p<<1, l, mid, L, R);
    if(R > mid) sum += querySum(p<<1|1, mid+1, r, L, R);
    return sum;
}
void update(long p, long l, long r, long L, long R, long t) {
    //printf("%lld %lld\n", l, r);
    if(max1[p] <= t) return;
    if(L <= l && r <= R && max2[p] < t) {
        //pushup(p, l, r);
        change(p, t);
        //printf("change: [%lld, %lld] sum: %lld, max2:%lld, cnt:%lld\n", l, r, sum[p], max2[p], cnt[p]);
        return;
    }
    pushdown(p);
    long mid = (l + r) >> 1;
    if(L <= mid) update(p<<1, l, mid, L, R, t);
    if(R > mid) update(p<<1|1, mid+1, r, L, R, t);
    pushup(p, l, r);
}
int main() {
    long t; scanf("%lld", &t);
    while(t--) {
        long n, m; scanf("%lld%lld", &n, &m);
        build(1, 1, n);
        for(long i=1; i<=m; i++) {
            long opt; scanf("%lld", &opt);
            long x, y; scanf("%lld%lld", &x, &y);
            if(opt == 0) {
                long t; scanf("%lld", &t);
                update(1, 1, n, x, y, t);
            }
            if(opt == 1) {
                printf("%lld\n", queryMax(1, 1, n, x, y));
            }
            if(opt == 2) {
                printf("%lld\n", querySum(1, 1, n, x, y));
            }
            /*
            for(long i=1; i<=n; i++) {
                printf("%lld ", querySum(1, 1, n, i, i));
            }
            printf("\n");
            */
        }
    }
    return 0;
}

Last modification:February 9th, 2020 at 03:40 pm
如果觉得我的文章对你有用,请随意赞赏