ARC190E

一个全新的领域！

众所周知，二分图最大匹配为：

|V_{L}|-\max_{S\in V_L}(|S|-|N(S)|)

，霍尔定理推论。

霍尔定理相关题目已经出了很多很多，诞生了许多好题。

聪明的出题人一定不会满足于此，走向全新的领域：一般图！

一般图最大匹配为：

\frac{1}{2} (|V|-\max_{S\in V}(O(V-S)-|S|))

，其中

O(V-S)

表示把图扣去集合

S

中的点之后大小为奇数的连通块个数，在学术上被称作：Tutte-Berge Formula。证明部分略去，有兴趣自行了解（我还不太会，待学习）

言归正传，那么本题先可以简单得建立出一般图最大匹配模型：两个距离小于等于

2

的点之间连一条边，保留区间中的所有点，跑最大匹配。

那么我们现在只用考虑求

\max_{S\in V}O(V-S)-|S|

。

注意到这里是带权的最大匹配（每个点包含了

a_i

个点），可以发现一个点要么全部选入

S

，要么全没有选入

S

，具体而言，假设最终

S

中选了

0< x <a_i

个点，那么调整成选

x-1

个点一定不劣。

不妨设

d_i=1/0

表示下标

i

的所有点选/没选入

S

，考虑设计

dp

转移。

不妨设区间长度为

m

，以及

d_0=d_{m+1}=1

，方便处理边界。

首先答案为奇

0

连通块个数减去所有

1

的带权和，当然会有细节需要你考虑。

当一个

0

形成一个独立连通块时，贡献为

a_i

并非

1

（每个点都是孤立的）

000100

出现时即中间只有一个

1

间断两边的

0

其实是一个连通块，这种情况是烦人的，但是你直接钦定全局不能出现这种情况即可（有支配性：不如把

1

改为

0

，可调整证明）

a_i=0

的时候是不能选

d_i=1

的，但是

d_i=0

不劣于

d_i=1

的，所以不需要特殊处理。

然后就可以

dp

转移了，设

f_{i,0/1/2/3/4}

表示当前考虑了

1\sim i

，

i

号点当前状态为：单独的一个

1

，在多个

1

的连通块内，单独的一个

0

，在多个

0

的联通块内且当前连通块大小为偶数/奇数。

列出矩阵（max+）做转移即可，细节看代码。

复杂度

O((n+q\log)K^3)

，

K

为矩阵大小，本题还能支持单点修改。

一道很牛牛的题，感觉这个结论扩展性极强，期待下一次遇见。

CPP

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=2e5+3,K=5,INF=1e18;
ll n,m,a[N],sa[N];
void Max(ll &x,ll y){if(x<y)x=y;}
struct Mat
{
	array<ll,K>f[K];
	auto& operator[](int x){return f[x];}
	void Clear(){memset(f,0xcf,sizeof(f));}
	friend Mat operator *(Mat A,Mat B)
	{
		Mat C;C.Clear();
		for(int i=0;i<K;i++)for(int k=0;k<K;k++)for(int j=0;j<K;j++)
			Max(C[i][j],A[i][k]+B[k][j]);
		return C;
	}
}I;
void Init(){for(int i=0;i<K;i++)for(int j=0;j<K;j++)I[i][j]=i==j?0:-INF;}
Mat Get(ll v)
{
	Mat A;
	if(v%2==0)
	{
		A[0]={-INF,-v,-INF,-INF,-INF};
		A[1]={-INF,-v,v,0,-INF};
		A[2]={-v,-INF,-INF,-INF,-INF};
		A[3]={-v,-INF,-INF,0,-INF};
		A[4]={-v,-INF,-INF,-INF,0};
	}
	else
	{
		A[0]={-INF,-v,-INF,-INF,-INF};
		A[1]={-INF,-v,v,-INF,1};
		A[2]={-v,-INF,-INF,-INF,-INF};
		A[3]={-v,-INF,-INF,-INF,1};
		A[4]={-v,-INF,-INF,-1,-INF};
	}
	return A;
}
struct SGT
{
	int DT;Mat tr[1<<19|3];
	void Up(int p){tr[p]=tr[p<<1]*tr[p<<1|1];}
	void Build()
	{
		DT=1<<(__lg(n)+1);
		for(int i=1;i<=n;i++)tr[i+DT]=Get(a[i]);
		for(int i=DT-1;i;i--)Up(i);
	}
	Mat Ask(int l,int r)
	{
		Mat sl=I,sr=I;
		for(l+=DT-1,r+=DT+1;l+1!=r;l>>=1,r>>=1)
		{
			if(~l&1)sl=sl*tr[l+1];
			if(r&1)sr=tr[r-1]*sr;
		}
		return sl*sr;
	}
}T;
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;Init(); 
	for(int i=1;i<=n;i++)cin>>a[i],sa[i]=sa[i-1]+a[i];
	T.Build();
	for(int i=1,l,r;i<=m;i++)
	{
		cin>>l>>r;Mat t=T.Ask(l,r);
		ll ans=*max_element(t[1].begin(),t[1].end());
		cout<<(sa[r]-sa[l-1]-ans)/2<<"\n";
	}
}

文章操作

相关推荐

评论

ARC190E