GMOJ 6808. 【2020.10.29提高组模拟】easy
题目描述
JKLover 很喜欢数值连续的区间，现在他有一个大小为 n 的数组 a，他想知道有多少对(l,r)满足1 ≤ l ≤ r ≤ n，且把a[l], a[l + 1], . . . , a[r]排序后相邻数差的绝对值不超过 1。
题解
这题比较简单。
可以发现，当满足({Max}-{Min}+{cnt}=R-L) 时，((L,R)) 这个区间就是合法的。（cnt是这段区间中非第一次出现的数的个数）
考虑转化式子({Max}-{Min}+{cnt}+L=R) ，又因为({Max}-{Min}+{cnt}+Lge R) 所以我们只需要用线段树维护 ({Max}-{Min}+{cnt}+L) 的最小值及他的个数就行了。
考虑每次新加进来一个数的影响：
- 对(Max)和(Min)的影响，可以直接用单调栈维护。
- 对(cnt)的影响，可以用(map)维护。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define N 200000
#define ll long long
using namespace std;
int n,i,a[N],top1,top2,last[N];
ll ans;
struct node{
int min,num,lazy;
}f[N*10];
struct stack{
int val,id;
}stk1[N],stk2[N];
map<int,int> bz;
void insert(int x,int l,int r,int k){
if (l==r){
f[x].min=k;
f[x].num=1;
return;
}
int mid=(l+r)/2;
if (k<=mid) insert(x*2,l,mid,k);
else insert(x*2+1,mid+1,r,k);
if (f[x*2].min<f[x*2+1].min)
f[x].min=f[x*2].min,f[x].num=f[x*2].num;
if (f[x*2].min>f[x*2+1].min)
f[x].min=f[x*2+1].min,f[x].num=f[x*2+1].num;
if (f[x*2].min==f[x*2+1].min)
f[x].min=f[x*2].min,f[x].num=f[x*2].num+f[x*2+1].num;
}
void update(int x,int l,int r){
if (!f[x].lazy) return;
if (l<r){
f[x*2].min+=f[x].lazy;
f[x*2+1].min+=f[x].lazy;
f[x*2].lazy+=f[x].lazy;
f[x*2+1].lazy+=f[x].lazy;
}
f[x].lazy=0;
}
void change(int x,int l,int r,int l1,int r1,int p){
if (l1>r1) return;
update(x,l,r);
if (l1<=l&&r1>=r){
f[x].min+=p;
f[x].lazy+=p;
return;
}
int mid=(l+r)/2;
if (l1<=mid)
change(x*2,l,mid,l1,r1,p);
if (r1>mid)
change(x*2+1,mid+1,r,l1,r1,p);
if (f[x*2].min<f[x*2+1].min)
f[x].min=f[x*2].min,f[x].num=f[x*2].num;
if (f[x*2].min>f[x*2+1].min)
f[x].min=f[x*2+1].min,f[x].num=f[x*2+1].num;
if (f[x*2].min==f[x*2+1].min)
f[x].min=f[x*2].min,f[x].num=f[x*2].num+f[x*2+1].num;
}
int main(){
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
last[i]=bz[a[i]];
bz[a[i]]=i;
}
for (i=0;i<N*10;i++) f[i].min=1e9;
for (i=1;i<=n;i++){
insert(1,1,n,i);
change(1,1,n,i,i,a[i]);
while (top1&&stk1[top1].val<a[i]){
change(1,1,n,stk1[top1-1].id+1,stk1[top1].id,a[i]-stk1[top1].val);
top1--;
}
stk1[++top1].val=a[i];stk1[top1].id=i;
change(1,1,n,i,i,-a[i]);
while (top2&&stk2[top2].val>a[i]){
change(1,1,n,stk2[top2-1].id+1,stk2[top2].id,-(a[i]-stk2[top2].val));
top2--;
}
stk2[++top2].val=a[i];stk2[top2].id=i;
change(1,1,n,1,last[i],1);
if (f[1].min==i) ans+=f[1].num;
}
printf("%lld
",ans);
return 0;
}