正題

題目鏈接:https://ac.nowcoder.com/acm/contest/7329/E

---

題目大意

給出一個$n$的排列，求有多少個區(qū)間$[l,r]$使得最大值是$r$，最小值是$l$。

---

解題思路

首先對于一個位置的值作為左端點和右端點都有一段合法區(qū)間（到左邊第一個比他小的和右邊第一個比他大的，當(dāng)右端點時同理）。可以用樹狀數(shù)組預(yù)處理每個的合法區(qū)間

然后對于兩個點各作為左右端點需要滿足左端點在右端點的合法區(qū)間內(nèi)，右端點在左端點的合法區(qū)間內(nèi)。

那么有算法就是對于每個右端點我們在他合法區(qū)間的左邊壓入，右邊彈出然后指針掃描作為左端點的值進行區(qū)間查詢即可。

時間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lowbit(x) (x&-x) using namespace std; const int N=1e6+10; int n,p[N],la[N],ra[N],lp[N],rp[N],num[N]; vector<int> ql[N],qr[N]; long long ans; struct Tree_Array{int t[N];void Change(int x,int val){while(x<=n){t[x]=max(val,t[x]);x+=lowbit(x);}return;}int Ask(int x){int ans=0;while(x){ans=max(t[x],ans);x-=lowbit(x);}return ans;} }Ta,Tp; struct tTree_Array{int t[N];void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return;}int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;} }T; bool cmp(int x,int y) {return p[x]<p[y];} int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&p[i]),num[i]=i;for(int i=1;i<=n;i++){la[i]=Ta.Ask(p[i]);ra[i]=Tp.Ask(n-p[i]+1);Ta.Change(p[i],i);Tp.Change(n-p[i]+1,i);}memset(Ta.t,0,sizeof(Ta.t));memset(Tp.t,0,sizeof(Tp.t));for(int i=n;i>=1;i--){lp[i]=n-Ta.Ask(p[i])+1;rp[i]=n-Tp.Ask(n-p[i]+1)+1;Ta.Change(p[i],n-i+1);Tp.Change(n-p[i]+1,n-i+1);}for(int i=1;i<=n;i++)if(p[i]>=i&&ra[i]<p[i]&&p[i]<rp[i]){ql[ra[i]].push_back(i);qr[rp[i]].push_back(i);}sort(num+1,num+1+n,cmp);for(int i=0;i<=n;i++){int x=num[i];for(int j=0;j<qr[i].size();j++)T.Change(p[qr[i][j]],-1);if(p[x]<=x&&la[x]<p[x]&&p[x]<lp[x])ans+=T.Ask(lp[x]-1)-T.Ask(x-1);for(int j=0;j<ql[i].size();j++)T.Change(p[ql[i][j]],1);}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛69E-子串【树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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