AcWing 1270. 数列区间最大值——树状数组写法
原题链接
简单
作者:
春江花月夜ovo
,
2024-04-12 15:54:08
,
所有人可见
,
阅读 19
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int tr[N];
int a[N];
int n, m;
int lowbit(int x)
{
return x & -x;
}
void update(int u, int x)
{
for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], x);
}
int query(int l, int r)
{
int ans = (-(1 << 31) + 1);
for (; r >= l && r - lowbit(r) >= r; r -= lowbit(r))
ans = max(ans, tr[r]);
while (r >= l)
{
ans = max(ans, a[r]);
r --;
for (; r >= l && r - lowbit(r) >= l; r -= lowbit(r))
ans = max(ans, tr[r]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < N; i ++) tr[i] = (-(1 << 31) + 1);
for (int i = 1; i <= n; i ++) cin >> a[i], update(i, a[i]);
while (m --)
{
int l, r;
cin >> l >> r;
cout << query(l, r) << "\n";
}
return 0;
}