无趣的RMQ-ST 模板。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
const int maxn=50001; int n, q, x, y; int a[maxn], max_r[maxn][16], min_r[maxn][16]; void pre() { for(int i=1; i<=n; i++) min_r[i][0]=max_r[i][0]; int t=log(n)/log(2); for(int j=1; j<=t; j++) for(int i=1; i+(1 << (j-1))-1<=n; i++) { max_r[i][j]=max(max_r[i][j-1], max_r[i+(1 << (j-1))][j-1]); min_r[i][j]=min(min_r[i][j-1], min_r[i+(1 << (j-1))][j-1]); } } int rmq(int l, int r) { int k=int(log((double)(r-l+1))/log(2.0)); int a1=max(max_r[l][k], max_r[r-(1 << k)+1][k]); int a2=min(min_r[l][k], min_r[r-(1 << k)+1][k]); printf("%d%d\n", a1, a2); } int main() { scanf("%d%d", &n, &q); for(int i=1; i<=n; i++) scanf("%d", &a[i]); pre(); while(q--) { scanf("%d%d", &x, &y); rmq(x, y); } return 0; } |