牛牛的凑数游戏

给一个 T3 的不用主席树的简易做法。

建线段树，对每个点维护一个值 和一个有序 pair 列表，表示这个点对应的区间做完合并后，可以覆盖的区间为 ，且剩余的待合并的数为 。

这个列表的意义是：如果 增大到某个不小于 的 ，那么新的可覆盖区间会变成 ，但这时仍然有 。

对于 的定义类似：如果 增大到某个不小于 的 ，那么新的可覆盖区间会变成 ，但这时仍然有 。对于 之类的可以类似定义下去。

这样定义之后，容易发现一个列表的长度至多是 ，因为 是两倍两倍增长的。而合并两个点的信息也只需要归并两个列表的信息。因此总的时间复杂度为 。

使用这个框架的另一个好处在于其可以方便地处理在线的询问，或者进行修改，如 2019 ICPC 徐州区域赛 H 题。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int a[100005], siz;
ll seg1[263000] = {0}, tmpv;
vector<intpair > seg2[263000], tmp, tmp2;
ll mmerge(ll xx1, ll xx2, vector<intpair >& v1, vector<intpair >& v2, vector<intpair >& res){
    ll newx = xx1 + xx2 - 1;
    int siz1 = v1.size(), siz2 = v2.size();
    int lp = 0, rp = 0;
    while (lp < siz1 || rp < siz2){
        if (lp == siz1 || (rp < siz2 && v2[rp].first < v1[lp].first)){
            // rp
            if (v2[rp].first <= newx) newx += v2[rp].first + v2[rp].second;
            else {
                if (res.empty() || v2[rp].first > 2ll * res.back().first + res.back().second)
                    res.push_back(v2[rp]);
                else res.back().second += v2[rp].first + v2[rp].second;
            }
            ++rp;
        } else {
            if (v1[lp].first <= newx) newx += v1[lp].first + v1[lp].second;
            else {
                if (res.empty() || v1[lp].first > 2ll * res.back().first + res.back().second)
                    res.push_back(v1[lp]);
                else res.back().second += v1[lp].first + v1[lp].second;
            }
            ++lp;
        }
    }
    return newx;
}
void init(){
    n = read(), m = read();
    REP(i, 1, n) a[i] = read();
    for (siz = 1; siz < n; siz <<= 1) ;
    REP(i, 1, n) {
        if (a[i] == 1) seg1[i + siz - 1] = 2;
        else seg1[i + siz - 1] = 1, seg2[i + siz - 1].push_back(make_pair(a[i], 0));
    }
    REP(i, siz + n, siz + siz - 1) seg1[i] = 1;
    REPR(i, siz - 1, 1){
        seg1[i] = mmerge(seg1[i << 1], seg1[i << 1 | 1], seg2[i << 1], seg2[i << 1 | 1], 
            seg2[i]);
    }
}
int _a, _b;
void query(int id, int l, int r){
    if (l > _b || r < _a) return ;
    if (l >= _a && r <= _b){
        tmp2.clear();
        tmpv = mmerge(tmpv, seg1[id], tmp, seg2[id], tmp2);
        tmp.clear();
        for (const auto& p: tmp2) tmp.push_back(p);
        return ;
    }
    int mid = (l + r) >> 1;
    query(id << 1, l, mid);
    query(id << 1 | 1, mid + 1, r);
}
void solve(){
    while (m--){
        _a = read(), _b = read();
        tmpv = 1, tmp.clear();
        query(1, 1, siz);
        printf("%lld\n", tmpv);
    }
}
int main(){
    init();
    solve();
    return 0;
}