正題

題目鏈接:https://www.luogu.com.cn/problem/P7988

---

題目大意

給出一個長度為$n$的排列，開始有一個數字$x$，第一次詢問回答$x<a_1$（記為$LO$）或者$x>a_1$（記為$HI$），然后繼續往后問，如果$a_i$不在范圍內就不詢問，求對于每個$k\in [0,n],x=k+0.5$時回答串中$HILO$的個數。

$1\le n\le 2\times 10^5$

---

解題思路

所有數一起考慮，考慮到序列里的每個詢問$a_i$只有當數字所在的區間包含$a_i$時才會詢問，然后$a_i$會把一個區間成兩個。

那么先考慮$HI$，假設第$i$個詢問是$HI$，那么首先肯定有$x<a_i$，然后有$x>a_j(j\in [1,i?1],a_j\le a_i)$也就是還要在$a_i$目前在的區間內。

之后考慮這個$HI$的下一個能否是$LO$，首先它的下一個被詢問的位置肯定是在$[max\{a_j\},a_i]$這個范圍內的$a_k$。然后我們要的$x$就在$[a_k,a_i]$范圍內。

用$set$求出每個$a_i$對應的$max\{a_j\}$讓，然后反過來做用線段樹維護$a_k$就好了。

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

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; const int N=2e5+10; int n,a[N],l[N],s[N],w[N<<2]; set<int> pre; void Change(int x,int L,int R,int pos,int val){w[x]=val;if(L==R)return;int mid=(L+R)>>1;if(pos<=mid)Change(x*2,L,mid,pos,val);else Change(x*2+1,mid+1,R,pos,val);return; } int Ask(int x,int L,int R,int l,int r){if(L==l&&R==r)return w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return min(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r)); } int main() {scanf("%d",&n);pre.insert(0);pre.insert(n+1);for(int i=1;i<=n;i++){scanf("%d",&a[i]);l[i]=*(--pre.upper_bound(a[i]));pre.insert(a[i]);}for(int i=0;i<=n+1;i++)Change(1,0,n+1,i,n+1);for(int i=n;i>=1;i--){int k=a[Ask(1,0,n+1,l[i],a[i])];if(k){s[a[Ask(1,0,n+1,l[i],a[i])]]++;s[a[i]]--;}Change(1,0,n+1,a[i],i);}for(int i=1;i<=n;i++)s[i]+=s[i-1];for(int i=0;i<=n;i++)printf("%d\n",s[i]);return 0; }

總結

以上是生活随笔為你收集整理的P7988-[USACO21DEC] HILO G【set,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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