Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 那我怕是有幸拿了最慢吧xdd 4954ms

Posted by marszed at 2017-05-19 12:33:45 on Problem 3264
```裸的RMQ 笑死了

#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 50010

int n, m;
int dp_min[maxn][20], dp_max[maxn][20];

void rmq_init()
{
for (int i = 1; i <= n; i++)
{
cin >> dp_min[i][0];
dp_max[i][0] = dp_min[i][0];
}
for (int j = 1; 1 << j <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]);
}
}

int query(int l, int r)
{
int len = 0;
while (l + (1 << (len + 1)) - 1 <= r) len++;
return max(dp_max[l][len], dp_max[r - (1 << len) + 1][len]) - min(dp_min[l][len], dp_min[r - (1 << len) + 1][len]);
}

int main()
{

ios::sync_with_stdio(false);

cin >> n >> m;
rmq_init();
int l, r;
for (int i = 1; i <= m; i++)
{
cin >> l >> r;
cout << query(l, r) << endl;
}
return 0;
}

```

Followed by: