Solution P14380 | Easy Data Structure

· · 题解

若 f(l+1,r)\neq f(l,r) 且 f(l,r-1)\neq f(l,r)，将 [l,r] 视作极小区间。问题转化为计算 [L,R] 中有多少个极小区间。

对于每个 i 求出最大的 r 使得 f(i,r)\neq f(i+1,r)，记作 ar_i；同时求出最小的 l 使得 f(l,i)\neq f(l,i-1)，记作 al_i。

那么极小区间的判定变成了 r\le ar_l 且 l\ge al_r。

令 b(l,r) \in \{0,1\} 表示 [l,r] 是否极小。查询可以看作在 b 上矩形求和。用二维前缀和拆掉考虑。

对 r 扫描线，用历史和线段树维护即可。

int n,q,dfn[500005],out[500005],tim,al[500005],ar[500005],l[500005],r[500005];
vector<int>E[500005];

void dfs(int x,int fa){
    dfn[x]=(++tim);
    for(auto y: E[x]){
        if(y==fa) continue;
        dfs(y,x);
    }
    out[x]=tim;
}
void chkmax(int &a,int b){ if(b>a) a=b; }
namespace zkw{
    int n,c[2000005];
    void init(int _n){
        for(n=1;n<_n;n<<=1);
        for(int i=0;i<(n<<1);i++) c[i]=0;
    }
    void upd(int x,int w){
        for(x+=n-1;x;x>>=1) chkmax(c[x],w);
    }
    int qry(int l,int r){
        int ret=0;
        for(l+=n-1,r+=n;l<r;l>>=1,r>>=1){
            if(l&1) chkmax(ret,c[l++]);
            if(r&1) chkmax(ret,c[--r]);
        }
        return ret;
    }
}
namespace seg{
    int cnt[2000005],tag[2000005]; ll val[2000005];
    void upd(int pos,int v){
        tag[pos]+=v;
        val[pos]+=1ull*v*cnt[pos];
    }
    void pushdown(int pos){
        if(tag[pos]){
            upd(pos<<1, tag[pos]), upd(pos<<1|1, tag[pos]);
            tag[pos]=0;
        }
    }
    void pushup(int pos){
        val[pos]=val[pos<<1]+val[pos<<1|1];
        cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1];
    }
    void update(int l,int r,int ql,int qr,int pos){
        if(qr<l || r<ql) return;
        if(ql<=l && r<=qr){
            upd(pos, 1);
            return;
        }
        int mid=(l+r)>>1; pushdown(pos);
        update(l,mid,ql,qr,pos<<1);
        update(mid+1,r,ql,qr,pos<<1|1);
        pushup(pos);
    }
    void modify(int l,int r,int x,int s,int pos){
        if(l==r){ cnt[pos]=s; return; }
        int mid=(l+r)>>1; pushdown(pos);
        if(x<=mid) modify(l,mid,x,s,pos<<1);
        else modify(mid+1,r,x,s,pos<<1|1);
        pushup(pos);
    }
    ll query(int l,int r,int ql,int qr,int pos){
        if(qr<l || r<ql) return 0;
        if(ql<=l && r<=qr) return val[pos];
        int mid=(l+r)>>1; pushdown(pos);
        return query(l,mid,ql,qr,pos<<1)+query(mid+1,r,ql,qr,pos<<1|1);
    }
}
vector<int>vec[500005];
vector<pair<int,int>>qry[500005];
ll ans[500005];

void procedure(){
    n=read(),q=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        E[x].pb(y), E[y].pb(x);
    }   
    dfs(1,0);
    zkw::init(n);
    for(int i=1;i<=n;i++){
        vector<int>cur;
        for(auto j: E[i]){
            if(dfn[j]<dfn[i]) cur.pb(max(zkw::qry(1,dfn[i]-1),zkw::qry(out[i]+1,n)));
            else cur.pb(zkw::qry(dfn[j],out[j]));
        }
        if(cur.size()>=2){ 
            sort(cur.begin(), cur.end(), greater<int>());
            al[i]=cur[1]+1;
        }else al[i]=1;
        zkw::upd(dfn[i],i);
    }
    zkw::init(n);
    for(int i=n;i>=1;i--){
        vector<int>cur;
        for(auto j: E[i]){
            if(dfn[j]<dfn[i]) cur.pb(max(zkw::qry(1,dfn[i]-1),zkw::qry(out[i]+1,n)));
            else cur.pb(zkw::qry(dfn[j],out[j]));
        }
        if(cur.size()>=2){ 
            sort(cur.begin(), cur.end(), greater<int>());
            ar[i]=n-cur[1];
        }else ar[i]=n;
        zkw::upd(dfn[i],n-i+1);
        vec[i].pb(i), vec[ar[i]+1].pb(-i);
    }

    for(int i=1;i<=q;i++){
        l[i]=read(),r[i]=read();
        qry[l[i]-1].pb(l[i]-1,i), qry[l[i]-1].pb(r[i],-i);
        qry[r[i]].pb(l[i]-1,-i), qry[r[i]].pb(r[i],i);
    }
    for(int r=1;r<=n;r++){
        for(auto x: vec[r]){
            if(x>0) seg::modify(1,n,x,1,1);
            else seg::modify(1,n,-x,0,1);
        }
        seg::update(1,n,al[r],r,1);

        for(auto [x,y]: qry[r]){
            ll val=seg::query(1,n,1,x,1);

            if(y>0) ans[y]+=val;
            else ans[-y]-=val;
        }
    }

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