洛谷P1816 忠诚

思路

查询区间最小值，\(ST\)表/线段树板子题

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const int maxn = 2e5 + 5;
const int inf = 0x7f7f7f7f;

struct custom_hash 
{
	static uint64_t splitmix64(uint64_t x) 
    {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		return x; 
	}
	size_t operator () (uint64_t x) const 
    {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
		return splitmix64(x + FIXED_RANDOM);
	}
};

int ans[maxn][32];
int nums[maxn];
// ans[i][i] --> [i, i + (2 ^ j) - 1]

int n = 0, m = 0;

void st()
{
    for (int i = 1; i <= n; i++)
    {
        ans[i][0] = nums[i];
    }
    int t = log2(n);
    for (int j = 1; j <= t; j++)
    {
        // i + (2 ^ j) - 1 <= n
        int m = n + 1 - (1 << j);
        for (int i = 1; i <= m; i++)
        {
            ans[i][j] = std::min(ans[i][j - 1], ans[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r)
{
    int tot = r - l + 1;
    int t = log2(tot);
    // x + (2 ^ tot) - 1 = r
    return std::min(ans[l][t], ans[r + 1 - (1 << t)][t]);
}

void solve()
{
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> nums[i];
    }
    st();
    int l = 0, r = 0;
    for (int i = 1; i <= m; i++)
    {
        std::cin >> l >> r;
        std::cout << query(l, r) << " ";
    }
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    //freopen("out.txt", "w", stdout);
    int t = 1;
    //std::cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}