P5574 [CmdOI2019] 任务分配问题的一个更优做法

· · 题解

首先大家都知道了 O(nk\log^2 n) 的做法吧，就是决策单调性分治+类莫队移动指针计算贡献，这是一个很优秀的做法，但是在 k 很大的时候这个做法就寄了。然后 k 很大的时候众所周知的是这个东西可以 wqs 二分优化，但是此时形如 f_{i}=\min \limits_{j<i}f_{j}+w(j,i) 的 DP 又不能直接决策单调性做，除非套个 cdq 多个 \log n，二分队列的话又不能快速计算 w(j,i)，区间顺序对只能 O(\sqrt n) 单次询问，这样太慢了。

但是在阅读完 APIO2021 Itst 大神的课件之后我们有一种可以由冷门科技 Wilber 算法改造的小清新做法。（其实就是把 SMAWK 换成了小清新决策单调性分治）

具体地，首先用 [c,r] 一段作为决策点估计 [r+1,\min(n,r+(r+c-1))] 的答案，得到的数组记为 g，显然所有满足决策点在 [r,c] 之间的位置 g 就是最优解了。然后再用 [r+1,\min(n,r+(r+c-1))] 一段的 g 去估计这一段的答案，得到的数组 h。然后将 h 和 g 对应位置两两比对得到第一个 h 比 g 优的位置 t，显然 [r+1,t-1] 位置的 g 数组是最优解，这里得到的 h_{t} 也是最优解，这样可以得到 t 是第一个决策点 >r 的点，显然此时已经算完 [r+1,t] 的答案，直接把 [c,r] 点对改为 [r+1,t] 继续做下去即可。（特殊的，如果 t 不存在就直接把 r 改成 \min(n,r+(r+c-1)) 即可）。

放一下本题这个部分的代码 （是不是非常小清新）：

void divide(int l,int r,int L,int R,const int &_mid){//决策单调性分治
    if(l>r) return;
    int mid=l+r>>1,p=L;
    F[mid]=(NODE){G[L].val+w(L+1,mid)+_mid,G[L].ch+1};
    rep(i,L+1,min(mid-1,R)){
        delL(cl++);//卡常
        NODE tmp=(NODE){G[i].val+val+_mid,G[i].ch+1};
        if(tmp<F[mid]) F[mid]=tmp,p=i;
    }
    divide(l,mid-1,L,p,_mid);
    divide(mid+1,r,p,R,_mid);
}
int Wilber(int mid){
    int r=0,c=0;
    cl=1,cr=0,TR.tt=0,memset(TR.c,0,sizeof TR.c);
    while(r<n){
        int ri=min(n,r+r-c+1);
        F=g,G=f,divide(r+1,ri,c,r,mid);//第一部分：用f估计得到g
        F=h,G=g,divide(r+2,ri,r+1,ri,mid);//第二部分：用g估计得到h
        int t=r+2;f[r+1]=g[r+1];
        while(t<=ri&&g[t]<h[t]) f[t]=g[t],++t;//找到第一个h比j优的t
        if(t>ri) r=ri;//t不存在，[c,r]->[c,ri]
        else f[t]=h[t],c=r+1,r=t;//t存在，[c,r]->[r+1,t]
    }
    return f[n].ch;
}

注意到花费了 O(1) 的次数要么让 r 和 r-c+1 都增大了 O(1)，要么让 r-c+1 减少 O(1)，所以总长均摊是 O(n)的，所以一轮的时间就是 O(n\log nP) （P 是莫队指针移动的复杂度）的，本题一轮就是 O(n\log^2 n) 的。

然后就直接套上 wqs 二分，时间复杂度 O(n\log^2 n\log V)，但是 Wilber 因为每次要做两次决策单调性分治的原因常数大到爆炸，卡了卡常才勉强卡进 1s。

提一句这里可以用序列分块套值域分块做到 O(n\sqrt n) 的预处理，O(1) 回答区间有几个数 >/< 自己，然后做到 O(n\sqrt n+n\log n\log V)，但是常数过大而且空间 O(n\sqrt n) 估计表现不是很良好。

code（注意值域上界不是 10^8，这里只是卡常才开这么多）：

const int N=25500;
int n,k,a[N];
struct BIT{
    int c[N],tt;
    #define lowbit(x) (x&(-x))
    void update(int u,int x){tt+=x;for(;u<=n;u+=lowbit(u)) c[u]+=x;}
    int query(int u){int res=0;for(;u;u-=lowbit(u)) res+=c[u];return res;}
}TR;
int cl,cr;
LL val;
void delR(int i){val-=TR.query(a[i]-1),TR.update(a[i],-1);}
void addR(int i){val+=TR.query(a[i]-1),TR.update(a[i],1);}
void delL(int i){val-=TR.tt-TR.query(a[i]),TR.update(a[i],-1);}
void addL(int i){val+=TR.tt-TR.query(a[i]),TR.update(a[i],1);}
LL w(int l,int r){  
    while(cr>r) delR(cr--);
    while(cl<l) delL(cl++);
    while(cr<r) addR(++cr);
    while(cl>l) addL(--cl);
    return val;
}
struct NODE{
    LL val;int ch;
    bool operator <(const NODE &T)const{
        return val==T.val?ch>T.ch:val<T.val;
    }
}f[N],g[N],h[N],*F,*G;
void divide(int l,int r,int L,int R,const int &_mid){
    if(l>r) return;
    int mid=l+r>>1,p=L;
    F[mid]=(NODE){G[L].val+w(L+1,mid)+_mid,G[L].ch+1};
    rep(i,L+1,min(mid-1,R)){
        delL(cl++);
        NODE tmp=(NODE){G[i].val+val+_mid,G[i].ch+1};
        if(tmp<F[mid]) F[mid]=tmp,p=i;
    }
    divide(l,mid-1,L,p,_mid);
    divide(mid+1,r,p,R,_mid);
}
int Wilber(int mid){
    int r=0,c=0;
    cl=1,cr=0,TR.tt=0,memset(TR.c,0,sizeof TR.c);
    while(r<n){
        int ri=min(n,r+r-c+1);
        F=g,G=f,divide(r+1,ri,c,r,mid);
        F=h,G=g,divide(r+2,ri,r+1,ri,mid);
        int t=r+2;f[r+1]=g[r+1];
        while(t<=ri&&g[t]<h[t]) f[t]=g[t],++t;
        if(t>ri) r=ri;
        else f[t]=h[t],c=r+1,r=t;
    }
    return f[n].ch;
}
LL wqs(){
    int l=0,r=1e8,ans;
    while(l<=r){
        int mid=l+r>>1;
        if(Wilber(mid)>=k) ans=mid,l=mid+1;
        else r=mid-1;
    }
    Wilber(ans);
    return f[n].val-1ll*ans*k;
}