P10833 [COTS 2023] 下 Niz

5个月前发布

题目大意

详细题目传送门
给出 \(n\) 和 \(a_1\cdots a_n\)，求有多少个区间 \([l,r]\) 满足 \(a_l\cdots a_r\) 是 \(1\) 到 \(r-l+1\) 的排列。
\(a_i\leq n\leq10^6\)

思路

对于 \([l,r]\)，要满足

\(\max_{i=l}^r a_i=r-l+1\)
\(\forall i,j,a_i\neq a_j\)

可以猜到真正符合条件的区间应该不会很多，又因为区间一定要有且仅有一个 \(1\)，所以可以和 \(1\) 的位置考虑。先考虑一个位置 \(i\) 作为区间端点的情况，所以维护对于一个位置 \(i\) 上一个 \(1\) 和下一个的位置 \(p_i,n_i\)。发现只考虑 \((i,i+\max_{j=i}^{n_i}a_j-1)\) 和 \((i-\max_{j=p_i}^i a_j+1,i)\) 即可。首先这个肯定是对的，但是为什么不会少呢？是因为对于再前面或后面的，如果还有最大值会被前面的左端点也算上，所以不会算漏只会算重。所以现在有不超过 \(2n\) 个区间需要判断第 \(2\) 个条件。

对于这一个条件，一般做数据结构题做多了就会想到就是求 \(\mathrm{mex}(a_l\cdots a_r)\overset{?}{=} r-l+2\)。

区间 \(\mathrm{mex}\) 是不好求的，但是考虑到我们只有 \(2n\) 个区间，所以考虑离线后排序。前缀 \(\mathrm{mex}\) 相对好求，现在考虑如果把 \(a_l\) 删去带来的影响。发现就是可以在下一个 \(a_l\) 之前使用。所以也就是对于 \(m_i\) 表示 \(\mathrm{mex}\in[l,i]\)。我们可以找到 \(f_i\) 表示下一个 \(a_i\) 的位置。于是对于每一次 \(a_l\) 的删除操作，我们可以将 \(m_i\leftarrow \min(m_i,a_l),i\in[l+1,f_l-1]\)。对于一个 \([l,r]\) 判断 \(m_r\overset{?}{=}r-l+2\) 即可。

时间复杂度 \(O(n\log n)\)。

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll n,a[MAXN];
ll st[MAXN][22],lg[MAXN+5];
ll qm(ll l,ll r){
	ll len=lg[r-l+1];
	return max(st[l][len],st[r-(1<<len)+1][len]);
}
ll lst[MAXN],pre[MAXN];
struct Qj{
	ll l,r;
	bool operator<(const Qj&K)const{
		if(l==K.l){
			return r<K.r;
		}
		return l<K.l;
	}
};
vector<Qj>V,v;
struct node{
	ll u,x,tag;
	#define lc(u) (u<<1)
	#define rc(u) (u<<1|1)
}t[MAXN*4];
void push_down(ll u){
	t[lc(u)].tag=min(t[lc(u)].tag,t[u].tag);
	t[rc(u)].tag=min(t[rc(u)].tag,t[u].tag);
	t[lc(u)].x=min(t[lc(u)].x,t[u].tag);
	t[rc(u)].x=min(t[rc(u)].x,t[u].tag);
	t[u].tag=1e18;
}
ll mex[MAXN];
void build(ll u,ll l,ll r){
	t[u].tag=1e18;
	if(l==r){
		t[u].x=mex[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(lc(u),l,mid);
	build(rc(u),mid+1,r);
}
void modify(ll u,ll l,ll r,ll ql,ll qr,ll x){
	if(ql<=l&&r<=qr){
		t[u].tag=min(t[u].tag,x);
		t[u].x=min(t[u].x,x);
		return;
	}
	push_down(u);
	ll mid=(l+r)>>1;
	if(ql<=mid){
		modify(lc(u),l,mid,ql,qr,x);
	}
	if(mid+1<=qr){
		modify(rc(u),mid+1,r,ql,qr,x);
	}
}
ll nxt[MAXN],vs[MAXN];
ll query(ll u,ll l,ll r,ll x){
	if(l==r){
		return t[u].x;
	}
	push_down(u);
	ll mid=(l+r)>>1;
	if(x<=mid){
		return query(lc(u),l,mid,x);
	}
	return query(rc(u),mid+1,r,x);
}
bool vv[MAXN];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	rep(i,2,n+5){
		lg[i]=lg[i/2]+1;
	};
	rep(i,1,n){
		cin>>a[i];
		if(a[i]==1){
			lst[i]=i;
		}else{
			lst[i]=lst[i-1];
		}
		st[i][0]=a[i];
	};
	for(int i=n;i>=1;--i){
		nxt[i]=vs[a[i]];
		if(nxt[i]==0){
			nxt[i]=n+1;
		}
		vs[a[i]]=i;
		if(a[i]==1){
			pre[i]=i;
		}else{
			pre[i]=pre[i+1];
		}
	}
	rep(j,1,lg[n]){
		for(int i=1;i+(1<<j)-1<=n;++i){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	};
	rep(i,1,n){
		if(lst[i]){
			ll l=i-qm(lst[i],i)+1,r=i;
			if(l>=1){
				V.push_back({l,r});
			}
		}
		if(pre[i]){
			ll r=i+qm(i,pre[i])-1,l=i;
			if(r<=n){
				V.push_back({l,r});
			}
		}
	};
	if(V.empty()){
		cout<<0<<endl;
		return 0;
	}
	sort(V.begin(),V.end());
	v.push_back(V[0]);
	rep(i,1,ll(V.size()-1)){
		if(V[i].l==V[i-1].l&&V[i].r==V[i-1].r){
			continue;
		}
		v.push_back(V[i]);
	};
	vv[0]=true;
	rep(i,1,n){
		mex[i]=mex[i-1];
		vv[a[i]]=true;
		while(vv[mex[i]]){
			mex[i]++;
		}
	};
	build(1,1,n);
	ll tot=0,ans=0;
	rep(i,1,n){
		while(tot<ll(v.size())&&v[tot].l==i){
			ll l=v[tot].l,r=v[tot].r,val=query(1,1,n,r);
			if(val==r-l+2){
				ans++;
			}
			tot++;
		}
		modify(1,1,n,i+1,nxt[i]-1,a[i]);
	};
	cout<<ans<<endl;
	return 0;
}

来源链接：https://www.cnblogs.com/tanghg/p/18774598/solution-p10833

评分

欢迎为Ta评分