题意：给出一个序列 ai
问有多少对 l r 满足 将 a[l]-a[r]之间的数sort一下 a[l]-a[r] 相邻的数字差值差值不大于1
非常巧妙的线段树 比赛的时候根本没啥头绪
对于每一个L 和都可能需要修改 那么用单调栈进行维护即可 cnt的话 用last来维护
对于那个-1 因为每次加入一个R 当L=R的那对LR 是一定满足条件的 所以最小值一定是-1 也就是最小值一定满足答案 所以这个-1也就没有意义 build的时候初始化任意值都可以
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=1e5+10; int minn[N<<2],t[N<<2],n,m,col[N<<2],a[N]; ll ans; void up(int pos) { if(minn[pos<<1]==minn[pos<<1|1]) minn[pos]=minn[pos<<1],t[pos]=t[pos<<1]+t[pos<<1|1]; else if(minn[pos<<1]<minn[pos<<1|1]) minn[pos]=minn[pos<<1],t[pos]=t[pos<<1]; else minn[pos]=minn[pos<<1|1],t[pos]=t[pos<<1|1]; } void down(int pos) { if(!col[pos])return; col[pos<<1]+=col[pos]; col[pos<<1|1]+=col[pos]; minn[pos<<1]+=col[pos]; minn[pos<<1|1]+=col[pos]; col[pos]=0; } void build(int l,int r,int pos) { col[pos]=0; if(l==r){minn[pos]=0;t[pos]=1;return ;} int m=(l+r)>>1;build(l,m,pos<<1);build(m+1,r,pos<<1|1); up(pos); } void UPsum(int L,int R,int v,int l,int r,int pos) { if(L<=l&&r<=R){col[pos]+=v;minn[pos]+=v;return ;} int m=(l+r)>>1;down(pos); if(L<=m)UPsum(L,R,v,l,m,pos<<1); if(R>m)UPsum(L,R,v,m+1,r,pos<<1|1); up(pos); } stack<int>ma,mi;map<int,int>mp; int main() { int cas;cin>>cas;int kase=0; while(cas--) { mp.clear(); while(!ma.empty())ma.pop(); while(!mi.empty())mi.pop(); ans=0; scanf("%d",&n); build(1,n,1); rep(i,1,n)scanf("%d",&a[i]); int pre; rep(i,1,n) { while(!ma.empty())//维护单调递减 { int k=ma.top(); if(a[k]>=a[i])break; ma.pop(); if(ma.empty())pre=1; else pre=ma.top()+1; UPsum(pre,k,-a[k],1,n,1); } if(ma.empty())pre=1; else pre=ma.top()+1; ma.push(i); UPsum(pre,i,a[i],1,n,1); while(!mi.empty()) { int k=mi.top(); if(a[k]<=a[i])break; mi.pop(); if(mi.empty())pre=1; else pre=mi.top()+1; UPsum(pre,k,a[k],1,n,1); } if(mi.empty())pre=1; else pre=mi.top()+1; mi.push(i); UPsum(pre,i,-a[i],1,n,1); if(!mp[a[i]])pre=1; else pre=mp[a[i]]+1; UPsum(pre,i,-1,1,n,1); mp[a[i]]=i; ans+=t[1]; } printf("Case #%d: %lld ",++kase,ans); } }