周赛Problem 1025: Hkhv love spent money（RMQ）-白红宇

周赛Problem 1025: Hkhv love spent money（RMQ）

阅读量：5346 次

发布时间：2019-06-15

本文共 1398 字，大约阅读时间需要 4 分钟。

Problem 1025: Hkhv love spent money

Time Limits: 1000 MS Memory Limits: 65536 KB

64-bit interger IO format: %lld Java class name: Main

Description

Hkhv喜欢花钱，尤其是给他girl friend花钱。现在有n天，每天他花了ai元(i在1到n之间)。

他现在想知道第i天到第j天之间哪天花费的钱最少，输出最少的钱。

Input

输入一个数t，表示有t(t <= 10)组数据。

每组数据输入一个数n(1 <= n <= 10000)和q(1 <= q <= 10000)，接下来一行输入n个数ai(0 <= a[i] <= 10^9)，ai表示第i天花费的钱。

接下来q个查询，每个查询输入i和j，表示第i天和第j天。

Output

对于每个查询输出第i天到第j天之间哪天花费的钱最少，输出最少的钱。

Sample Input

14 22 1 3 53 41 4

Output for Sample Input

Hint

DP思想来对多个长度为2^k区间内的最小/最大值。有待于好好理解一番。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #define INF 0x3f3f3f3f#define MM(x) memset(x,0,sizeof(x))using namespace std;typedef long long LL;const int N=10010; int minm[N][20];int pos[N];int n;inline void RMQ_init(int n){ for(int i=1; i<=N; i++) minm[i][0]=pos[i]; for(int j=1; (1<
                  
                   <=n; j++) for(int i=1;i+(1<
                   
                    <=n;i++) minm[i][j]=min(minm[i][j-1],minm[i+(1<<(j-1))][j-1]);}int main(void){ int tcase,i,j,l,r,q; scanf("%d",&tcase); while (tcase--) { scanf("%d%d",&n,&q); for (i=1; i<=n; i++) { scanf("%d",&pos[i]); } RMQ_init(N); for (i=1; i<=q; i++) { scanf("%d%d",&l,&r); int k=log2(r-l+1); int ans=min(minm[l][k],minm[r-(1<