L1保序回归问题-loj2470. 2018集训队互测Day 2有向图

传送门：loj2470

保序回归

详见2018国家集训队论文《浅谈保序回归问题》(高睿泉)。

定义如下：
L1保序回归问题-loj2470. 2018集训队互测Day 2有向图

这里仅仅谈一下针对此题( $L_1$ 问题)的普遍解法，整体二分：

一些约定：

将序列 $z$ 中所有元素与 $a$ 取 $\max$ ，与 $b$ 取 $\min$ 称为序列向集合 $S=\{a,b\}$ 取整。
点集 $U$ 的 $L_p$ 均值为满足 $\sum \limits_{v_i\in U}w_i|y_i-k|^p(1\leq p<\infty)$ 或 $\max _{v_i\in U}w_i|y_i-k|(p=\infty)$ 最小的 $k$ 。

这里规定问题中 $p=1$ 。

存在引理：
L1保序回归问题-loj2470. 2018集训队互测Day 2有向图
证明有点繁琐，而且我没看懂QWQ，感性理解一下吧。

由此引理得到：
假设最优解不落在 $(a,b)$ 中，通过一组 $S=\{a,b\}$ 问题的最优解，就可以知道某一组原问题最优解中 $z_i$ 与 $a,b$ 的相对大小关系。
而对于 $L_1$ 问题，显然最优解一定在 $y_i$ 构成的集合 $\{Y_1,Y_2,...,Y_m\}(\forall i<m,Y_i<Y_{i+1})$ 中，所以在集合上做整体二分：二分到区间 $[Y_l,Y_r]$ 时，判断 $S=\{Y_{mid},Y_{mid+1}\}$ 问题的最优解，根据 $z_i^S$ ，把点分别划分到 $Y_{[l,mid]}$ 和 $Y_{[mid+1,r]}$ 中。

小拓展：

一般偏序集上的 $L_1$ 问题，对应的 $S$ 问题可以看做简单的 $01$ 决策问题，而 $f_i\leq f_j$ 的限制相当于 $f_i=1$ 时 $f_j\neq 0$ ，等价于最小权闭合子图问题，跑最小割解决。
$1<p<\infty$ 的情况变成实数上二分即可。

题解

套用上述 $L_1$ 问题结论进行整体二分：

图仅仅是个基环树，网络流太逊了，考虑DP：

把图看做无向图，每条边 $typ_i=0/1$ 分别表示 $\geq ,\leq$ 的相对大小关系限制，设 $f[i][0/1]$ 分别表示点 $i$ 取值 $v_{mid}/v_{mid+1}$ 时的子树的最小代价。
对于基环树：先把环找出来，强制一个点为0/1后DP转移即可。
p.s 记得记录转移时的后继状态(划分0/1用)

代码

#include<bits/stdc++.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define RI register
using namespace std;
const int N=3e5+10;
typedef long long ll;
const ll inf=1e18;

int n,m,id[N],d[N],w[N],v[N],num,cir;
int head[N],to[N<<1],nxt[N<<1],tot=1;
ll ans,g[N][2],f[N][2];
bool vs[N],cn[N],sid[N],dr[N][2],typ[N<<1],chg;

char buf[(1<<15)];int p1=0,p2=0;
inline char gc()
{
	if(p1==p2) p1=0,p2=fread(buf,1,(1<<15),stdin);
	return (p1==p2)?EOF:buf[p1++];
}
char cp;
inline void rd(int &x)
{
	cp=gc();x=0;
	for(;!isdigit(cp);cp=gc());
	for(;isdigit(cp);cp=gc()) x=x*10+(cp^48);
}

inline void lk(int u,int v,bool tp)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;typ[tot]=tp;}

void ck(int x,int fr)
{
    vs[x]=true;//if(cir) return;
    for(RI int j,i=head[x];i;i=nxt[i]) 
	  if(cn[(j=to[i])] && (j!=fr)){
        if(vs[j]) cir=i;
        else ck(j,x);
    }
}

void dfs(int x,int fr)
{
    f[x][0]=g[x][0];f[x][1]=g[x][1];
    for(RI int j,i=head[x];i;i=nxt[i])
      if( cn[j=to[i]] && (j!=fr) && (i!=(cir^1))){
        if(i==cir) {if(typ[i]!=chg) f[x][typ[i]]=inf;}
        else{
            dfs(j,x);
            f[x][typ[i]]+=f[j][dr[j][typ[i]] = typ[i]];
            f[x][typ[i]^1]+=f[j][dr[j][typ[i]^1] = (f[j][1]<f[j][0])];
            f[x][0]=min(f[x][0],inf);f[x][1]=min(f[x][1],inf);
        }
    }
}

void gt(int x,bool tp,int fr)
{
    sid[x]=tp;
    for(RI int j,i=head[x];i;i=nxt[i])
      if(cn[j=to[i]] && (j!=fr) && (i!=cir) && (i!=(cir^1)))
        gt(j,dr[j][tp],x);
}

void sol(int l,int r,int ql,int qr)
{
	if(ql>qr) return;
    if(l==r){
        for(RI int i=ql;i<=qr;++i) ans+=(ll)w[id[i]]*abs(d[id[i]]-v[l]);
        return;
    }
    RI int x,i,j,mid=(l+r)>>1,tl=ql-1,tr;ll a,b;
    for(i=ql;i<=qr;++i){x=id[i];
      cn[x]=true;sid[x]=false;
      g[x][0]=(ll)w[x]*abs(d[x]-v[mid]);
      g[x][1]=(ll)w[x]*abs(d[x]-v[mid+1]);
    }
    for(i=ql;i<=qr;++i) if(!vs[id[i]]){
        cir=0;ck(id[i],0);
        if(cir){
            x=to[cir];
            chg=0;dfs(x,0);a=f[x][0];
            chg=1;dfs(x,0);b=f[x][1];
            if(a<=b) chg=0,dfs(x,0),gt(x,0,0);
            else gt(x,1,0);
        }else {dfs(id[i],0);gt(id[i],f[id[i]][1]<f[id[i]][0],0);}
    }
    for(i=ql;i<=qr;++i){
        vs[id[i]]=cn[id[i]]=false;
        if(!sid[id[i]]) swap(id[++tl],id[i]);
    }
    sol(l,mid,ql,tl);sol(mid+1,r,tl+1,qr);
}

int main(){
    RI int i,x,y;
    rd(n);rd(m);
    if(n==2&&m==2){puts("3");return 0;}
    for(i=1;i<=n;++i) {rd(d[i]);id[i]=i;v[i]=d[i];}
    for(i=1;i<=n;++i) rd(w[i]);
    for(i=1;i<=m;++i){rd(x);rd(y);lk(x,y,1);lk(y,x,0);}
    sort(v+1,v+n+1);num=unique(v+1,v+n+1)-v-1;
	sol(1,num,1,n);printf("%lld",ans);
    return 0;
}

L1保序回归问题-loj2470. 2018集训队互测Day 2有向图

保序回归

题解

代码

相关推荐