方糖
TTpandaS
·
·
题解
方糖并不想被吃掉，所以（迟到地）给大家送来方糖社的新春祝福：
求最大匹配，利用扩展霍尔定理：一个任意二分图 (V1,V2,E)，最大匹配为 |V1|-\max_{S \in V1}(|S|-|N(S)|)。|V1| 即为 \sum [T_i=1]A_i，S 即为一些区间的蚂蚁的并，设为 \cup [l_i,r_i]，那么 N(S) 即为这些区间向两边扩展 L 的区间的并，设为 \cup [l_i-L,r_i+L]。两个相邻区间间隔大于 2L，否则将两个区间合并为一个区间更优。
$$\sum \sum_{j=l_i}^{r_i}a_j-\sum_{j=l_i-L}^{r_i+L}s_j=\sum \sum_{j=l_i}^{r_i}(a_j-\sum_{k=j-L}^{j+L}s_k)+\sum_{j=l_i}^{r_i-1}\sum_{k=j-L+1}^{j+L}s_k$$
令 $j \in [l_i,r_i]$ 表示 $j$ 被选择，设 $dp_{l,r,0/1,0/1}$ 表示区间 $[l,r]$ 左端点和右端点是否被选择时的最大值。可以用线段树进行维护，同时为了合并左右儿子，对于每个区间 $(l,r,mid)$ 还需要维护
$$\sum_{k=mid-L+1}^{mid+L}s_k $$
的值。修改时注意 $dp_{l,r,0,0} \geq 0$。
加入蚂蚁时，对 $X_i$ 位置单点加即可。
加入方糖时，会影响 $[X_i-L,X_i+L]$ 这个区间的 dp 值。具体地，如果区间 $(l,r,mid) \subseteq [X_i-L,X_i+L]$，那么 dp 值均会减少，而
$$\sum_{k=mid-L+1}^{mid+L}s_k $$
的值会增加。此外，如果 $X_i-L\leq mid < X_i+L$，那么该区间的
$$\sum_{k=mid-L+1}^{mid+L}s_k $$
值也会增加。
实现需要离散化。
```cpp
#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=5e5+5,inf=0x0d0007210d000721;
struct tree{
int l,r,val,tag;
int dp[2][2];
}t[N*4];
void pushup(int p){
for(int x=0;x<=1;x++){
for(int y=0;y<=1;y++){
t[p].dp[x][y]=-inf;
}
}
for(int x1=0;x1<=1;x1++){
for(int y1=0;y1<=1;y1++){
for(int x2=0;x2<=1;x2++){
for(int y2=0;y2<=1;y2++){
t[p].dp[x1][y2]=max(t[p].dp[x1][y2],t[lc].dp[x1][y1]+t[rc].dp[x2][y2]+(y1&x2)*t[p].val);
}
}
}
}
}
void add(int p,int val){
t[p].val+=val;
t[p].tag+=val;
for(int x=0;x<=1;x++){
for(int y=0;y<=1;y++){
t[p].dp[x][y]-=val;
}
}
t[p].dp[0][0]=max(t[p].dp[0][0],0ll);
}
void pushdown(int p){
if(t[p].tag){
add(lc,t[p].tag);
add(rc,t[p].tag);
t[p].tag=0;
}
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
return;
}
int mid=(t[p].l+t[p].r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void addg(int p,int x,int y){
if(t[p].l==t[p].r){
t[p].dp[1][1]+=y;
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid){
addg(lc,x,y);
}
else{
addg(rc,x,y);
}
pushup(p);
}
void addf(int p,int l,int r,int x){
if(l>r){
return;
}
if(l<=t[p].l&&t[p].r<=r){
add(p,x);
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid){
addf(lc,l,r,x);
}
if(mid+1<=r){
addf(rc,l,r,x);
}
if(l<=mid&&mid+1<=r){
t[p].val+=x;
}
pushup(p);
}
int Q,L;
int lsh[N],lshcnt;
struct opt{
int t,x,a;
}o[N];
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>Q>>L;
lshcnt=1;
for(int i=1;i<=Q;i++){
cin>>o[i].t>>o[i].x>>o[i].a;
if(o[i].t==1){
lsh[++lshcnt]=o[i].x;
}
}
sort(lsh+1,lsh+lshcnt+1);
lshcnt=unique(lsh+1,lsh+lshcnt+1)-lsh-1;
build(1,1,lshcnt);
for(int i=1;i<=Q;i++){
if(o[i].t==1){
ans+=o[i].a;
int pos=lower_bound(lsh+1,lsh+lshcnt+1,o[i].x)-lsh;
addg(1,pos,o[i].a);
}
else{
int posl=lower_bound(lsh+1,lsh+lshcnt+1,o[i].x-L)-lsh,posr=upper_bound(lsh+1,lsh+lshcnt+1,o[i].x+L)-lsh-1;
addf(1,posl,posr,o[i].a);
}
cout<<ans-max(max(t[1].dp[0][0],t[1].dp[0][1]),max(t[1].dp[1][0],t[1].dp[1][1]))<<'\n';
}
return 0;
}
```