题解 CF997E 【Good Subsegments】

先将问题进行转化，发现满足\((max-min)-(r-l)=0\)的区间即为好区间。

对于本题这样的统计子区间的问题，先将询问离线，按右端点排序一个一个解决，固定右端点，然后通过数据结构来处理出区间信息，询问直接查询区间合法的贡献即可，扫一遍就能解决所有询问。

继续看这个式子\((max-min)-(r-l)=0\)，发现如果去维护这个式子的值，对于固定的右端点，可以统计出其之前的左端点与该右端点的区间最小值及其个数，最小值个数即为在这个区间内可以对这个固定的右端点有贡献的左端点。

但这只能记录右端点固定的答案，无法处理子区间的问题，可以记录下历史最小值个数和，再进行询问即为这段区间的所有子区间的答案了。

具体实现时，维护\(max-min\)的变化可以通过单调栈来实现，\(r-l\)的变化直接对整个区间减一即可，历史最小值个数和需要通过打标记来看该区间是否能产生贡献，细节就看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 500010

#define ls (cur<<1)

#define rs (cur<<1|1)

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,q,t1,t2,root=1;

int a[maxn],s1[maxn],s2[maxn];

ll ans[maxn],mi[maxn],cnt[maxn],sum[maxn],add[maxn],tag[maxn];

struct Query

{

    int l,id;

};

vector<Query> ve[maxn];

void pushup(int cur)

{

    ll lm=mi[ls],rm=mi[rs],lc=cnt[ls],rc=cnt[rs];

    if(lm==rm) mi[cur]=lm,cnt[cur]=lc+rc;

    if(lm<rm) mi[cur]=lm,cnt[cur]=lc;

    if(lm>rm) mi[cur]=rm,cnt[cur]=rc;

    sum[cur]=sum[ls]+sum[rs];

}

void pushadd(int cur,ll v)

{

    mi[cur]+=v,add[cur]+=v;

}

void pushtag(int cur,ll v)

{

    sum[cur]+=cnt[cur]*v,tag[cur]+=v;

}

void pushdown(int cur)

{

    if(add[cur])

        pushadd(ls,add[cur]),pushadd(rs,add[cur]),add[cur]=0;

    if(tag[cur])

    {

        if(mi[cur]==mi[ls]) pushtag(ls,tag[cur]);

        if(mi[cur]==mi[rs]) pushtag(rs,tag[cur]);

        tag[cur]=0;

    }

}

void build(int l,int r,int cur)

{

    if(l==r)

    {

        mi[cur]=l,cnt[cur]=1;

        return;

    }

    build(l,mid,ls),build(mid+1,r,rs);

    pushup(cur);

}

void modify(int L,int R,int l,int r,ll v,int cur)

{

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

    {

        pushadd(cur,v);

        return;

    }

    pushdown(cur);

    if(L<=mid) modify(L,R,l,mid,v,ls);

    if(R>mid) modify(L,R,mid+1,r,v,rs);

    pushup(cur);

}

ll query(int L,int R,int l,int r,int cur)

{

    if(L<=l&&R>=r) return sum[cur];

    pushdown(cur);

    ll ans=0;

    if(L<=mid) ans+=query(L,R,l,mid,ls);

    if(R>mid) ans+=query(L,R,mid+1,r,rs);

    return ans;

}

int main()

{

    read(n),build(1,n,root);

    for(int i=1;i<=n;++i) read(a[i]);

    read(q);

    for(int i=1;i<=q;++i)

    {

        int l,r;

        read(l),read(r);

        ve[r].push_back((Query){l,i});

    }

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

    {

        while(t1&&a[s1[t1]]<=a[i])

        {

            modify(s1[t1-1]+1,s1[t1],1,n,a[i]-a[s1[t1]],root);

            t1--;

        }

        while(t2&&a[s2[t2]]>=a[i])

        {

            modify(s2[t2-1]+1,s2[t2],1,n,a[s2[t2]]-a[i],root);

            t2--;

        }

        s1[++t1]=s2[++t2]=i,pushadd(root,-1),pushtag(root,1);

        int size=ve[i].size();

        for(int j=0;j<size;++j)

            ans[ve[i][j].id]=query(ve[i][j].l,i,1,n,root);

    }

    for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);

    return 0;

}

巴特西

题解 CF997E 【Good Subsegments】

最新文章

热门文章