[cf 997 E] Good Subsegments

(这是石神找到的一道hiao题。)

题意:

你有一个长度为n的排列,有Q组询问$[l,r]$,每次询问$[l,r]$的子区间中有多少是好的。

一个区间是好的区间当且仅当该区间中的元素在排序后是连续的。

$n,Qleq 120000$。

题解:

为什么说这是一道hiao题呢?

像我一样的数据结构弱智选手看到之后可能会想一些树套树的操作。

但这个题有一种具有代表性的经典方法。

注意到一段区间是好的当且仅当$(max-min)-(r-l)=0$。

我们可以将将询问离线下来,每次处理以$r$为右端点的所有询问。

考虑从左往右枚举右端点$r$,并用一棵线段树维护每个点$l$的$(max-min)-(r-l)$的值。

我们不妨将以$r$为右端点时的这颗线段树称作版本$r$。

那么,以$r$为右端点的好区间个数就是版本$r$中0的个数。

以$r$为右端点,左端点在$[l,r]$间的好区间个数就是版本$r$中$[l,r]$中0的个数之和,记为$siz[r][l,r]$。

但是注意到,我们要求的答案其实是$sum_{i=l}^{r}{siz[i][l,i]}$。

那么需要对线段树上的每个节点额外记录一个$sum$,代表这个区间所有版本中0的个数之和。

也就是${sum[l,r]}=sum_{i=1}^{now}{siz[i][l,r]}$。

显然答案就是$sum[l,r]$,那么如何维护这个$sum$呢?

不妨维护一个类似$lazy$标记的$tag$标记,表示该区间现在的$siz$要对$sum$产生几次的贡献。

这个标记实际上就是把$min=0$时的$siz$一直继承下来,直到访问到它的时候再更新$siz$。

注意无论该区间现在的$min$值是不是等于0(可能被上面区间的$pushdown$改掉了),在访问到它之前都需要保留该标记,因为那个0的版本始终是有贡献的。

在$pushdown$这个$tag$的时候要注意:假如该区间当前的$min$值是由一个而不是两个子区间转移上来的,那我们只应该更新转移上来的那个子区间的$tag$。

如何判断哪个是转移上来的子区间?显然当且仅当$min_{son}=min_{now}$(注意$min_{now}$未必等于0)。

时间复杂度$O((n+Q)logn)$。

积累套路:对于询问区间子序列的信息,可以离线移动右指针,类似扫描线一样计算贡献。

代码:

#include<bits/stdc++.h>
#define maxn 120005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long
 
using namespace std;
ll N,Q,A[maxn],mn[maxn<<2],ans[maxn];
ll sum[maxn<<2],nd[maxn<<2],lz[maxn<<2];
ll siz[maxn<<2],tim[maxn<<2];
vector<pair<ll,ll> > ques[maxn];
struct node{ll v,l,r;};
stack<node> smx,smn;
 
inline ll read(){
    ll x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
 
inline void pushup(ll k){
    if(mn[k<<1]==mn[k<<1|1]) mn[k]=mn[k<<1],siz[k]=siz[k<<1]+siz[k<<1|1];
    else if(mn[k<<1]<mn[k<<1|1]) mn[k]=mn[k<<1],siz[k]=siz[k<<1];
    else mn[k]=mn[k<<1|1],siz[k]=siz[k<<1|1];
}
inline void pushdown(ll k){
    if(lz[k]){
        lz[k<<1]+=lz[k],lz[k<<1|1]+=lz[k];
        mn[k<<1]+=lz[k],mn[k<<1|1]+=lz[k];
        lz[k]=0;
    }
    if(nd[k]){
        if(mn[k<<1]==mn[k]) sum[k<<1]+=siz[k<<1]*nd[k],nd[k<<1]+=nd[k];
        if(mn[k<<1|1]==mn[k]) sum[k<<1|1]+=siz[k<<1|1]*nd[k],nd[k<<1|1]+=nd[k];
        nd[k]=0; 
    }
}
inline void build(ll l,ll r,ll k){
    if(l==r){mn[k]=inf,siz[k]=1;return;}
    ll mid=l+r>>1;
    build(l,mid,k<<1),build(mid+1,r,k<<1|1);
    pushup(k); return;
}
inline void add(ll l,ll r,ll x,ll y,ll v,ll t,ll k){
    if(x<=l && r<=y){mn[k]+=v,lz[k]+=v;return;}
    pushdown(k); ll mid=l+r>>1;
    if(x<=mid) add(l,mid,x,y,v,t,k<<1);
    if(y>mid) add(mid+1,r,x,y,v,t,k<<1|1);
    pushup(k); return;
}
inline void ins(ll l,ll r,ll p,ll v,ll t,ll k){
    if(l==r){mn[k]=v;return;}
    pushdown(k); ll mid=l+r>>1;
    if(p<=mid) ins(l,mid,p,v,t,k<<1);
    else ins(mid+1,r,p,v,t,k<<1|1);
    pushup(k); return; 
}
inline ll query(ll l,ll r,ll x,ll y,ll t,ll k){
    if(x<=l && r<=y) return sum[k];
    pushdown(k); ll mid=l+r>>1,res=0;
    if(x<=mid) res+=query(l,mid,x,y,t,k<<1);
    if(y>mid) res+=query(mid+1,r,x,y,t,k<<1|1);
    return res;
}
 
int main(){
    N=read();
    for(ll i=1;i<=N;i++) A[i]=read();
    Q=read();
    for(ll i=1;i<=Q;i++){
        ll l=read(),r=read();
        ques[r].push_back(make_pair(i,l));
    }
    build(1,N,1);
    for(ll i=1;i<=N;i++){
        ll x=A[i],nl1=i,nl2=i;
        while(!smx.empty()){
            if(smx.top().v<x){
                ll l=smx.top().l,r=smx.top().r;
                add(1,N,l,r,x-smx.top().v,i,1);
                nl1=l,smx.pop();
            }
            else break;
        }
        while(!smn.empty()){
            if(smn.top().v>x){
                ll l=smn.top().l,r=smn.top().r;
                add(1,N,l,r,smn.top().v-x,i,1);
                nl2=l,smn.pop();
            }
            else break;
        }
        node tp1; tp1.v=x,tp1.l=nl1,tp1.r=i;
        node tp2; tp2.v=x,tp2.l=nl2,tp2.r=i;
        smx.push(tp1),smn.push(tp2);
        if(i-1) add(1,N,1,i-1,-1,i,1);
        ins(1,N,i,0,i,1);
        sum[1]+=siz[1],nd[1]+=1;
        for(ll j=0;j<ques[i].size();j++){
            ll l=ques[i][j].second,r=i,id=ques[i][j].first;
            ans[id]=query(1,N,l,r,i,1); 
        } 
    }
    for(ll i=1;i<=Q;i++)
        printf("%I64d
",ans[i]);
    return 0;
}
cf 997 E
原文地址:https://www.cnblogs.com/YSFAC/p/11661668.html