P7988-[USACO21DEC] HILO G【set,线段树】

正题

题目链接: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$，首先它的下一个被询问的位置肯定是在 [   m a x { a j } , a i   ] [\ max\{a_j\},a_i\ ] [ max{aj​},ai​ ]这个范围内的$a_k$。然后我们要的$x$就在$[a_k,a_i]$范围内。

用$set$求出每个$a_i$对应的 m a x { a j } max\{a_j\} max{aj​}让，然后反过来做用线段树维护$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;
}