题目大意
定义一个整数集合 S S S是好的,当且仅当 S S S中所有值域连续段的长度都不超过 k k k。
换句话说, S S S是好的,当且仅当不存在一对整数 l , r l,r l,r,满足 [ l , r ] [l,r] [l,r]中的整数都在 S S S中出现且 r − l + 1 > k r-l+1>k r−l+1>k。
给定一个长度为 n n n的序列 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an,问该序列有多少个子区间满足这个区间的数的集合是好的。
1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i , k ≤ n 1\leq n\leq 2\times 10^5,1\leq a_i,k\leq n 1≤n≤2×105,1≤ai,k≤n
题解
首先,我们可以发现,如果区间 [ l , r ] [l,r] [l,r]是好的,那所有被区间 [ l , r ] [l,r] [l,r],包含的区间也是好的因为这样最长值域连续段长度不会变大,一定也满足条件。
我们可以用扫描线,从小到大枚举右端点,然后维护最小的 l l l,满足区间 [ l , r ] [l,r] [l,r]是好的。
那哦们怎么判断一个区间是不是好的呢?我们用线段树来维护 a i a_i ai的值域,线段树上的每个节点维护区间中最长值域连续段的长度,以及包含左、右端点的极长连续段长度。判断当前区间是否是好的,只需要看根节点维护区间中最长值域连续段的长度是否超过 k k k即可。如果超过了,则将 a l a_l al在线段树上删去。 r r r每往右一个位置,就将 a r a_r ar在线段树上加上。也就是说,线段树只需要支持单点修改。
对于每个 r r r和其对应的最小的 l l l, a n s + = r − l + 1 ans+=r-l+1 ans+=r−l+1。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=200000;
int n,k,a[N+5],ct[4*N+5],mx[4*N+5],lx[4*N+5],rx[4*N+5];
long long ans=0;
void ch(int k,int l,int r,int x,int v){
if(l==r&&l==x){
ct[k]+=v;
mx[k]=lx[k]=rx[k]=(ct[k]>0);
return;
}
int mid=l+r>>1;
if(x<=mid) ch(lc,l,mid,x,v);
else ch(rc,mid+1,r,x,v);
if(lx[lc]<mid-l+1) lx[k]=lx[lc];
else lx[k]=lx[lc]+lx[rc];
if(rx[rc]<r-mid) rx[k]=rx[rc];
else rx[k]=rx[rc]+rx[lc];
mx[k]=max(rx[lc]+lx[rc],max(mx[lc],mx[rc]));
}
int main()
{
// freopen("set.in","r",stdin);
// freopen("set.out","w",stdout);
// scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1,j=1;i<=n;i++){
ch(1,1,n,a[i],1);
while(mx[1]>k){
ch(1,1,n,a[j],-1);++j;
}
ans+=i-j+1;
}
printf("%lld",ans);
return 0;
}