本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-31 14:04:28

vp 被卡死在这题了，写个题解记录一下。

题意

长度为 $n$ 的序列，第 $i$ 个数的值域范围是 $l_i,r_i$。

求所有可能的序列中，所有数出现次数平方和的最小可能的值。

做法

注意到每个位置 $i$ 都只能有一个数，并且这个数在 $[l_i,r_i]$ 之间，相当于位置 $i$ 可以为 $[l_i,r_i]$ 中的某个数贡献一次出现次数。

从这里可以想到网络流，由于最终每个数都要出现一次，考虑将原问题求的总代价作为费用，而最大流量设计为能有效安排的位置个数，这样保证了使用最小费用最大流可以在有解的情况下求出最小代价，当然，此时最大流是 $n$。

考虑一下发现，上述过程对应的是源点向每个位置 $i$ 连一条容量为 $1$，代价为 $0$ 的边，每个位置 $i$ 向数值 $[l_i,r_i]$ 连一条容量为 $1$，代价为 $0$ 的边。

由于每种数值 $j$ 的出现次数决定了最终代价，考虑每个数值 $j$ 向汇点连 $n$ 条容量为 $1$，费用分别为 $1^2-0^0,2^2-1^2,3^2-2^2,\cdots,n^2-(n-1)^2$ 的边。

然后跑最小费用最大流就行，我用的是 Dinic，用时 46ms。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x\/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=55;
int n,q;
int mx[maxn],mn[maxn];
struct EDGE{
    int to,nxt;
    int lim,cost;
}edge[maxn*maxn*6];
int head[maxn*2];
int cnt=1;
void _add(int u,int to,int lim,int cost){
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    edge[cnt].lim=lim;
    edge[cnt].cost=cost;
    head[u]=cnt;
}
void add(int u,int to,int lim,int cost){
	\/\/printf("%d -> %d\n",u,to);
    _add(u,to,lim,cost);
    _add(to,u,0,-cost);
}
int source=0,receive;
int dis[maxn*2];
int cur[maxn*2];
bool ins[maxn*2];
bool vis[maxn*2];
bool bfs(){
    queue<int> q;
    memset(dis,0x3f,sizeof dis);
    memcpy(cur,head,sizeof head);
	memset(vis,0,sizeof vis);
    q.push(source);
    dis[source]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ins[u]=0;
        for(int i=head[u];i;i=edge[i].nxt){
            int to=edge[i].to;
            if(edge[i].lim&&dis[to]>dis[u]+edge[i].cost){
                dis[to]=dis[u]+edge[i].cost;
                if(!ins[to]){
                    q.push(to),ins[to]=1;
                }
            }
        }
    }
    return (dis[receive]<=1e8);
}
int dfs(int u,int flow){
    if(!flow||u==receive)return flow;
    int used=0;
	vis[u]=1;
    for(int& i=cur[u];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(dis[to]==dis[u]+edge[i].cost&&!vis[to]&&edge[i].lim>0){
            int use=dfs(to,min(flow-used,edge[i].lim));
            edge[i].lim-=use;
            edge[i^1].lim+=use;
            used+=use;
        }
        
        if(used==flow)return used;
    }
    return used;
}
void Dinic(){
    int mxflow=0,totcost=0;
    while(bfs()){
        int nwflow=dfs(source,1e9);
        mxflow+=nwflow;
        totcost+=nwflow*dis[receive];
    }
    if(mxflow!=n){
        puts("-1");
    }else{
        printf("%d\n",totcost);
    }
}
void solve(int id_of_test){
	read(n);
    read(q);
    FOR(i,1,n){
        mn[i]=1,mx[i]=n;
    }
    receive=2*n+1;
    FOR(i,1,q){
        int t,l,r,v;
        read(t);
        read(l);
        read(r);
        read(v);
        if(t==1){
            FOR(j,l,r){
                ckmx(mn[j],v);
            }
        }else{
            FOR(j,l,r){
                ckmn(mx[j],v);
            }
        }
    }
    FOR(i,1,n){
        add(source,i,1,0);
    }
    FOR(i,1,n){
        FOR(j,mn[i],mx[i]){
            add(i,n+j,1,0);
        }
    }
    FOR(v,1,n){
        FOR(mult,1,n){
            add(v+n,receive,1,mult*mult-(mult-1)*(mult-1));
        }
    }
    Dinic();
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}