P4497 [WC2011]拼点游戏

P4497 [WC2011]拼点游戏

在我的 cnblogs 中查看

数据结构大杂烩 + 阿巴细节题。

调了三个小时。

首先考虑第一小问的答案。

注意到点数的计算方式是先负后正的形式，不妨看做选出 \(2k\) 个数 \(p_1,p_2,\cdots,p_{2k}\)，从小到大排序后计算 \(\sum u_{p_{2i}-p_{2i-1}}\)。再根据题目的区间修改操作，不难想到使用差分：

设 \(d_i=u_i-u_{i-1}\)，舍去 \(d_1\) 后得到一个长度为 \(n-1\) 的序列 \(d_2,d_3,\cdots,d_n\)。不难发现，选择一段连续的 \(d\) 并求和就相当于选择两个端点对应的 \(u\) 求差，即 \(d_l+d_{l+1}+\cdots+d_r=u_r-u_{l-1}\)。可以证明任何一种 \(d\) 中的选数方式都对应了 \(u\) 中的一种选数方式，故题目转化为在 \(d\) 中选出若干不相邻子段，求选出的数的和的最大值。

因此，为了让得分最大，我们只选取所有大于 \(0\) 的 \(d\) 即可，即 \(\sum_{i=2}^n\max(0,d_i)\)。

不妨设最终选取的 \(d\) 中的数的区间为 \([l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]\)。考虑小 Y（不是小 W）的修改操作的本质：选取两个编号相邻（不是在 \(d\) 中相邻）的区间 \([a,b],[c,d]\ (a\leq b<c\leq d,b+1<c)\)，将 \(b,c\) 分别换成任意 \(z_1,z_2\in [b,c]\) 满足 \(z_1+1<z_2\)。

为了让减小的得分最多且最终两区间端点不相邻，又因为 \((b,c)\) 中全是非正数，故留下最大的那一个数即可。得分的减少量即为区间 \((b,c)\) 的和减去它的最大值，即 \(\left(\sum_{i=b+1}^{c-1}d_i\right)-\left(\max_{i=b+1}^{c-1}d_i\right)\)。

例如 positive integer | -6 | -5 | -7 | -8 | positive integers，我们就可以将 \(b\gets b+1\)，\(c\gets c-2\)，此时得分减小 \(6+7+8=21\)，是最优的。

如果我们选了 \(m\) 个这样的区间，那么它们之间就有 \(m-1\) 个空隙可以用来减小分数。对于这 \(m-1\) 个空隙，分别计算它的得分最大减少量并丢到平衡树 or 动态开点线段树上。每个节点记录落在该区间的数的个数以及它们的和，则最终可以通过线段树上二分（原理类似主席树求区间第 k 小）求出答案。

同时，对于操作 \(1\)，我们通过差分将其转化为了两次单点修改，而单点修改对于选择的区间的影响是 \(\mathcal{O}(1)\) 的，于是我们可以暴力 \(\log n\) 重新计算被影响的区间的答案即可。因为我们只关心 “被选择区间” 之间形成的 “空隙区间” 的信息，前者只需求和，所以记录后者即可。具体地，用线段树维护区间最大值与区间和，并用 set 维护 “空隙区间” 的端点信息，方便修改。

时间复杂度为 \(Tn\log n\sim Tn\log w\)，其中 \(w\) 为值域。

当然，说起来轻巧，实现却并不简单。有亿些细节需要注意：都是踩过的坑啊。

最后查询答案，在线段树上跑到叶子结点时，返回的不是该叶子结点维护的数的个数，而应该是 “剩余需要减少的得分” 除以 “该节点所表示的得分减少值” 上取整。这个错误太经典了。
区间端点为 \(2\)（代码中为 \(1\)）“非正整数值区间” 尽管不在两个 “被选择区间” 的中间，但也需要维护，因为若区间内部有一个位置变为正数，则该区间会裂开来分裂成左边的端点为 \(2\) 的区间和右边的 “空隙区间”。端点为 \(n\) 的情况同理。
老老实实更新第一问的答案！不要投机取巧，踏踏实实地减去原贡献，加上新贡献。
若一个位置从非正整数变为了非正整数，这并不意味着不需要修改，因为包含该位置的区间的和与最大值都改变了，所以 “得分减少量最大值” 也改变了。
Testcase 6,7 可能会出现相邻两个数相等的情况，即出现 \(d_i=0\)。辣鸡出题人用脚造数据。思考一下这种情况 \(d_i\) 究竟要不要选上。

实际上，如果要使第二问答案最小，是不应该选 \(0\) 的。考虑 \(5\) 个相邻的数 \(a,b,c,d,e\)，其中 \(a,e>0\)，\(b,d<0\)，\(c=0\)。如果 \(c\) 不被选，那么 \(b,c,d\) 为一个空隙区间，得分减少量为 \(|b+d|\)。但如果 \(c\) 被选，那么尽管不影响第一问答案，但会导致空隙区间分裂为 \(b\) 和 \(d\) 两个，此时得分减少量为 \(0\)（因为只有一个数的区间的和与最大值就是区间所含的这个数本身，相减即为 \(0\)），显然不优。因此 \(0\) 不应该选。

吐槽一句：选不选 \(0\) 不应该是小 X 的事情么？什么时候轮到小 Y 来决定选什么了（笑）。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define mem(x,v) memset(x,v,sizeof(x))

#define pii pair <int,int>

#define fi first

#define se second

const int N=1e5+5;

const ll W=1ll<<31;

ll n,q,ans,u[N],d[N];

// SegTree 1

ll mval[N<<2];

void build(int l,int r,int x){

	if(l==r)return mval[x]=d[l],void();

	int m=l+r>>1;

	build(l,m,x<<1),build(m+1,r,x<<1|1);

	mval[x]=max(mval[x<<1],mval[x<<1|1]);

}

void modify(int l,int r,int p,int x,ll v){

	if(l==r)return mval[x]=v,void();

	int m=l+r>>1;

	if(p<=m)modify(l,m,p,x<<1,v);

	else modify(m+1,r,p,x<<1|1,v);

	mval[x]=max(mval[x<<1],mval[x<<1|1]);

}

ll query(int l,int r,int ql,int qr,int x){

	if(ql<=l&&r<=qr)return mval[x];

	ll m=l+r>>1,ans=-W;

	if(ql<=m)ans=max(ans,query(l,m,ql,qr,x<<1));

	if(m<qr)ans=max(ans,query(m+1,r,ql,qr,x<<1|1));

	return ans;

}

// BIT

ll c[N];

void add(int x,ll v){while(x<=n)c[x]+=v,x+=x&-x;}

ll query(int x){ll s=0; while(x)s+=c[x],x-=x&-x; return s;}

ll query(int l,int r){return query(r)-query(l-1);}

// end points

set <pii> s;

ll cont[N];

// SegTree 2

ll R,node,ls[N<<6],rs[N<<6],val[N<<6],sum[N<<6];

void insert(ll l,ll r,ll p,ll &x,bool tp){

	if(!x)x=++node;

	if(tp)sum[x]++,val[x]+=p-W;

	else sum[x]--,val[x]-=p-W;

	if(l==r)return;

	ll m=l+r>>1;

	if(p<=m)insert(l,m,p,ls[x],tp);

	else insert(m+1,r,p,rs[x],tp);

}

ll query(ll l,ll r,ll k,ll x){

	if(!x)return -W;

	if(l==r)return k+val[x]<=0?((k-1)/(W-l)+1):-W;

	ll m=l+r>>1;

	if(k+val[ls[x]]<=0)return query(l,m,k,ls[x]);

	return sum[ls[x]]+query(m+1,r,k+val[ls[x]],rs[x]);

}

void clear(pii x){

	if(x.fi==1||x.se==n-1)return;

	insert(1,W,cont[x.fi]+W,R,0),cont[x.fi]=0;

}

void update(int l,int r){

	if(l==1||r==n-1)return;

	cont[l]=query(l,r)-query(1,n,l,r,1);

	insert(1,W,cont[l]+W,R,1);

}

// update changes

void change(int pos,ll &val,ll add){

	auto it=s.upper_bound({pos,N});

	// update end points and contribution

	if(val<=0&&val+add>0){

		ans+=val+add;

		pii x=*--it; clear(x),s.erase(x);

		if(x.fi==x.se)return val+=add,void();

		else if(x.fi==pos)s.insert({++x.fi,x.se}),update(x.fi,x.se);

		else if(pos==x.se)s.insert({x.fi,--x.se}),update(x.fi,x.se);

		else{

			s.erase(x);

			s.insert({x.fi,pos-1}),update(x.fi,pos-1);

			s.insert({pos+1,x.se}),update(pos+1,x.se);

		}

	}

	else if(val>0&&val+add<=0){

		ans-=val;

		pii x={pos,pos};

		if(it!=s.begin()){

			pii tmp=*(--it); it++;

			if(tmp.se==pos-1)clear(tmp),s.erase(tmp),x.fi=tmp.fi;

		} if(it!=s.end()){

			pii tmp=*it;

			if(tmp.fi==pos+1)clear(tmp),s.erase(tmp),x.se=tmp.se;

		} s.insert(x),update(x.fi,x.se);

	} else if(val<=0&&val+add<=0)it--,clear(*it),update((*it).fi,(*it).se);

	else ans+=add; val+=add;

}

void solve(){

	// empty

	mem(c,0),mem(cont,0),s.clear(),ans=0;

	R=node,mem(ls,0),mem(rs,0),mem(val,0),mem(sum,0);

	// read

	cin>>n>>q>>u[0];

	for(int i=1;i<n;i++){

		cin>>u[i],d[i]=u[i]-u[i-1];

		if(d[i]>0)ans+=d[i];

		add(i,d[i]);

	} build(1,n,1);

	// find end points [l,r)

	for(int i=1,pre=1;i<n;i++){

		if(d[i]<=0&&d[i-1]>0)pre=i;

		if(d[i]>0&&d[i-1]<=0){

			s.insert({pre,i-1});

			if(pre!=1)update(pre,i-1);

		} if(i==n-1&&d[i]<=0)s.insert({pre,n-1});

	}

	// answer all the queries

	for(int i=1;i<=q;i++){

		int op; cin>>op;

		if(op==0){

			ll l,r,c; cin>>l>>r>>c,l--,r--;

			// modify SegTree 1 & BIT then update answer

			if(l)add(l,c),modify(1,n,l,1,d[l]+c),change(l,d[l],c);

			if(r+1<n)add(r+1,-c),modify(1,n,r+1,1,d[r+1]-c),change(r+1,d[r+1],-c);

		}

		else cout<<ans<<" "<<(ans?max(-1ll,query(1,W,ans,R)):0)<<endl;

	}

}

int main(){

	int T; cin>>T;

	while(T--)solve();

	return 0;

}

巴特西

P4497 [WC2011]拼点游戏

最新文章

热门文章