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

这道题需要线段树和懒标记的知识喵！

有些难，但是认真听猫猫说就可以懂了喵！

首先要明白线段树里左孩子的索引是自己的2倍，而右孩子是左孩子加1喵！

1. 首先认识咱的小伙伴们喵！

vector<ll> ma;    // 记着每个小组的最高分（最高的小可爱！）
vector<ll> mi;    // 记着每个小组的最低分（最需要加油的小可爱！）
vector<ll> a;     // 所有数字小猫的原始分数
vector<ll> lazy;  // 小本本，记着还没告诉小猫的“加分任务”

2. 建立管理团队 —— build()函数

咱是总队长（根节点，即1），手下有好多小组长（线段树节点），每个小组长管几个小猫：

build(0, n-1, 1)  // 从总队长开始，管所有小猫

如果小组长发现自己只管一个小猫（l==r），就在小本本上记下这个小猫的分数（ma[id]=a[l], mi[id]=a[l]），然后开心地回去报告~

如果管好几个小猫，就把他们分成两队，左边一队、右边一队，然后拍拍手说：“左队长去管左边！右队长去管右边！”

两队都汇报完后，总队长就抱起两个队长，看看左边和右边最大的分数和最小的分数，并记下来自己负责区域的最大最小（push_up()），这样就知道全队的最高分和最低分啦喵！

3. 向上汇报 —— push_up()

就像接力赛一样，每个小组长都会跟自己的上级说：

“报告！我管的小猫里，最高的是 88 分！最低的是 45 分！”

上级收集两个下属的报告，挑出更大的最高分，更小的最低分，再往上汇报~ 

ma[id] = max(ma[id<<1], ma[id<<1|1]);  // 挑更高的
mi[id] = min(mi[id<<1], mi[id<<1|1]);  // 挑更小的

4. 神奇的小本本 —— vector<ll> lazy 懒标记

咱有一个魔法小本本，上面可以记着“加分任务”！

如果主人说：“给所有小猫加 5 分！”

咱不用立刻跑到每个小猫面前喊，而是在小本本上写一笔（lazy[id] += add_num），然后继续玩去啦喵~ ✨

等主人问“这个小猫现在多少分”的时候，咱才翻开小本本，把任务告诉小猫（give_lazy()），这样就不用跑遍全班啦，超聪明的喵！

5. 传达任务 —— give_lazy()

当需要知道真实分数时，小组长会看看自己的小本本：

“哎呀，我本本上写着要给手下加 5 分！我得告诉左右两个副队长！”

于是他把任务交给左副队和右副队（lazy[id<<1] += lazy[id]），让他们也记下来，然后把自己本本擦干净（lazy[id]=0）。

这样任务就一层层传下去，直到每个小猫都知道自己该加多少分~

6. 加分啦，加分啦！ —— plus_tree()

现在主人说：“给第 3 号到第 5 号小朋友加 10 分！”

总队长看看自己管的所有人，发现只有一部分要加分，就拿出小本本（give_lazy），让左右队长去处理。

左队长一看：“哎呀，我管的小朋友全部要加分！太好啦！”

他就在自己小本本上写“加 10 分”（lazy[id] += add_num），然后开心地把最高分和最低分都加上 10（ma[id]+=add_num, mi[id]+=add_num），然后躺平休息，不用再往下通知啦！zzz~

右队长可能只管一部分，他就继续往下分任务...

最后，所有受影响的小组长都更新完自己的小本本，然后向上汇报（push_up），总队长就得到新的最高分和最低分啦~

这样，咱只用 O(log n) 时间就完成了大任务，是不是超厉害！

. 寻找小可爱 —— fin 查询

主人问：“第 2 号到第 6 号小朋友里，分数低于 60 分的有几个呀？”

总队长马上开始工作：

第一个剪枝（最小值剪枝）：

• 如果这个小组的最低分都 ≥ 60，那这个小组里所有人都 ≥ 60，没有低于 60 的小可爱，直接说 “0 个！” 然后跑去摸鱼啦~

第二个剪枝（最大值剪枝）：

• 如果这个小组的最高分 < 60，那这个小组里所有人都 < 60，直接说 “全组都是！” 然后报出猫数喵~

不然就要仔细找：

• 如果这个小组既有低于 60 的，也有高于 60 的，那就需要继续往下问（递归）。
• 总队长拿出小本本（give_lazy），让左右队长去数数，然后把两边的答案加起来。

这样，咱只用深入那些“混杂”的小组，那些全符合或全不符合的小组一下子就跳过去啦！

接下来是代码时间，不会写代码的猫猫会给每个写批注喵！希望小猫们都能听懂喵！

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

// 咱的“最大值本本”，记着每个小组管的小猫里的最高分
vector<ll> ma;
// 咱的“最小值本本”，记着每个小组管的小猫里的最低分
vector<ll> mi;
// 小猫们的初始成绩单
vector<ll> a;
// 魔法小本本，记着还没告诉小猫的加分任务
vector<ll> lazy;

// 向上汇报
void push_up(ll id)
{
    //id<<1其实等于id*2
    //记下左右队长更高的分
    ma[id]=max(ma[id<<1],ma[id<<1|1]);
    //记下更低的分
    mi[id]=min(mi[id<<1],mi[id<<1|1]);
}

//把魔法小本本(lazy)上的任务下发给左右小队长
void give_lazy(ll id)
{
    if(lazy[id]!=0)//有任务
    {
        //左右小队长记一笔
        lazy[id<<1]+=lazy[id];
        lazy[id<<1|1]+=lazy[id];
        //所有的值都要加一个
        ma[id<<1]+=lazy[id];
        ma[id<<1|1]+=lazy[id];
        mi[id<<1]+=lazy[id];
        mi[id<<1|1]+=lazy[id];
        //抹掉自己的喵
        lazy[id]=0;
    }
}

// 建树
void build(ll l,ll r,ll id)
{
    if(l==r)// 只管理一个小猫喵~
    {
        //最高最低都是这个小朋友
        ma[id]=a[l];
        mi[id]=a[l];
        return;
    }
    ll mid=(l+r)>>1;// 把区间分成两半
    build(l,mid,id<<1);// 左小队长去管左边的小朋友
    build(mid+1,r,id<<1|1);// 去管右边
    push_up(id);// 左右都管好了，咱来汇总喵！
}

// 区间加分
void plus_tree(ll l,ll r,ll id,ll to_l,ll to_r,ll add_num)
{
    // 如果咱管的这段完全被包含在要加分的范围里
    if(to_l<=l&&r<=to_r)
    {
        ma[id]+=add_num;
        mi[id]+=add_num;
        // 魔法小本本记一笔，不用急着告诉小猫
        lazy[id]+=add_num;
        return;
    }
    // 否则，先把咱小本本上的任务传给左右小队长
    give_lazy(id);

    ll mid=(l+r)>>1;
    // 如果左半段和要加分的范围有重叠，就告诉左小队长去
    if(mid>=to_l) plus_tree(l,mid,id<<1,to_l,to_r,add_num);
    // 如果右半段和要加分的范围有重叠，就告诉右小队长去处理
    if(mid<to_r) plus_tree(mid+1,r,id<<1|1,to_l,to_r,add_num);
    // 两个小队长都处理完了，咱重新汇总一下最高分和最低分
    push_up(id);
}

// 查询
ll fin(ll l,ll r,ll id,ll to_l,ll to_r,ll fin_num)
{
    // 如果咱管的这段完全在查询范围内，而且最低分都 ≥ fin_num
    if(l>=to_l&&r<=to_r&&mi[id]>=fin_num) return 0;
    // 一个都没有，直接跳过

    // 如果咱管的这段完全在查询范围内，而且最高分 < fin_num
    if(l>=to_l&&r<=to_r&&ma[id]<fin_num)
    {
        return r-l+1;// 全都小于，全部都要！
    }
    // 到了叶子节点，说明这个小朋友不满足条件
    if(l==r) return 0;
    // 先把小本本上的任务下发给左右小队长
    give_lazy(id);

    ll mid=(l+r)>>1;
    ll ans=0;
    if(mid>=to_l) ans+=fin(l,mid,id<<1,to_l,to_r,fin_num);
    if(mid<to_r) ans+=fin(mid+1,r,id<<1|1,to_l,to_r,fin_num);
    return ans;// 把两个小队长数出来的结果加起来，告诉主人！
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll n,q;cin >> n >> q;
    // 给咱的小本本们分配空间（每个小队长都要有地方记笔记）
    ma.resize(n<<2);
    mi.resize(n<<2);
    a.resize(n);
    lazy.resize(n<<2,0);

    for(ll i=0;i<n;i++) cin >> a[i];

// 建树！组织管理团队，从总队长（id=1）开始，管 [0, n-1] 所有小朋友
    build(0,n-1,1);

    while(q--)
    {
        int op;cin >> op;
        ll l,r,x;cin >> l >> r >> x;

        l--;r--;// 主人给的编号是从1开始的，咱要转成从0开始喵
        if(op==1)
        {
            // 加分任务！区间 [l, r] 的小朋友每人加 x 分
            plus_tree(0,n-1,1,l,r,x);
        }
        else if(op==2)
        {
            // 查询任务！看看区间 [l, r] 里有多少小朋友分数小于 x
            cout << fin(0,n-1,1,l,r,x) << '\n';
        }
    }
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/