HDU6315 Naive Operations(线段树 复杂度分析)

题意

sol

这题关键是注意到题目中的\(b\)是个排列

那么最终的答案最多是\(nlogn\)(调和级数)

设\(d_i\)表示\(i\)号节点还需要加\(d_i\)次才能产生\(1\)的贡献

用线段树维护每个节点里\(d_i\)的最小值，每次当\(d_i - 1= 0\)的时候往下递归即可

时间复杂度：\(o(nlog^2 n)\)

多组数据记得清空lazy标记啊qwq。。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, b[maxn];
#define ls k << 1
#define rs k << 1 | 1
struct node {
    int l, r, mn, sum, f;
}t[maxn];
void update(int k) {
    t[k].mn = min(t[ls].mn, t[rs].mn);
    t[k].sum = t[ls].sum + t[rs].sum;
}
void add(int k, int val) {
    t[k].mn -= val; t[k].f += val;
}
void pushdown(int k) {
    if(!t[k].f) return ;
    add(ls, t[k].f); add(rs, t[k].f);
    t[k].f = 0;
}
void build(int k, int ll, int rr) {
    t[k].l = ll; t[k].r = rr; t[k].sum = 0; t[k].f = 0;
    if(ll == rr) {t[k].mn = b[ll]; return ;}
    int mid = ll + rr >> 1;
    build(ls, ll, mid); build(rs, mid + 1, rr);
    update(k); 
}
void dec(int k) {
    if(t[k].mn == 0) {
        if(t[k].l == t[k].r) t[k].sum++, t[k].mn = b[t[k].l];
        else pushdown(k), dec(ls), dec(rs), update(k);
    }
}
void intervaladd(int k, int ll, int rr) {
    if(ll <= t[k].l && t[k].r <= rr) {
        add(k, 1);
        if(t[k].mn == 0) dec(k);
        return ;
    }
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(ll <= mid) intervaladd(ls, ll, rr);
    if(rr  > mid) intervaladd(rs, ll, rr);
    update(k);
}
int query(int k, int ll, int rr) {
    if(ll <= t[k].l && t[k].r <= rr) return t[k].sum;
    pushdown(k);
    int mid = t[k].l + t[k].r >> 1;
    if(rr <= mid) return query(ls, ll, rr);
    else if(ll > mid) return query(rs, ll, rr);
    else return query(ls, ll, rr) + query(rs, ll, rr);
}
main() {
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 1; i <= n; i++) b[i] = read();
        build(1, 1, n);
        while(m--) {
            char s[6]; int l, r;
            scanf("%s", s + 1); l = read(), r = read(); 
            if(s[1] == 'a') intervaladd(1, l, r);
            else printf("%d\n", query(1, l, r));            
        }
    }
}