【P1295】我 CDQ 硬上三维偏序怎么你了

· · 题解

在题解区转了一圈，发现仅有几篇题解提到了这个可以用 CDQ 分治做。如果再算上双倍经验和三倍经验的题解区，一篇 CDQ 分治的题解都没有，待遇比幸运猫猫树还糟糕！

虽然最劣解但是 CDQ 分治她好想啊我不会线段树对不起拜线段树教，名字还这么好听怎么你了。

像其他题解一样，我们设 f_i 表示划分前 i 个数的最小代价。顺便把 h_i 做前缀和变 sum_i。我们枚举上一段在哪里结束，就有：

f_i = \min_{sum_i-sum_j \le M}\left \{ f_j+\max_{j+1\le k\le i}h_k \right \}

当然，上式还有一个隐含条件 i>j。还有这个 j 也是可以取到 0 的。

将 sum_i-sum_j \le M 移项，就是 sum_i-M\le sum_j。再算上 i>j，很容易想到用 CDQ 分治处理这两个偏序条件。如果我们能用数据结构之类的方法将花括号里面的 \max 处理掉，这道题就做完了。

先考虑在 CDQ 内部如何转移。设分治区间左端点为 L，右端点为 R。我们按中点把区间分开后将其分别按 sum 升序排序。使用双指针就可以解决两个偏序限制。

接下来考虑如何处理最大值的那部分。注意到最大值部分所对应的区间一定经过中点，所以该区间的最大值要么来自左半部分，要么来自右半部分。

我们从中间向两边分别弄个后缀最大值和前缀最大值。左半的后缀最大值叫 lmx_i，右半的前缀最大值叫 rmx_i。

开两棵权值线段树 A 和 B。对于左半部分，每扫到一个点 i，就把 f_i 和 f_i+lmx_{i+1} 分别打 A 和 B 的下标 lmx_{i+1} 上。对于右半部分，每扫到一个点 i，就考虑转移的最大值来自左半边还是右半边。如果来自左半边，就在 B 里查找比 rmx_i 大的值域；如果来右自半边，就在 A 里查找比 rmx_i 小的值域。这样这道题就做完了。

我知道你要说什么，上面有个 lmx_{i+1}，那要是左半边扫到中点不就炸了吗。不用担心兄弟，注意到扫到中点意味着整个区间都在右半边，也就是最值在右半边，所以此时只要令 lmx_{i+1} 为 -inf 即可。

这样我们就真的做完这道题了。

注意开 long long 和离散化。

话说权值线段树是不是可以改成树状树祖？

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+7;
const LL inf=0x7f7f7f7f7f7f7f7f;
int N;
LL M;
LL a[maxn],sum[maxn],f[maxn];
LL un[maxn];
int UN;
#define get(xx) (lower_bound(un+1,un+UN+1,(xx))-un)
//单点修改，区间查询 
struct SegmentTree{
    LL mn[maxn<<2];
    SegmentTree(){memset(mn,0x7f,sizeof(mn));}
    void Modify(int p,int L,int R,int inx,LL xx){
        if(L>=R){mn[p]=min(mn[p],xx);return;}
        int mid=(L+R)>>1;
        if(inx<=mid)Modify(p<<1,L,mid,inx,xx);
        else Modify(p<<1|1,mid+1,R,inx,xx);
        mn[p]=min(mn[p<<1],mn[p<<1|1]);
    }
    void Set(int p,int L,int R,int inx,LL xx){
        if(L>=R){mn[p]=xx;return;}
        int mid=(L+R)>>1;
        if(inx<=mid)Set(p<<1,L,mid,inx,xx);
        else Set(p<<1|1,mid+1,R,inx,xx);
        mn[p]=min(mn[p<<1],mn[p<<1|1]);
    }
    LL Query(int p,int L,int R,int ql,int qr){
        if(ql<=L&&R<=qr)return mn[p];
        int mid=(L+R)>>1;
        LL ret=inf;
        if(ql<=mid)ret=min(ret,Query(p<<1,L,mid,ql,qr));
        if(mid+1<=qr)ret=min(ret,Query(p<<1|1,mid+1,R,ql,qr));
        return ret;
    }
}SEG1,SEG2;
//带max，不带max
struct OP{int inx;LL val;}O[maxn];
bool cmp(OP A,OP B){return A.val>B.val;}
bool cmpid(OP A,OP B){return A.inx<B.inx;}
LL lmx[maxn],rmx[maxn];
void CDQ(int L,int R){
    if(L>=R)return;
    int mid=(L+R)>>1;
    CDQ(L,mid);
    sort(O+L,O+mid+1,cmp);
    sort(O+mid+1,O+R+1,cmp);
    lmx[mid+1]=-inf;
    for(int i=mid;i>=L;i--)lmx[i]=max(lmx[i+1],a[i]);
    rmx[mid]=-inf;
    for(int i=mid+1;i<=R;i++)rmx[i]=max(rmx[i-1],a[i]);
    int p=L;
    for(int i=mid+1;i<=R;i++){
        while(p<=mid&&O[p].val>=O[i].val-M){
            SEG1.Modify(1,1,UN,get(lmx[O[p].inx+1]),f[O[p].inx]+lmx[O[p].inx+1]);
            SEG2.Modify(1,1,UN,get(lmx[O[p].inx+1]),f[O[p].inx]);
            ++p;
        }
        LL res=inf;
        res=min(res,SEG1.Query(1,1,UN,get(rmx[O[i].inx])+1,UN));
        res=min(res,SEG2.Query(1,1,UN,1,get(rmx[O[i].inx]))+rmx[O[i].inx]);
        f[O[i].inx]=min(f[O[i].inx],res);
    }
    while(p>L){
        --p;
        SEG1.Set(1,1,UN,get(lmx[O[p].inx+1]),inf);
        SEG2.Set(1,1,UN,get(lmx[O[p].inx+1]),inf);
    }
    sort(O+mid+1,O+R+1,cmpid);
    CDQ(mid+1,R);
}
int main(){
    scanf("%d %lld",&N,&M);
    for(int i=1;i<=N;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],un[++UN]=a[i];
    un[++UN]=-inf;un[++UN]=inf;
    sort(un+1,un+UN+1);UN=unique(un+1,un+UN+1)-un-1;
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    for(int i=0;i<=N;i++)O[i].inx=i,O[i].val=sum[i];
    CDQ(0,N);
    printf("%lld",f[N]);
    return 0;
}