题解 | 区间增量与区间小于计数 #

$[模板+分块+二分]$

给定长度为 $n$ 的 $a$ 数组，执行两种操作：

区间增量：将 $[l,r]$ 这个区间中的全部元素修改为其与一个数 $x$ 相加后的值，即 $\forall i \in [l,r], a_{i} \rightarrow a_{i} + x$
区间小于计数：输出下标在 $[l,r]$ 这个区间中的所有元素中小于一个特定的数 $x$ 的元素的个数，即 $\sum_{i=l}^{r}{1_{a_{i}<x}}$

如果用线段树来做，是维护区间的最大值 $Max$ 和区间的和 $sum$ ：

操作一：就是基本操作维护区间累加

操作二：使用 $Max$ 优化查询的区间个数，如果一个区间的 $Max$ 比 $x$ 小，那么直接返回 $tr[u].r - tr[u].l + 1$ ，否则继续寻找子节点

但是在很坏的情况下，操作二查询区间时， $Max$ 总是大于等于 $x$ ，那么最坏会遍历所有的叶子节点，时间复杂度从 $O(logn)$ 退化为 $O(n)$ ，导致超时

线段树的代码(一共30个测试数据，通过了29个，最后1个超时了)

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const int N = 1e5 + 10;

struct Node{
    int l, r;
    int sum, Max, add;
}tr[4 * N];

int n, q, a[N];

void push_up(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].Max = max(tr[u << 1].Max, tr[u << 1 | 1].Max); 
}

void push_down(int u){
    if(tr[u].add){
        int v = tr[u].add;
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * v;
        tr[u << 1].Max += v; 
        tr[u << 1].add += v;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * v;
        tr[u << 1 | 1].Max += v;  
        tr[u << 1 | 1].add += v;
        tr[u].add = 0;
    }
}

void build(int u, int l, int r){
    if(l == r) tr[u] = {l, r, a[l], a[l], 0};
    else{
        tr[u] = {l, r, 0, 0, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void modify(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r){
        tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
        tr[u].Max += x;
        tr[u].add += x;
        return;
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(u << 1, l, r, x);
    if(r > mid) modify(u << 1 | 1, l, r, x);
    push_up(u);
}

int query(int u, int l, int r, int x){
    if(l <= tr[u].l && tr[u].r <= r && tr[u].Max < x){
        return tr[u].r - tr[u].l + 1;
    }
    
    if(tr[u].l == tr[u].r){
        return tr[u].sum < x ? 1 : 0;
    }
    
    push_down(u);
    int res = 0;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) res += query(u << 1, l, r, x);
    if(r > mid) res += query(u << 1 | 1, l, r, x);
    return res;
}

signed main(){
    IOS;
    
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    while(q--){
        int op; cin >> op;
        if(op == 1){
            int l, r, x; cin >> l >> r >> x;
            modify(1, l, r, x);
        }
        else{
            int l, r, x; cin >> l >> r >> x;
            cout << query(1, l, r, x) << endl;
        }   
    }
    return 0;
}

正确的方法是使用分块：将区间若干个长度为 $\sqrt{n}$ 的区间来执行操作：

首先区间的长度就是为 $\sqrt{n}$

那么一共需要多少个长度为 $\sqrt{n}$ 的块的数量呢： $\lfloor \frac{n - 1}{\sqrt{n}} \rfloor +1$

block_size = (int)sqrt(n) + 1;
total_block = (n - 1) / block_size + 1;

操作一：那么 $[l,r]$ 这个区间就是由若干个块组成， $l$ 所在块的编号是 $\lfloor \frac{l - 1}{\sqrt{n}} \rfloor +1$ ， $r$ 所在块的编号是 $\lfloor \frac{r - 1}{\sqrt{n}} \rfloor +1$

如果 $idx\_l=idx\_r$ ，说明区间 $[l,r]$ 在同一个块中，那么直接暴力修改，修改的次数不会超过 $\sqrt{n}$ 次，因为这个块的长度只有 $\sqrt{n}$

如果 $idx\_l\ne idx\_r$ ，那么就将区间 $[l,r]$ 分成三个部分讨论： $l$ 所在块， $r$ 所在块以及中间 $idx\_r - idx\_l-1$ 个完完整整的块

$l$ 所在块， $r$ 所在块直接暴力修改就行；中间 $idx\_r - idx\_l-1$ 个完完整整的块如果暴力修改那就是 $O(n)$ 的做法，所以使用一个 $add[]$ 数组懒标记，记录每个块需要加的数，所以只需要从 $idx\_l + 1$ 遍历到 $idx\_r-1$ 即可，最多遍历 $\lfloor \frac{r - l + 1}{\sqrt{n}} \rfloor$ 次。

range_add(int l, int r, int x){
    int idx_l = (l - 1) / block_size + 1;
    int idx_r = (r - 1) / block_size + 1;
    if(idx_l == idx_r){
        for(int i = l; i <= r; i ++) a[i] += x;
        reset_block(idx_l);
    }
    else{
        int left_end = idx_l * block_size;
        for(int i = l; i <= left_end; i ++) a[i] += x;
        reset_block(idx_l);
        for(int i = idx_l + 1; i <= idx_r - 1; i ++) add[i] += x;
        int right_begin = (idx_r - 1) * block_size + 1;
        for(int i = right_begin; i <= r; i ++) a[i] += x;
        reset_block(idx_r);
    }
}

等下解释什么是 $reset\_block$

操作二：
如果 $idx\_l=idx\_r$ ，说明区间 $[l,r]$ 在同一个块中，那么直接暴力判断，同样不会超过 $\sqrt{n}$ 次

如果 $idx\_l\ne idx\_r$ ，那么就将区间 $[l,r]$ 分成三个部分讨论： $l$ 所在块， $r$ 所在块以及中间 $idx\_r - idx\_l-1$ 个完完整整的块

$l$ 所在块， $r$ 所在块直接暴力判断就行；中间 $idx\_r - idx\_l-1$ 个完完整整的块，如何查询每一个完整的块里面有多少个 $a_{i}$ 满足 $a_{i}+add_{idx}<x$ 呢？( $i$ 是这个块里面元素的下标， $idx$ 是这个块的编号)，使用的方法是二分的方法，如果这个块里面的元素是从小到大排序的，在这个块里面找到一个下标 $pos$ 满足 $[block\_idx\_l,pos-1]$ 里的所有 $a_{i}$ 满足 $a_{i}+add_{idx}<x$ ，而 $[pos,block\_idx\_r]$ 里所有的 $a_{i}$ 满足 $a_{i}+add_{idx}\geq x$ ，那么这个块的答案贡献就是 $pos$ 。

如何有序呢？那就是对于每次操作一的修改，都进行一次 $sort$ 排序，看 $reset\_block$ ：

void reset_block(int idx){
    block[idx].clear();
    int l = (idx - 1) * block_size + 1;
    //int r = idx * blcok_size;
    r = min(idx * block_size, n);
    for(int i = l; i <= r; i ++) block[idx].push_back(a[i]);
    sort(block[idx].begin(), block[idx].end());
}

时间复杂度为 $O(\sqrt{n}log(\sqrt{n}))$

容易忽略的一点是 $r$ 需要与 $n$ ，在最后一个形成不完整的块中的右边界是等于 $n$
总时间复杂度为 $O(n\times log(\sqrt{n})) +O(C\times \sqrt{n} \times log(\sqrt{n}))$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

const int N = 1e5 + 10;
int n, q, block_size;
int a[N], add[N];
vector<int> block[N];

void reset_block(int idx){
    block[idx].clear();
    int l = (idx - 1) * block_size + 1;
    int r = min(idx * block_size, n);
    for(int i = l; i <= r; i ++) block[idx].push_back(a[i]);
    sort(block[idx].begin(), block[idx].end());
}

void range_add(int l, int r, int x){
    int idx_l = (l - 1) / block_size + 1;
    int idx_r = (r - 1) / block_size + 1;
    if(idx_l == idx_r){
        for(int i = l; i <= r; i ++) a[i] += x;
        reset_block(idx_l);
    }
    else{
        int left_end = idx_l * block_size;
        for(int i = l; i <= left_end; i ++) a[i] += x;
        reset_block(idx_l);
        for(int i = idx_l + 1; i <= idx_r - 1; i ++) add[i] += x;
        int right_begin = (idx_r - 1) * block_size + 1;
        for(int i = right_begin; i <= r; i ++) a[i] += x;
        reset_block(idx_r);
    }
}

int range_count(int l, int r, int x){
    int res = 0;
    int idx_l = (l - 1) / block_size + 1;
    int idx_r = (r - 1) / block_size + 1;
    if(idx_l == idx_r){
        for(int i = l; i <= r; i ++){
            if(a[i] + add[idx_l] < x) res ++;
        }
    }
    else{
        int left_end = idx_l * block_size;
        for(int i = l; i <= left_end; i ++){
            if(a[i] + add[idx_l] < x) res ++;
        }
        for(int i = idx_l + 1; i <= idx_r - 1 ; i ++){
            int target = x - add[i];
            int len = lower_bound(block[i].begin(), block[i].end(), target) - block[i].begin();
            res += len;
        }
        int right_begin = (idx_r - 1) * block_size + 1;
        for(int i = right_begin; i <= r; i ++){
            if(a[i] + add[idx_r] < x) res ++;
        }
    }
    return res;
}

signed main(){
    HelloWorld;
    
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    block_size = (int)sqrt(n) + 1;
    int total_block = (n - 1) / block_size + 1;
    for(int i = 1; i <= total_block; i ++) reset_block(i);
    while(q --){
        int op; cin >> op;
        if(op == 1){
            int l, r, x; cin >> l >> r >> x;
            range_add(l, r, x);
        }
        else{
            int l, r, x; cin >> l >> r >> x;
            cout << range_count(l, r, x) << endl;
        }
    }

    return 0;
}