首先先可以发现对于限制 \(\min_{i \in [l,r]} a_i \leq r-l+1\),的任意一个右端点,能贡献的 \(l\) 肯定是一个可以确定的前缀,这一部分可以用单调队列提前预处理出每个前缀记为 \(pre_i\)。同理对于任意一个左端点也对应可以转移到一个确定的后缀,也预处理出来记为 \(nxt_i\)。
到这里可以暴力 \(O(n^2)\text{dp}\),也可以做出特殊性质。
然后对于最大值的限制,考虑仿照 \(\text{cdq}\) 分治优化 \(dp\),找到分界点为当前区间最大值的位置,这样对于左边对右边的区间的最大值就确定了,然后发现有两种方案:
- 枚举左端点 \(i \in [l,mid]\),发现他能贡献到的右端点肯定是连续的,可以用预处理出的值算出,然后树状数组计算,这样会多一个 \(\log\)。但是发现是先修改再查询,所以可以差分。
- 枚举右端点 \(i \in [mid,r]\),发现可以贡献到他的左端点也是可以直接算出,维护左边的前缀和计算就行了。
由于最大值的分布位置不一定均匀,为了防止复杂度退化到 \(O(n^2)\),考虑两种方案那边区间小选对应方案计算。然后差分数组和前缀和数组可以用一个指针,时刻维护出已经计算完贡献的前缀的信息就可以做到复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
const int lgn=25;
const int mod=1e9+7;
int a[maxn],pre[maxn],nxt[maxn],sum[maxn],sum2[maxn];
int que[maxn],head,tail,dp[maxn],now=1;
int st[maxn][lgn],lg[maxn];
inline void init(int n){
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(a[st[i][j-1]]>=a[st[i+(1<<(j-1))][j-1]]) st[i][j]=st[i][j-1];
else st[i][j]=st[i+(1<<(j-1))][j-1];
}
}
}
int query(int l,int r){
int k=lg[r-l+1];
if(a[st[l][k]]>=a[st[r-(1<<k)+1][k]]) return st[l][k];
return st[r-(1<<k)+1][k];
}
void cdq(int l,int r){
if(l>=r){
if(now<=l){
for(int i=now;i<l;i++){
sum[i]=(sum[i-1]+sum[i])%mod;
dp[i]=(dp[i]+sum[i])%mod;
sum2[i]=(sum2[i-1]+dp[i])%mod;
}
now=l;
}
if(l==r&&a[l]==1) dp[l]=(dp[l]+dp[l-1])%mod;
if(now<=r){
for(int i=now;i<=r;i++){
sum[i]=(sum[i-1]+sum[i])%mod;
// printf("%d %d %d : %d\n",i,sum[i],sum2[i],dp[i]);
dp[i]=(dp[i]+sum[i])%mod;
sum2[i]=(sum2[i-1]+dp[i])%mod;
// printf("%d %d %d : %d\n",i,sum[i],sum2[i],dp[i]);
}
now=r+1;
}
return;
}
int mid=query(l,r);
cdq(l,mid-1);
// for(int i=mid;i<=r;i++) sum[i]=sum2[i]=0;
if(mid-l<r-mid+1){
for(int i=l-1;i<mid;i++){
int tmp=min(r,i+a[mid]);
if(tmp<mid) continue;
if(max(mid,nxt[i+1])<=tmp){
// printf("kk%d : %d %d\n",i,max(mid,nxt[i+1]),tmp);
sum[max(mid,nxt[i+1])]=(sum[max(mid,nxt[i+1])]+dp[i])%mod;
sum[tmp+1]=(sum[tmp+1]-dp[i]+mod)%mod;
}
}
}else{
for(int i=mid;i<=r;i++){
int tmp=max(l,i-a[mid]+1);
if(tmp>mid) continue;
if(min(pre[i],mid)>=tmp){
dp[i]=(dp[i]+sum2[min(pre[i],mid)-1])%mod;
if(tmp>=2) dp[i]=(dp[i]-sum2[tmp-2]+mod)%mod;
}
}
}
cdq(mid+1,r);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
st[i][0]=i;
}
init(n);
int mn=0;
head=1;
tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&a[que[tail]]>=a[i]) tail--;
que[++tail]=i;
while(head<=tail&&i-a[que[head]]+1>que[head]){
mn=max(mn,que[head]);
head++;
}
pre[i]=max(mn,i-a[que[head]]+1);
}
head=1;
tail=0;
mn=n+1;
for(int i=n;i>=1;i--){
while(head<=tail&&a[que[tail]]>=a[i]) tail--;
que[++tail]=i;
while(head<=tail&&i+a[que[head]]-1<que[head]){
mn=min(mn,que[head]);
head++;
}
nxt[i]=min(mn,i+a[que[head]]-1);
}
// for(int i=1;i<=n;i++) printf("%d : %d %d\n",i,pre[i],nxt[i]);
// exit(0);
sum2[0]=dp[0]=1;
cdq(1,n);
printf("%d\n",dp[n]);
return 0;
}
标签:head,端点,int,T3,tail,maxn,dp,3.30,模拟
From: https://www.cnblogs.com/activeO/p/18110995