题解：P9530 [JOIST 2022] 鱼 2 / Fish 2

· · 题解

好牛的题。

一个很厉害的想法是，直接上线段树，我们尝试把两个区间的答案进行合并。

你对于一个区间 [L,R]，假设这里面的某一条鱼，能扩展到的最大区间为 [l,r]，如果 L<l,r<R，那么显然这个小鱼永远也出不来了，我们不需要维护，那么也就是说，我们需要维护所有 [L,R] 的鱼，所有 [L,r] 的鱼，以及 [l,R] 的鱼。

显然我们把所有鱼按照 [l,r] 划分成若干个等价类，一个事情是，这些等价类只有 O(\log V) 个。

这样子的话，我们可以用一个 vector 存所有等价类，然后考虑合并这些等价类。

考虑怎么维护，我们大概要支持左边节点 [l,R] 区间的鱼与右边区间 [L,r] 的鱼的合并，然后你发现 l 左移的时候，最终区间的 [l',r'] 一定在不断增大，双指针维护即可。

时间复杂度 O(n\log V +q\log n\log V)。

我比较懒，合并的时候多了一个 \log\log V，但是依旧可以通过。 ::::info[code]

const int N=2e5+5;
const ll inf=1e16+7;
int n,m,T;
ll v[N];
struct Info{
    int p,c;
    ll s;
    bool operator<(Info x){return p<x.p;}
};
struct Node{
    int l,r,c;
    vector<Info> L,R;  
}tr[N<<2];
void upd(vector<Info>& s){
    sort(s.begin(),s.end());
    vector<Info> sq;
    int ls=-1;
    for(auto u:s){
        if(u.p==ls)sq.back().c+=u.c;
        else sq.pb(u),ls=u.p;
    }
    s=sq;
}
Node operator+(Node a,Node b){
    Node x;
    x.r=b.r,x.l=a.l; x.c=0;
    vector<Info> &xl=x.L,&xr=x.R;
    for(auto u:a.L)if(u.p!=a.r)xl.pb(u);
    for(auto u:b.R)if(u.p!=b.l)xr.pb(u);
    int ml=v[x.l-1],mr=v[x.r+1];
    v[x.l-1]=inf,v[x.r+1]=inf;
    int L=0,R=-1;
    for(int i=0;i< a.R.size();i++){
        Info u=a.R[i]; chkmax(L,i);
        if(u.s>=v[b.l]){
            R=0;
            while(1){
                ll ns=a.R[L].s+b.L[R].s;
                if(R!=b.L.size() && ns>=v[b.L[R].p+1])R++;
                else if(L!=a.R.size() && ns>=v[a.R[L].p-1])L++;
                else break;
            }
        }
        ll ns=a.R[L].s+((R>=0)?b.L[R].s:0);
        if(L==a.R.size()-1 && R==b.L.size()-1)x.c+=u.c;
        if(R==b.L.size()-1)xr.pb(Info{(L>=0)?a.R[L].p:b.l,u.c,ns});
        if(L==a.R.size()-1)xl.pb(Info{(R>=0)?b.L[R].p:a.r,u.c,ns});
    }
    L=-1,R=0;
    for(int i=0;i< b.L.size();i++){
        Info u=b.L[i]; chkmax(R,i);
        if(u.s>=v[a.r]){
            L=0;
            while(1){
                ll ns=a.R[L].s+b.L[R].s;
                if(R!=b.L.size() && ns>=v[b.L[R].p+1])R++;
                else if(L!=a.R.size() && ns>=v[a.R[L].p-1])L++;
                else break;
            }
        }
        ll ns=((L>=0)?a.R[L].s:0)+b.L[R].s;
        if(L==a.R.size()-1 && R==b.L.size()-1)x.c+=u.c;
        if(R==b.L.size()-1)xr.pb(Info{(L>=0)?a.R[L].p:b.l,u.c,ns});
        if(L==a.R.size()-1)xl.pb(Info{(R>=0)?b.L[R].p:a.r,u.c,ns});
    }
    upd(xl),upd(xr); reverse(xr.begin(),xr.end());
    v[x.l-1]=ml,v[x.r+1]=mr;
    return x;
}
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define root 1,1,n
void pushup(int u){
    tr[u]=tr[u<<1]+tr[u<<1|1];
}
void setup(int u,int l){
    tr[u].c=1;
    tr[u].l=tr[u].r=l;
    tr[u].L.clear(),tr[u].R.clear();
    tr[u].L.pb(Info{l,1,v[l]});
    tr[u].R.pb(Info{l,1,v[l]});
}
void build(int u,int l,int r){
    if(l==r)return setup(u,l);
    build(lson),build(rson);
    pushup(u);
}
void modify(int u,int l,int r,int x,int v){
    if(l==r)return setup(u,l);
    if(x<=mid)modify(lson,x,v);
    if(x> mid)modify(rson,x,v);
    pushup(u);
}
Node query(int u,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[u];
    if(x> mid)return query(rson,x,y);
    if(y<=mid)return query(lson,x,y);
    return query(lson,x,y)+query(rson,x,y);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)v[i]=read();
    m=read();
    build(root);
    while(m--){
        int o=read(),x=read(),y=read();
        if(o==1)v[x]=y,modify(root,x,y);
        if(o==2)printf("%d\n",query(root,x,y).c);
    }
    return 0;
}
//  Think twice,code once

::::