UOJ #225.排队-白红宇

UOJ #225.排队

阅读量：5301 次

发布时间：2019-06-14

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

【题目描述】：每天，农夫约翰的N头奶牛总是按同一顺序排好队，有一天，约翰决定让一些牛玩一场飞盘游戏（Ultimate Frisbee），他决定在队列里选择一群位置连续的奶牛进行比赛，为了避免比赛结果过于悬殊，要求挑出的奶牛身高不要相差太大。约翰准备了Q组奶牛选择，并告诉你所有奶牛的身高Hi。他想知道每组里最高的奶牛和最矮的奶牛身高差是多少。注意：在最大的数据上，输入输出将占据大部分时间。【输入描述】：第一行，两个用空格隔开的整数N和Q。第2到第N+1行，每行一个整数，第i+1行表示第i头奶牛的身高Hi第N+2到第N+Q+1行，每行两个用空格隔开的整数A和B，表示选择从A到B的所有牛（1<=A<=B<=N）【输出描述】：共Q行，每行一个整数，代表每个询问的答案。【样例输入】：6 31734251 54 62 2【样例输出】：630【时间限制、数据范围及描述】：时间：1s 空间：128M1<=N<=50,000; 1<=Q<=200,000; 1<=Hi<=10^6本题用RMQ求出区间最大和区间最小,然后将二者相减即可。Code:#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1000005,M=25;int n,q,a[N],f1[N][M],f2[N][M];int query1(int L,int R){ int k; k=int(log(R-L+1)/log(2)); return max(f1[L][k],f1[R+1-(1<