King of Range

題意：

給你n個數，有m個詢問，每次詢問一個x，問有多少個區間的最大值減最小值大于x

題解：

我一開始的想法
st表實現區間最大減最小，利用二分來找這個區間范圍，復雜度O(nmlogn)，正好被卡
一個簽到題給做復雜了
我們這樣想，我們定義左端i，然后去移動右端點pos，當出現pos大于k時，此時pos位置之后的肯定與l組成的區間也大于k，然后左端點移動(i++),右端點在pos繼續走(pos不清零)，為什么？
結合代碼分析：
我們每次記錄答案都是當區間差值剛好大于k時退出，也就是pos位置肯定是最大值或者最小值(會影響差值，不然也不可能跳出while循環)。記錄完答案后左端點移動一位，此時區間是[i+1,pos],第l位沒了，但是如果此時區間差值還是大于k，說明區間最值不是第i位，pos之后的右端點都是可以的，直接累加答案，如果小于等于k，繼續右推右端點。
相當于這個差值區間是有這種性質，可以直接在前一個的基礎上繼承過來，不用重新找
這樣復雜度應該是(2n)
總復雜度是(2mn)

for(int i = 1;i <= n;i++){while(query_max(i,pos)-query_min(i,pos)<=k&&pos+1<=n){pos++;}if(query_max(i,pos)-query_min(i,pos)>k){ans+=n-pos+1;} }

官方題解是這樣做的：
因為區間端點都是單調的，所以維護兩個單調隊列，其中一個遞增序列，隊首維護最小值，一個遞減序列，隊首維護最大值，每次彈出兩個隊列中隊首考前的一個，直到極差<=k,這樣就可以在均攤O(1)的時間內求Ri了
其實就相當于維護區間最大最小值，更新左端點，在左端點右側的就要被彈出，這樣一直維護
O(nm)

題解：

st+尺取

#include<bits/stdc++.h>using namespace std; const int inf=0x3f3f3f3f; typedef long long ll; const int maxn = 1e5+50;int ffmax[maxn][20]; int ffmin[maxn][20]; int a[maxn]; int n,m,k; double lg2[maxn]; int h; int max2(int x,int y) {if(x<y)return y;return x; } int min2(int x,int y) {if(x<y)return x;return y; } void init(){memset(ffmax,0,sizeof(ffmax));memset(ffmin,0x3f,sizeof(ffmin));for(int i = 1;i <= n;i++){ffmax[i][0] = ffmin[i][0] = a[i];}for(int j = 1;j <=int(lg2[n]/lg2[2]);j++){ for(int i = 1;i+(1<<j)-1<= n;i++){ ffmax[i][j] = max2(ffmax[i][j-1],ffmax[i+(1<<(j-1))][j-1]);ffmin[i][j] = min2(ffmin[i][j-1],ffmin[i+(1<<(j-1))][j-1]);}}} int query_max(int l,int r){int s = int(lg2[r-l+1]/lg2[2]);//cout<<l<<" "<<l+(1<<s)-1<<" "<<r<<" "<<r-(1<<s)+1<<" "<<s<<endl;return max2(ffmax[l][s],ffmax[r-(1<<s)+1][s]); }int query_min(int l,int r){int s = int(lg2[r-l+1]/lg2[2]);return min2(ffmin[l][s],ffmin[r-(1<<s)+1][s]); }int main(){scanf("%d%d",&n,&m);for(int i=1;i<=100000;i++)lg2[i]=log(i); //cout<<lg2[2];h=int(lg2[n]/lg2[2]);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);init();//cout<<ffmax[3][2]<<endl;while(m--){scanf("%d",&k);ll ans = 0;int pos=0;for(int i = 1;i <= n;i++){while(query_max(i,pos)-query_min(i,pos)<=k&&pos+1<=n){pos++;}if(query_max(i,pos)-query_min(i,pos)>k){ans+=n-pos+1;}}printf("%lld\n",ans);} return 0; } /* 10 10 1 2 3 4 5 6 7 8 9 10 2 1 2 3 4 5*/

單調隊列做法：

#include<bits/stdc++.h> using namespace std; long long a[100100]; long long qmax[100100]; long long qmin[100100]; int main(){int n,m,k;scanf("%d %d",&n,&m);for(int i=1;i<=n;++i){scanf("%d",&a[i]);}while(m--){scanf("%d",&k); long long ans=0;int l=1,h1=1,t1=0,h2=1,t2=0;for(int i=1;i<=n;i++){while(h1<=t1&&a[i]>=a[qmax[t1]]) t1--; while(h2<=t2&&a[i]<=a[qmin[t2]]) t2--;qmax[++t1]=i;qmin[++t2]=i;while(h1<=t1&&h2<=t2&&a[qmax[h1]]-a[qmin[h2]]>k){ans+=n-i+1;l++;if(qmax[h1]<l) h1++;if(qmin[h2]<l) h2++;}} cout<<ans<<endl;} }

總結

以上是生活随笔為你收集整理的King of Range的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。