1004: Zeratul的完美區間Time Limit:5000/3000 MS (java/Others)   Memory Limit:294912/262144 KB (Java/Others)Total Submissions:93   Accepted:17[Submit][Status][Discuss]

Description

如果一個長度為k區間中的數排序后正好可以形成n+1,n+2,…,n+k的形式，那么我們稱這個區間叫完美區間。

現在Zeratul給出了一個1∼n的一個全排列，并給出m組[a,b]，詢問區間[a,b]是否是完美區間。其中a,b表示區間的起止下標。(a≤b)

比如1∼6的一個全排列{1，4，2，3，6，5}中，[1,4]和[2,6]都是完美區間，[2,5]不是完美區間。

Input

輸入僅一組數據：

第一行包括一個整數n(1≤n≤100000)

第二行包括n個整數a1,a2,…,an. (1≤ai≤n, 對任意i≠j，都有ai≠aj)

第三行包括一個整數m(1≤m≤100000)

接下來m行，每行包括兩個整數a,b(1≤a≤b≤n),表示一組詢問。

Output

對于每組詢問[a,b]，如果[a,b]是完美區間，輸出YES，否則輸出NO。

Sample Input

61 4 2 3 6 531 42 62 5
Sample Output
YESYESNO點擊跳轉到原題ST表簡述：    ST表即sparse table，也叫稀疏表。其特點是在海量數據中可以在O(1)的復雜度下求出任意區間的最值，前提是進行數據預處理，復雜度為O(nlogn)。      預處理：主要是用到了二分及動態規劃的思想。以最大值為例，最小值類似。建立一個動態規劃數組dp[i][j],表示區間i->i+2^j-1的最大值,這樣就可以表示所有區間的最值了，其中定義dp[i][0]表示元素本身。推出動態規劃方程為：dp[i][j] = max(dp[i][j-1],dp[i+2^j][j-1]),思維敏捷的讀者就可以發現，這里其實就是將2^j-1長的區間二分為兩個2^(j-1)區間。這樣就可以由動態規劃方程完成初始化，復雜度顯然為O(nlogn)。      查詢：從預處理的思想得出查詢的方法，對于任意的區間[a,b]，int k = log2(b-a+1)，這樣將區間劃分為[a,a+2^k-1],[b-2^k+1,b]，聰明的讀者一定會發現，這樣區間會有覆蓋的部分。事實的確如此，但是我們需要的求解最值，所以對我們求解沒有影響。這樣就可以得到：[a,b]最大值為max(dp[a][k], dp[b-2^k+1][k])。      小結：ST表是一種對數據處理的極好方式，通過對數據進行預處理，使得查詢任意區間最值變為O(1)，啟發我們對于一些數據詢問問題中，對數據進行合理的預處理有時候是很有效的。
分析：    不難想到，對于任意的給定區間[a,b]，只需要去驗證區間內的最大值與最小值之差與區間長度是否相等即可（由于任意的元素都不相等），估算復雜度：一般的求解最值方法復雜度為O(n),共有n組查詢，總復雜度為O(n^2)=1e10，可見一般的方法不能解決，所以想到采用ST表，總的復雜度為O(nlongn)+O(n)=O(nlongn)<2*1e6,可以AC。下面是AC代碼：
#include<iostream>#include<cstring>#include<math.h>#include<stdlib.h>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;const int Max = 1e5+5;int dp_max[Max][33];int dp_min[Max][33];int main( ){    //freopen("input.txt","r",stdin);    int n;    scanf("%d", &n);    for(int i=1; i<=n; i++)    {        scanf("%d", &dp_max[i][0]);        dp_min[i][0] = dp_max[i][0];    }    //初始化（注意按照列優先的規則進行初始化）,復雜度O(nlogn)    int k = (int)log2(n);    for(int j=1; j<=k; j++)        for(int i=1; i<=n; i++)            if(i+(1<<(j-1)) <= n)//注意i+2^(j-1)可能大于n            {                dp_max[i][j] = max(dp_max[i][j-1], dp_max[i+(1<<(j-1))][j-1]);                dp_min[i][j] = min(dp_min[i][j-1], dp_min[i+(1<<(j-1))][j-1]);            }    int m;    scanf("%d", &m);    while(m--)    {        int a,b;        scanf("%d%d", &a,&b);        //通過稀疏表進行查詢任意區間的最值，復雜度O(1)        int length = (int)log2(b-a+1);        int high = max(dp_max[a][length], dp_max[b-(1<<length)+1][length]);        int low = min(dp_min[a][length], dp_min[b-(1<<length)+1][length]);        if(high-low == b-a)            PRintf("YES/n");        else            printf("NO/n");    }   return 0;}文中如有錯誤，還請各位讀者及時糾正，在下不勝感激，