ARC190E
Hanghang
·
·
题解
一个全新的领域！
众所周知，二分图最大匹配为：|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（每个点都是孤立的）
$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";
}
}
```