JOISC 2022 Day3 Ants and Sugar

先利用霍尔定理，将问题转化为一个 dp 问题，我们在线段树上用矩阵维护 dp 。现在问题在于我们如何处理加点操作。可以发现每个点的两个权值分别为 \(sum1[i]-sum2[i+L]\) ，\(sum2[i-L-1]-sum1[i-1]\) 。

分开考虑上下两种点集的加点操作。

• 如果是下点集（\(sum1\)）的加点操作。就是一个后缀的 一维权值加上 \(w\) ，另一维权值减去 \(w\) 的 修改，我们称之为 整体修改 。考虑到这种修改是不会影响到后缀内部的决策的，只能影响权值，我们考虑直接打 tag 即可。而只有跨该点的区间的决策才会被影响到，而这些区间只有 \(\log\) 个，直接维护即可。

• 如果是上点集（\(sum2\)）的加点操作，我们可以看成一个后缀 整体权值 修改和一个区间的 部分权值修改（即仅有一个维度修改）。前者与上一种情况同理，而后者我们考虑这个区间的长度是只有 \(2L\) 的，因此内部并不会出现 \(f[1][0]\) 的最优情况，所以所有的剩余情况都是单个的，也不会影响决策，所以直接修改即可。

/*
我要是不原谅我自己，就没人原谅我，我得自己原谅我自己。
												——zhuo
*/

#include
using namespace std;

const int N=5e5+5,A=1e9;
const long long INF=1e18;

void cmax(long long &a,long long b){if(ab)a=b;}

int q,L;long long tot=0;

//空白节点可能查询，需要修改。
struct seg_tree{
	int rt,tot;
	struct Node{int ls,rs;long long f;}tr[N*30];
	void modify(int &u,int l,int r,int x,int y,long long z){
		if(!u) u=++tot;
		if(x<=l&&r<=y) return tr[u].f+=z,void();
		int mid=(l+r)>>1;
		if(x<=mid) modify(tr[u].ls,l,mid,x,y,z);
		if(y>mid) modify(tr[u].rs,mid+1,r,x,y,z);
	}
	long long query(int u,int l,int r,int x){
		if(!u) return 0;
		if(l==r) return tr[u].f;
		int mid=(l+r)>>1;
		if(x<=mid) return tr[u].f+query(tr[u].ls,l,mid,x);
		else return tr[u].f+query(tr[u].rs,mid+1,r,x);
	}
}t1,t2;

struct Data{long long f[2][2];};
Data operator + (Data a,Data b){
	Data res={{{-INF,-INF},{-INF,-INF}}};
	cmax(res.f[0][0],max(a.f[0][0],b.f[0][0]));
	cmax(res.f[0][0],max(a.f[0][0]+b.f[1][0],a.f[0][1]+b.f[0][0]));

	cmax(res.f[0][1],max(a.f[0][1],b.f[0][1]));
	cmax(res.f[0][1],max(a.f[0][0]+b.f[1][1],a.f[0][1]+b.f[0][1]));

	cmax(res.f[1][0],max(a.f[1][0],b.f[1][0]));
	cmax(res.f[1][0],max(a.f[1][0]+b.f[1][0],a.f[1][1]+b.f[0][0]));

	cmax(res.f[1][1],max(a.f[1][1],b.f[1][1]));
	cmax(res.f[1][1],max(a.f[1][0]+b.f[1][1],a.f[1][1]+b.f[0][1]));
	return res;
}

//空白节点无意义，无需修改。
struct Seg_Tree{
	int rt,tot;
	struct Node{Data f;int ls,rs;long long tag1,tag2;}tr[N*30];
	Seg_Tree(){tr[0].f={{{-INF,-INF},{-INF,-INF}}};}
	void up(int u){
		tr[u].f=tr[tr[u].ls].f+tr[tr[u].rs].f;
	}
	void update(int u,long long z1,long long z2){
		if(!u) return ;
		tr[u].f.f[1][1]+=z1,tr[u].f.f[0][0]-=z1,tr[u].tag1+=z1;
		tr[u].f.f[1][1]+=z2,tr[u].f.f[0][1]+=z2,tr[u].tag2+=z2;
	}
	void down(int u){
		update(tr[u].ls,tr[u].tag1,tr[u].tag2);
		update(tr[u].rs,tr[u].tag1,tr[u].tag2);
		tr[u].tag1=tr[u].tag2=0;
	}
	void insert(int &u,int l,int r,int x){
		if(!u) u=++tot,tr[u]=tr[0];
		if(l==r){
			tr[u].f.f[1][1]=t1.query(1,-1,A,x)-t2.query(1,-1,A,x+L);
			tr[u].f.f[0][0]=t2.query(1,-1,A,x-1-L)-t1.query(1,-1,A,x-1);
			tr[u].f.f[0][1]=tr[u].f.f[0][0]+tr[u].f.f[1][1];
			return ;
		}
		int mid=(l+r)>>1;down(u);
		if(x<=mid) return insert(tr[u].ls,l,mid,x),up(u);
		else return insert(tr[u].rs,mid+1,r,x),up(u);
	}
	void modify(int u,int l,int r,int x,int y,long long z1,long long z2){
		if(!u||x>y) return ;
		if(x<=l&&r<=y) return update(u,z1,z2);
		int mid=(l+r)>>1;down(u);
		if(x<=mid) modify(tr[u].ls,l,mid,x,y,z1,z2);
		if(y>mid) modify(tr[u].rs,mid+1,r,x,y,z1,z2);
		return up(u);
	}
}t;

int main(){
	// freopen("1.in","r",stdin);

	cin>>q>>L;
	
	for(int i=1;i<=q;++i){
		int opt,x,a;scanf("%d%d%d",&opt,&x,&a);

		if(opt==1){
			t1.modify(t1.rt,-1,A,x,A,a);
			t.modify(t.rt,0,A,x+1,A,a,0),t.insert(t.rt,-1,A,x),tot+=a;
		}
		else{
			t2.modify(t2.rt,-1,A,x,A,a);
			t.modify(t.rt,-1,A,x+L+1,A,-a,0),t.modify(t.rt,-1,A,x-L,x+L,0,-a);
		}

		printf("%lld\n",tot-max(0ll,t.tr[t.rt].f.f[0][1]));
	}

	return 0;
}