P1038 （C++代码）

解题思路:





注意事项:





参考代码:

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int n, m;
int A[200001];
int size;
int bmin[500];
void init();
void update(int x, int v);
int query(int left, int right);
int read();
int main()
{    
    char c; int a, b;    
    scanf("%d %d", &n, &m);    
    for (int i =0; i < n; ++i) A[i]=read();
    size=(int)sqrt(n); init(); 
    for (int i = 0; i < m; ++i) {
        a=read(); 
        b=read();        
        printf("%d ", query(a-1, b-1));
    }    
    return 0;
}
    int query(int left, int right) 
    {    
    int ret = 2147483647;    
    int lstop=(left-1)/size; 
    int rstop=(right+1)/size;    
    for (int i = lstop+1; i < rstop; ++i) 
    {ret=min(ret, bmin[i]);}    
    for (int i = left; i < (lstop+1)*size&&i<=right; ++i) 
    {ret=min(ret, A[i]);}    
    for (int i = max((rstop-1)*size+1, left); i<=right; ++i) 
    {ret=min(ret, A[i]);}    
    return ret;
}   
    void init() 
    {    
        for (int i = 0; i <= size; ++i) bmin[i]=2147483647;    
        int belong;    
        for (int i = 0; i < n; ++i) {
        belong = i/size;
        bmin[belong]=min(bmin[belong], A[i]);
    }
} 
int read() 
{     int x = 0, f = 1;  
      char ch = getchar();  
      while (ch < '0' || ch > '9') {    if (ch == '-')
      f=-1;
      ch = getchar();
  }  
      while (ch >= '0' && ch <= '9') {
      x = x * 10 + ch - '0';
      ch = getchar();
  }  
  return x * f;
}