题目链接

题目描述

老管家是一个聪明能干的人。他为财主工作了整整 $10$ 年，财主为了让自已账目更加清楚。要求管家每天记 $k$ 次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按 $1,2,3 \cdots$ 编号，然后不定时的问管家问题，问题是这样的：在 $a$ 到 $b$ 号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入格式

输入中第一行有两个数 $m,n$ 表示有 $m$($m \le 10^5$)笔账,$n$ 表示有 $n$ 个问题，$n \le 10^5$。

第二行为 $m$ 个数,分别是账目的钱数

后面 $n$ 行分别是 $n$ 个问题,每行有 $2$ 个数字说明开始结束的账目编号。

输出格式

输出文件中为每个问题的答案。

题解

当然可以用线段树来维护，但是这里选择树状数组会更加精炼

当然，树状数组也有其弊端，对于没有被包含的单个节点，就需要一个一个比较了……这会大大降低效率！

upd: ST 表（这个会快很多，重点在于没有修改）

代码

树状数组

cpp

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int t[N], a[N];
int x, y;
void add(int x, int k) {
    while (x <= n) {
        if (t[x] > k)
            t[x] = k;
        else
            return;
        x += x & -x;
    }
}
int getmin(int x, int y) {
    int r = 2147483647;
    while (y >= x) {
        if (y - (y & -y) > x) {
            r = min(r, t[y]);
            y -= y & -y;
        } else {
            r = min(r, a[y]);
            --y;
        }
    }
    return r;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    memset(t, 127, sizeof(t));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        cout << getmin(x, y) << ' ';
    }
    return 0;
}

线段树

cpp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n, m, op, x, y, k;
ll a[N];
struct node {
    ll min_p, sum, tag;
} T[N << 2];
inline ll min(ll a, ll b) { return a > b ? b : a; }
inline int ls(ll p) { return p << 1; }
inline int rs(ll p) { return p << 1 | 1; }
inline void push_up(ll p) {
    T[p].sum = T[ls(p)].sum + T[rs(p)].sum;
    T[p].min_p = min(T[ls(p)].min_p, T[rs(p)].min_p);
}
void build(ll p, ll l, ll r) {
    T[p].tag = 0;
    T[p].min_p = 0x3f3f3f3f;
    if (l == r) {
        T[p].min_p = T[p].sum = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
inline void push_down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    T[ls(p)].sum += T[p].tag * (r - l + 1);
    T[ls(p)].tag += T[p].tag;
    T[rs(p)].sum += T[p].tag * (r - l + 1);
    T[rs(p)].tag += T[p].tag;
    T[p].tag = 0;
}
ll query_min(ll q_x, ll q_y, ll l, ll r, ll p) {
    if (q_x <= l && r <= q_y)
        return T[p].min_p;
    ll mid = (l + r) >> 1, resa = 0x3f3f3f3f, resb = 0x3f3f3f3f;
    push_down(p, l, r);
    if (q_x <= mid)
        resa = query_min(q_x, q_y, l, mid, ls(p));
    if (q_y > mid)
        resb = query_min(q_x, q_y, mid + 1, r, rs(p));
    return min(resa, resb);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        cout << query_min(x, y, 1, n, 1) << " ";
    }
    return 0;
}

ST 表

cpp

#include <bits/stdc++.h>
using namespace std;
int lg2(int n, int result = 0) {
    if (n & 0xffff0000) result += 16, n >>= 16;
    if (n & 0x0000ff00) result += 8, n >>= 8;
    if (n & 0x000000f0) result += 4, n >>= 4;
    if (n & 0x0000000c) result += 2, n >>= 2;
    if (n & 0x00000002) result += 1, n >>= 1;
    return result;
}
const int N = 1e6 + 5;
int n, m, f[25][N], l, r;
inline char getcha() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    char ch = getcha();
    int ret = 0, f = 1;
    while (!isdigit(ch)) {
        if (ch == '-') f = -f;
        ch = getcha();
    }
    while (isdigit(ch)) {
        ret = (ret << 1) + (ret << 3) + ch - '0';
        ch = getcha();
    }
    return ret * f;
}
char pbuf[100000], *pp = pbuf;
void push(const char c) {
    if (pp - pbuf == 100000)
        fwrite(pbuf, 1, 100000, stdout), pp = pbuf;
    *pp++ = c;
}
void write(int x) {
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
    push(' ');
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) f[0][i] = read();
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
    for (int i = 1; i <= m; i++) {
        l = read(), r = read();
        int s = lg2(r - l + 1);
        write(min(f[s][l], f[s][r - (1 << s) + 1]));
    }
    fwrite(pbuf, 1, pp - pbuf, stdout);
    pp = pbuf;
    return 0;
}

注意

1. 要初始化为最大值