題意：判斷一個區(qū)間[l,r]的數(shù)是否是1到(r-l+1)。

解題思路：首先判斷該區(qū)間內(nèi)的和是否是n*(1+n)/2，這里可以用前綴和判斷。

接下來是要判斷該區(qū)間內(nèi)無重復(fù)的數(shù)：

pos[i]表示第i個數(shù)左邊與它相同的且最靠近它的位置。如果尋找的[l,r]區(qū)間內(nèi)最大的pos[i]大于了l，說明區(qū)間有重復(fù)的數(shù)。這里可以用rmq維護，但rmq超內(nèi)存。正解是線段樹。

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std;const int maxn = 1000005; int n,m,sum[maxn],tmp[maxn]; int pos[maxn],dp[maxn][20];void init() {for(int i = 1; i <= n; i++)dp[i][0] = pos[i];for(int j = 1; j <= 20; j++)for(int i = 1; i + (1 << j) - 1 <= n; j++)dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); }int rmq(int l,int r) {int k = (int)(log(r - l + 1.0) / log(2.0));return max(dp[l][k],dp[r-(1<<k)+1][k]); }int main() {int l,r;while(scanf("%d%d",&n,&m)!=EOF){memset(tmp,0,sizeof(tmp));for(int i = 1; i <= n; i++){scanf("%d",&sum[i]);pos[i] = tmp[sum[i]];tmp[sum[i]] = i;}for(int i = 2; i <= n; i++)sum[i] += sum[i-1];init();while(m--){scanf("%d%d",&l,&r);if((1 + (r - l + 1)) * (r - l + 1) / 2 != sum[r] - sum[l-1]){printf("NO\n");continue;}if(rmq(l,r) < l)printf("YES\n");else printf("NO\n");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 5172(RMQ+前缀和)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。