【LibreOJ】#6396. 「THUPC2018」弗雷兹的玩具商店 / Toyshop 线段树+完全背包

【题目】#6396. 「THUPC2018」弗雷兹的玩具商店 / Toyshop

【题意】给定一个长度为n的物品序列，每个物品有价值、不超过m的重量。要求支持以下三种操作：1.物品价值区间加减，2.物品重量区间加（超过m部分取模），3.区间物品求解容量为m的完全背包数组。\(n \leq 2*10^5,m \leq 60,Q \leq 3*10^4\)。

【算法】线段树+完全背包

显然，每个重量只需要保留价值最大的物品。

然后就很简单了，线段树每个维护一个数组c[x]表示重量x的最大价值，区间循环和区间加减，每次询问将区间m个重量的最大价值拿出来做完全背包。注意初始化为-inf（否则相当于有价值为0的物品，之后进行物品价值加减后就会干扰答案了）。

复杂度\(O(nm\ \ log\ \ n+m^2)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define lowbit(x) (x&-x)

bool isdigit(char c){return c>='0'&&c<='9';}

int read(){

	int s=0,t=1;char c;

	while(!isdigit(c=getchar()))if(c=='-')t=-1;

	do{s=s*10+c-'0';}while(isdigit(c=getchar()));

	return s*t;

}

using namespace std;

const int maxn=200010,M=70;

const ll inf=1ll<<60;

int n,m,w[maxn],v[maxn];

ll C[M],f[M],D[M];//chong fu X

struct tree{int l,r,w_delta,v_delta;ll c[M];}t[maxn*4];

ll max(ll a,ll b){return a<b?b:a;}

void up(int k){

	for(int i=1;i<=m;i++)t[k].c[i]=max(t[k<<1].c[i],t[k<<1|1].c[i]);

}

void w_modify(int k,int x){

	t[k].w_delta+=x;

	for(int i=1;i<=m;i++)D[(i-1+x)%m+1]=t[k].c[i];

	for(int i=1;i<=m;i++)t[k].c[i]=D[i];

}

void v_modify(int k,int x){

	t[k].v_delta+=x;

	for(int i=1;i<=m;i++)t[k].c[i]+=x;

}

void down(int k){

	if(t[k].w_delta){

		w_modify(k<<1,t[k].w_delta);w_modify(k<<1|1,t[k].w_delta);

		t[k].w_delta=0;

	}

	if(t[k].v_delta){

		v_modify(k<<1,t[k].v_delta);v_modify(k<<1|1,t[k].v_delta);

		t[k].v_delta=0;

	}

}

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

	for(int i=1;i<=m;i++)t[k].c[i]=-inf;//-inf no influense

	t[k].l=l;t[k].r=r;

	if(l==r){t[k].c[w[l]]=v[l];return;}//return

	int mid=(l+r)>>1;

	build(k<<1,l,mid);build(k<<1|1,mid+1,r);

	up(k);

}

void w_fix(int k,int l,int r,int x){

	if(l<=t[k].l&&t[k].r<=r){w_modify(k,x);return;}

	down(k);//

	int mid=(t[k].l+t[k].r)>>1;

	if(l<=mid)w_fix(k<<1,l,r,x);

	if(r>mid)w_fix(k<<1|1,l,r,x);

	up(k);

}

void v_fix(int k,int l,int r,int x){

	if(l<=t[k].l&&t[k].r<=r){v_modify(k,x);return;}

	down(k);//

	int mid=(t[k].l+t[k].r)>>1;

	if(l<=mid)v_fix(k<<1,l,r,x);

	if(r>mid)v_fix(k<<1|1,l,r,x);

	up(k);

}

void query(int k,int l,int r){

	if(l<=t[k].l&&t[k].r<=r){

		for(int i=1;i<=m;i++)C[i]=max(C[i],t[k].c[i]);

		return;//return

	}

	down(k);//use down

	int mid=(t[k].l+t[k].r)>>1;

	if(l<=mid)query(k<<1,l,r);

	if(r>mid)query(k<<1|1,l,r);

}

int main(){

	n=read();m=read();

	for(int i=1;i<=n;i++)w[i]=read();

	for(int i=1;i<=n;i++)v[i]=read();

	build(1,1,n);

	int Q=read();

	while(Q--){

		int kind=read(),l=read(),r=read();

		if(kind==1){

			int x=read();

			w_fix(1,l,r,x);

		}

		else if(kind==2){

			int x=read();

			v_fix(1,l,r,x);

		}

		else{

			for(int i=1;i<=m;i++)C[i]=0,f[i]=0;//long long

			query(1,l,r);

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

				for(int j=i;j<=m;j++){

					f[j]=max(f[j],f[j-i]+C[i]);

				}

			}

			ll ans=0;for(int i=1;i<=m;i++)ans+=f[i];printf("%lld ",ans);//long long

			ans=0;for(int i=1;i<=m;i++)ans^=f[i];printf("%lld\n",ans);

		}

	}

	return 0;

}

这种线段树套数组的做法经典而常见。

巴特西

【LibreOJ】#6396. 「THUPC2018」弗雷兹的玩具商店 / Toyshop 线段树+完全背包

最新文章

热门文章