1. 静态区间最小值查询

给定一个包含 $n$ 个整数的数组 $x$，要求处理以下形式的 $q$ 个查询：

• 区间 $[a, b]$ 上的最小值是什么？

限制：

• $1 \leqslant n, q \leqslant 2 \times 10^5$
• $1 \leqslant x_i \leqslant 10^9$
• $1 \leqslant a \leqslant b \leqslant n$

算法分析

st表板题
记 st[i][j] 表示从 $a_i$ 开始，长度为 $2^j$ 的区间的最小值。
对于一次询问：查询 $[l, r]$ 的最小值，就是 $\min(st[l][k], st[r-2^k+1])$，其中 $k$ 是满足 $2^k \geqslant r-l+1$ 的最小值。所以，每个询问的回答是 $O(1)$ 的复杂度

转移方程：

$ st[i][j] = \min(st[i][j-1], st[i+2^{j-1}][j-1]) $

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using std::cin;
using std::cout;
using std::min;

const int MX = 200005;
int x[MX], st[MX][20];

int query(int l, int r) {
    int k = log2(r-l+1);
    return min(st[l][k], st[r-(1<<k)+1][k]);
}

int main() {
    int n, q;
    cin >> n >> q;

    rep(i, n) cin >> x[i];

    rep(i, n) st[i][0] = x[i];
    for (int j = 1; j < 20; ++j) {
        for (int i = 0; i + (1<<j) < MX; ++i) {
            st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
        }
    }

    rep(qi, q) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << '\n';
    }

    return 0;
}

2. 动态区间最小值查询

给定一个包含 $n$ 个整数的数组 $x$，要求处理以下两种类型的 $q$ 个查询：

1. 将点 $k$ 处的值更改为 $u$
2. 区间 $[a, b]$ 上的最小值是什么？

限制：

• $1 \leqslant n, q \leqslant 2 \times 10^5$
• $1 \leqslant x_i, u \leqslant 10^9$
• $1 \leqslant k \leqslant n$
• $1 \leqslant a \leqslant b \leqslant n$

算法分析

st表 只能做静态查询，这里需要用到线段树

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::min;
using std::vector;
using ll = long long;

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

} 

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

const int INF = 1e9;

int op(int a, int b) { return min(a, b); }

int e() { return INF; }

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> x(n);
    rep(i, n) cin >> x[i];

    segtree<int, op, e> t(x);

    rep(qi, q) {
        int type;
        cin >> type;
        if (type == 1) {
            int k, u;
            cin >> k >> u;
            --k;
            t.set(k, u);
        }
        else {
            int a, b;
            cin >> a >> b;
            --a;
            cout << t.prod(a, b) << '\n';
        }
    }

    return 0;
}

3. 典型RMQ

给定一个包含 $n$ 个整数的数组 $a$，要求处理以下两种类型的 $q$ 个查询：

• 对区间 $[l_i, r_i]$ 上加上 $c_i$
• 查询区间 $[l_i, r_i]$ 上的最小值

限制：

• $1 \leqslant n, q \leqslant 10^5$
• $-10^{10} \leqslant a_i \leqslant 10^{10}$
• $1 \leqslant l_i \leqslant r_i \leqslant n$
• $-10000 \leqslant c_i \leqslant 10000$

算法分析

这里涉及到区间更新和区间查询，所以可以用延迟线段树

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::min;
using std::vector;
using ll = long long;

const ll INF = 1e18;

ll op(ll a, ll b) { return min(a, b); }

ll e() { return INF; }

ll mapping(ll f, ll x) { return f + x; }

ll composition(ll f, ll g) { return f + g; }

ll id() { return 0; }

int main() {
    int n;
    cin >> n;

    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    lazy_segtree<ll, op, e, ll, mapping, composition, id> t(a);

    int q;
    cin >> q;
    rep(qi, q) {
        int k, l, r, c;
        cin >> k >> l >> r >> c;
        --l;
        if (k == 1) {
            t.apply(l, r, c);
        }
        else {
            cout << t.prod(l, r) << '\n';
        }
    }

    return 0;
}

4. Replace Digits

给你一个长度为 $N$ 的字符串 $S$。一开始，$S$ 中的所有字符都是 1

你将执行 $Q$ 次询问。

• 在第 $i$ 次询问中，给你两个整数，$L_i$ 和 $R_i$，以及字符 $D_i$。然后你必须用 $D_i$ 替换区间 $[L_i, R_i]$ 之间的所有字符。

在每次查询过后，把字符串看做是一个十进制整数，并输出这个值模 $998244353$

限制：

• $1 \leqslant N, Q \leqslant 2 \times 10^5$
• $1 \leqslant L_i \leqslant R_i \leqslant N$
• $1 \leqslant D_i \leqslant 9$

算法分析

记 $\overline{A_1A_2\cdots A_N}$ 为 $S$ 的十进制整数形式
这个整数可表示为 $A_1 \times 10^{N-1} + A_2 \times 10^{N-2} + \cdots + A_N$

可以用延迟线段树处理

lazy_segtree<型, op, e, 型, mapping, 函数合成, id>

(型, op, e) 构成半群
(型, mapping, 函数合成, id) 构成映射

$1 \oplus 23 = 123$
$1 \times 10^2 + 23 = 100 + 23$

我们需要维护两个信息 (值, 位数)，记做 $(x, w)$

$(x_1, w_1) \oplus (x_2, w_2) = (x_1 \times 10^{w_2} + x_2, w_1 + w_2)$

$1234 \to 5555$
$(x, w) \to (\underbrace{11\cdots 1}_{w} \times d, w)$

$\underbrace{11\cdots 1}_{w} = \frac{10^w - 1}{9}$

这里我们需要把位数 $w$ 改成 $10^w$ 会比较方便

记 $w’ = 10^w$

$(x_1, w’_1) \oplus (x_2, w’_2) = (x_1 \times w’_2 + x_2, w’_1 * w’_2)$

C++ 代码

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;

using mint = modint998244353;
const mint inv9 = mint(1) / 9;

struct S {
    mint x, w;
    S(mint x = 0, mint w = 1): x(x), w(w) {}
};

S op(S a, S b) {
    return S(a.x * b.w + b.x, a.w * b.w);
}

S e() { return S(); }

S mapping(int f, S a) {
    if (f == 0) return a;
    return S((a.w - 1) * inv9 * f, a.w); 
} 

int compostion(int f, int g) {
    if (f == 0) return g;
    return f;
}

int id() { return 0; }

int main() {
    int n, q;
    cin >> n >> q;

    lazy_segtree<S, op, e, int, mapping, compostion, id> t(n);
    rep(i, n) t.set(i, S(1, 10));
    rep(qi, q) {
        int l, r, d;
        cin >> l >> r >> d;
        --l; 
        t.apply(l, r, d);
        S ans = t.prod(0, n);
        printf("%lld\n", ans.x.val());
    }

    return 0;
}

5. 子集和（六）

给定一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ 与一个参数 $k$。

现有 $q$ 次询问，每次询问一个区间 $[L,R]$，请你求出该区间内所有子集和中，有多少个子集和恰好是 $k$ 的倍数，答案对 $998244353$。（注意：所有子集中包含空集）

限制：

• $1 \leqslant n, q \leqslant 10^5$
• $1 \leqslant k \leqslant 20$
• $1 \leqslant a_i \leqslant 10^9$

算法分析

分治，预处理中点向左和向右的答案，左右合并即可回答跨过中点的询问。

时间复杂度 $O(nm\log n+q\log n+qm)$。

具体可以参考 Subsequence Sum Queries

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) {
    return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
    return os << a.x;
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int n, q, k;
    cin >> n >> q >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i] %= k;

    vector<int> ls(q), rs(q);
    rep(i, q) {
        cin >> ls[i] >> rs[i];
        --ls[i];
    }

    vector<int> qs(q);
    rep(i, q) qs[i] = i;
    vector d(n+1, vector<mint>(k));
    vector<mint> ans(q);
    auto f = [&](auto& f, int l, int r, const vector<int>& qs) -> void {
        if (l == r) return;
        int mid = (l+r)/2;
        rep(i, k) d[mid][i] = 0;
        d[mid][0] = 1;
        for (int i = mid-1; i >= l; --i) {
            rep(j, k) d[i][j] = d[i+1][j] + d[i+1][(j+a[i])%k];
        }
        for (int i = mid; i < r; ++i) {
            rep(j, k) d[i+1][j] = d[i][j] + d[i][(j+a[i])%k];
        }

        vector<int> ql, qr;
        for (int i : qs) {
            if (rs[i] <= mid) ql.push_back(i);
            else if (ls[i] > mid) qr.push_back(i);
            else {
                rep(j, k) {
                    ans[i] += d[ls[i]][j]*d[rs[i]][(k-j)%k];
                }
            }
        }

        f(f, l, mid, ql);
        f(f, mid+1, r, qr);
    };
    f(f, 0, n, qs);

    rep(i, q) cout << ans[i] << '\n';

    return 0;
}

6. ABC237G

对于一个排列 $P$，考虑一个仅包含 $0, 1$ 和 $2$ 的序列 $A$，$A_i$ 的定义如下：

$ P_i = \begin{cases} 0, & P_i < X\\\ 1, & P_i = X\\\ 2, & P_i > X \end{cases} $

由于两种询问是对称的，所以这里仅讨论询问 $1$，也就是升序排序操作。注意到，无论 $P_j (L \leqslant j \leqslant R)$ 的实际值是什么，排序后的排列对应的01序列，是按照 $a$ 个 $0$ 和 $b$ 个 $1$ 的顺序分布的。
这等价于以下操作：

• 找到 $S = A_L + A_{L+1} + \cdots + A_R$
• 立即将 $A_L, A_{L+1}, \cdots, A_{L+\operatorname{zero}-1}$ 更改为 $0$
• 如果区间里有 $1$，就将 $A_{L+\operatorname{zero}}$ 更改为 $1$
• 立即将 $A_{R-\operatorname{two}+1}, \cdots, A_R$ 更改为 $1$

其中 $\operatorname{zero}$ 表示区间中 $0$ 的个数，$\operatorname{two}$ 表示区间中 $2$ 的个数

可以用延迟线段树来实现。

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

P op(P a, P b) {
    return P(a.first+b.first, a.second+b.second);
}

P e() { return P(0, 0); }

P mapping(int x, P a) {
    if (x == -1) return a;
    return P(a.second*x, a.second);
}

int composition(int x, int y) {
    if (x == -1) return y;
    return x;
}

int id() { return -1; }

bool g(P a) { return a.first%2 == 0; }

int main() {
    int n, q, x;
    cin >> n >> q >> x;

    vector<int> a(n);
    rep(i, n) {
        int p;
        cin >> p;
        if (p < x) a[i] = 0;
        if (p == x) a[i] = 1;
        if (p > x) a[i] = 2;
    }

    lazy_segtree<P, op, e, int, mapping, composition, id> t(n);
    rep(i, n) t.set(i, P(a[i], 1));

    rep(qi, q) {
        int c, l, r;
        cin >> c >> l >> r;
        --l;
        int s = t.prod(l, r).first;
        int s1 = s%2;
        int s2 = s/2;
        int s0 = r-l - s1 - s2;
        if (c == 1) {
            t.apply(l, l+s0, 0);
            if (s1) t.apply(l+s0, 1);
            t.apply(r-s2, r, 2);
        }
        else {
            t.apply(l, l+s2, 2);
            if (s1) t.apply(l+s2, 1);
            t.apply(r-s0, r, 0);
        }
    }

    int ans = t.max_right<g>(0)+1;
    cout << ans << '\n';

    return 0;

}