2018宁夏邀请赛 Continuous Intervals（单调栈线段树

https://vjudge.net/problem/Gym-102222L

题意：给你n个数的序列，让判断有几个区间满足排完序后相邻两数差都不大于1。

题解：对于一个区间 [L,R]，记最大值为 max、最小值为 min、数字种类数为 cnt，那么这个区间是 continuous interval 当且仅当 max−min+ 1 = cnt。考虑从小到大枚举 R，用线段树维护每个 L 的区间 [L,R] 的 max−min−cnt 的值。由于总有 max−min+1 ≥cnt，那么只需要维护线段树上每个 L 对应的 max−min−cnt 的最小值，以及有多少个 L 取到这个最小值。当 R 变大时，每个 L 对应的三个值都需要进行修改。对于 max 和 min，可以用单调栈来维护后缀 max 和 min，然后在线段树上进行区间加减操作，对于 cnt，只需要在线段树上对区间 [lastai + 1,R] 进行加减操作。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=2000010;

int Mn[maxn],lazy[maxn],sum[maxn],a[maxn];

int q1[maxn],t1,q2[maxn],t2;

map<int,int>mp;

void build(int Now,int L,int R)

{

    sum[Now]=R-L+1; Mn[Now]=lazy[Now]=0;

    if(L==R) return ; int Mid=(L+R)>>1;

    build(Now<<1,L,Mid);

    build(Now<<1|1,Mid+1,R);

}

void pushdown(int Now)

{

    if(!lazy[Now]) return ;

    Mn[Now<<1]+=lazy[Now]; Mn[Now<<1|1]+=lazy[Now];

    lazy[Now<<1]+=lazy[Now]; lazy[Now<<1|1]+=lazy[Now];

    lazy[Now]=0;

}

void pushup(int Now)

{

    Mn[Now]=min(Mn[Now<<1],Mn[Now<<1|1]);

    if(Mn[Now<<1]==Mn[Now<<1|1]) sum[Now]=sum[Now<<1]+sum[Now<<1|1];

    else if(Mn[Now<<1]<Mn[Now<<1|1]) sum[Now]=sum[Now<<1];

    else sum[Now]=sum[Now<<1|1];

}

void update(int Now,int L,int R,int l,int r,int v)

{

    if(l>r) return ;

    if(L==R) {

        Mn[Now]+=v;

        return ;

    }

    if(l<=L&&r>=R){

        Mn[Now]+=v; lazy[Now]+=v;

        return ;

    }

    int Mid=(L+R)>>1; pushdown(Now);

    if(l<=Mid) update(Now<<1,L,Mid,l,r,v);

    if(r>Mid) update(Now<<1|1,Mid+1,R,l,r,v);

    pushup(Now);

}

int main()

{

    int T,N,C=0; ll ans;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

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

        build(1,1,N);

        t1=t2=0; ans=0;  mp.clear();

        rep(i,1,N){

            update(1,1,N,i,i,-1);

            while(t1&&a[i]>=a[q1[t1]]){

                update(1,1,N,q1[t1-1]+1,q1[t1],a[i]-a[q1[t1]]);

                t1--;

            }

            q1[++t1]=i; //单减栈

            while(t2&&a[i]<=a[q2[t2]]){

                update(1,1,N,q2[t2-1]+1,q2[t2],a[q2[t2]]-a[i]);

                t2--;

            }

            q2[++t2]=i; //单增栈

            update(1,1,N,mp[a[i]]+1,i-1,-1); mp[a[i]]=i;

            ans+=sum[1];

        }

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

    }

    return 0;

}

巴特西

2018宁夏邀请赛 Continuous Intervals（单调栈线段树

最新文章

热门文章

巴特西

2018宁夏邀请赛 Continuous Intervals（单调栈 线段树

最新文章

热门文章

2018宁夏邀请赛 Continuous Intervals（单调栈线段树