题意

给定一个序列，定义连续区间为区间的数排序后，任意两个相邻的数之差不超过1。

分析

假设区间最大值为\(max\),最小值为\(min\)，不同数个数为\(cnt\)，那么问题转化为求满足\(max-min-cnt==1\)的区间个数。
统计满足条件的区间个数可以考虑用线段树，主要有三个步骤：
- 枚举右端点\(R\)
- 线段树维护当前所有左端点，即每个叶子节点\((i,i)\)，表示序列区间\([i,R]\)
- 统计答案，以\(R\)为右端点的所有区间，即线段树根节点\((1,n)\)
更新区间分为两部分
- 第一部分是\(cnt\)，也相当于也就是要更新当前\(R\)，前面有多少个区间\([i,R]\)以\(a[R]\)作为一个新的不同的数字，显然就是\(a[R]\)上一次出现的位置+1，因为公式中是\(-cnt\)，所以更新值为-1。
- 第二部分是\(max\)和\(min\)，利用单调栈来维护，当从栈中弹出时，可以得到该元素作为最大/最小值延伸的区间，更新值就是该元素和新的最大/最小值\(a[R]\)之间的差值。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+50;

const int INF=0x3f3f3f3f;

int T,n,a[N];

//线段树(1-n)维护的是当前R作为右端点，([1,R],[2,R]...[R,R])这些区间的情况，也就是一个点代表一个区间

struct ST{

#define ls i<<1

#define rs i<<1|1

#define mid (l+r)/2

    //维护区间(mx-mn-cnt)的最小值和最小值的个数

    int sm[N*4],mn[N*4],lz[N*4];

    void pushup(int i){

        mn[i]=min(mn[ls],mn[rs]);

        if(mn[ls]==mn[rs]){

            sm[i]=sm[ls]+sm[rs];

        }else if(mn[ls]<mn[rs]){

            sm[i]=sm[ls];

        }else{

            sm[i]=sm[rs];

        }

    }

    void pushdown(int i){

        if(lz[i]){

            lz[ls]+=lz[i];

            lz[rs]+=lz[i];

            mn[ls]+=lz[i];

            mn[rs]+=lz[i];

            lz[i]=0;

        }

    }

    void build(int i,int l,int r){

        lz[i]=0;

        if(l==r){

            mn[i]=INF;

            sm[i]=0;

            return;

        }

        build(ls,l,mid);

        build(rs,mid+1,r);

        pushup(i);

    }

    //单点插入/修改，即开始增加以ｐ为左端点的区间贡献

    void insert(int i,int l,int r,int p){

        if(l==r){

            //此时以ｐ为左端点的区间只有[p,p]，因此mx-mn-cnt=-1，为合法区间

            mn[i]=-1;

            sm[i]=1;

            return;

        }

        pushdown(i);

        if(p<=mid){

            insert(ls,l,mid,p);

        }else{

            insert(rs,mid+1,r,p);

        }

        pushup(i);

    }

    //区间更新(mx-mn-cnt)

    void update(int i,int l,int r,int ql,int qr,int v){

        if(ql<=l && qr>=r){

            lz[i]+=v;

            mn[i]+=v;

            return;

        }

        pushdown(i);

        if(ql<=mid){

            update(ls,l,mid,ql,qr,v);

        }

        if(qr>mid){

            update(rs,mid+1,r,ql,qr,v);

        }

        pushup(i);

    }

}ac;

map<int,int> lst;

int smx[N],smn[N];

int main(){

//    freopen("in.txt","r",stdin);

    scanf("%d",&T);

    for(int cas=1;cas<=T;cas++){

        ll ans=0;

        scanf("%d",&n);

        ac.build(1,1,n);

        lst.clear();

        int mxt=0,mnt=0;

        for(int i=1;i<=n;i++){

            scanf("%d",&a[i]);

            ac.insert(1,1,n,i);

            //单调栈维护最大最小值区间

            //维护一个小顶栈，那么弹出来的元素作为最大值延伸的位置是[smx[mxt-1]+1,smx[mxt]]

            while(mxt>0 && a[smx[mxt]]<=a[i]){

                ac.update(1,1,n,smx[mxt-1]+1,smx[mxt],a[i]-a[smx[mxt]]);

                mxt--;

            }

            smx[++mxt]=i;

            while(mnt>0 && a[smn[mnt]]>=a[i]){

                ac.update(1,1,n,smn[mnt-1]+1,smn[mnt],-(a[i]-a[smn[mnt]]));

                mnt--;

            }

            smn[++mnt]=i;

            //map维护上一次出现位置

            int L=0;

            if(lst.find(a[i])!=lst.end()){

                L=lst[a[i]]+1;

            }else{

                L=1;

            }

            if(L<=i-1){

                //比如3 1 2 4 3，最新加入的3，所以[1 2 4 3],[2 4 3],[4 3]都应该更新不同数的个数

                //由于维护的是mx-mn-cnt，所以是-1

                ac.update(1,1,n,L,i-1,-1);

            }

            lst[a[i]]=i;

            //以当前a[i]为右端点元素的合法区间个数

            //因为加入新节点(R,R)后，mn[1]肯定为-1，所以无需判断

            ans+=1ll*ac.sm[1];

        }

        printf("Case #%d: %lld\n",cas,ans);

    }

}

巴特西

2018icpc宁夏邀请赛_L_Continuous Intervals

题意

分析

代码

最新文章

热门文章