提出问题并警示后人
查看原帖
提出问题并警示后人
491322
xyYyx楼主2023/8/19 21:17

以下是AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,q;
ll m;
ll arr[N*4];
ll stree[N*4];

struct node{
	ll add=0,mul=1;
}tag[N*4];

void build(ll root,ll l,ll r)
{
	if(l==r){
		stree[root]=arr[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	stree[root]=stree[root<<1]+stree[root<<1|1];//////////////
	stree[root]%=m;
}

void pushup(ll root)
{
	stree[root]=(stree[root<<1]+stree[root<<1|1])%m;
}

void pushdown(ll root,ll l,ll r)
{
	ll ls=root<<1,rs=root<<1|1,mid=(l+r)>>1;
	//左子树
	stree[ls]=(stree[ls]*tag[root].mul+tag[root].add*(mid-l+1))%m;
	tag[ls].mul=(tag[ls].mul*tag[root].mul)%m; 
	tag[ls].add=(tag[ls].add*tag[root].mul+tag[root].add)%m;
	//右子树
	stree[rs]=(stree[rs]*tag[root].mul+tag[root].add*(r-mid))%m; //更新节点 
	tag[rs].mul=(tag[rs].mul*tag[root].mul)%m;
	tag[rs].add=(tag[rs].add*tag[root].mul+tag[root].add)%m;//传递标记 
	
	tag[root].add=0,tag[root].mul=1;//重置 
	return;
}

ll query(ll ql,ll qr,ll nl,ll nr,ll root)
{
	if(nr<ql||nl>qr)	return 0;
	if(nr<=qr&&nl>=ql)	return stree[root];
	int mid=(nl+nr)>>1;
	ll res=0;
	pushdown(root,nl,nr);
	res+=query(ql,qr,nl,mid,root<<1);
	res+=query(ql,qr,mid+1,nr,root<<1|1);
	return res%m;
}

void updata_add(ll root,ll ul,ll ur,ll nl,ll nr,ll k)
{
	if(nl>ur||nr<ul)	return;
	if(ul<=nl&&nr<=ur)
	{
		stree[root]=(stree[root]+k*(nr-nl+1))%m;
		tag[root].add=(tag[root].add+k)%m;
		return;
	}
	pushdown(root,nl,nr);
	ll ls=root<<1,rs=root<<1|1,mid=(nl+nr)>>1;
	updata_add(ls,ul,ur,nl,mid,k);
	updata_add(rs,ul,ur,mid+1,nr,k);
	pushup(root);
}

void updata_mul(ll root,ll ul,ll ur,ll nl,ll nr,ll k)
{
	if(nr<ul||nl>ur)	return;
	ll ls=root<<1,rs=root<<1|1,mid=(nl+nr)>>1;
	if(ul<=nl&&nr<=ur)
	{
		stree[root]=stree[root]*k%m;
		tag[root].mul=tag[root].mul*k%m;
		tag[root].add=tag[root].add*k%m;
		return;
	}
	
	pushdown(root,nl,nr);
	
	updata_mul(ls,ul,ur,nl,mid,k);
	updata_mul(rs,ul,ur,mid+1,nr,k);
	pushup(root);
}

int main()
{
	scanf("%d%d%lld",&n,&q,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
	build(1,1,n);//////////
	for(int i=1;i<=q;i++)
	{
		int opt;
		scanf("%d",&opt);
		ll x,y;
		ll k;
		if(opt==1)
		{
			scanf("%d%d%lld",&x,&y,&k);
			updata_mul(1,x,y,1,n,k);
		}
		else if(opt==2)
		{
			scanf("%d%d%lld",&x,&y,&k);
			updata_add(1,x,y,1,n,k);
		}
		else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

以下是WA代码（在定义结构体的时候没有将add设为0）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,q;
ll m;
ll arr[N*4];
ll stree[N*4];

struct node{
	ll add,mul=1;
}tag[N*4];

void build(ll root,ll l,ll r)
{
	if(l==r){
		stree[root]=arr[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	stree[root]=stree[root<<1]+stree[root<<1|1];//////////////
	stree[root]%=m;
}

void pushup(ll root)
{
	stree[root]=(stree[root<<1]+stree[root<<1|1])%m;
}

void pushdown(ll root,ll l,ll r)
{
	ll ls=root<<1,rs=root<<1|1,mid=(l+r)>>1;
	//左子树
	stree[ls]=(stree[ls]*tag[root].mul+tag[root].add*(mid-l+1))%m;
	tag[ls].mul=(tag[ls].mul*tag[root].mul)%m; 
	tag[ls].add=(tag[ls].add*tag[root].mul+tag[root].add)%m;
	//右子树
	stree[rs]=(stree[rs]*tag[root].mul+tag[root].add*(r-mid))%m; //更新节点 
	tag[rs].mul=(tag[rs].mul*tag[root].mul)%m;
	tag[rs].add=(tag[rs].add*tag[root].mul+tag[root].add)%m;//传递标记 
	
	tag[root].add=0,tag[root].mul=1;//重置 
	return;
}

ll query(ll ql,ll qr,ll nl,ll nr,ll root)
{
	if(nr<ql||nl>qr)	return 0;
	if(nr<=qr&&nl>=ql)	return stree[root];
	int mid=(nl+nr)>>1;
	ll res=0;
	pushdown(root,nl,nr);
	res+=query(ql,qr,nl,mid,root<<1);
	res+=query(ql,qr,mid+1,nr,root<<1|1);
	return res%m;
}

void updata_add(ll root,ll ul,ll ur,ll nl,ll nr,ll k)
{
	if(nl>ur||nr<ul)	return;
	if(ul<=nl&&nr<=ur)
	{
		stree[root]=(stree[root]+k*(nr-nl+1))%m;
		tag[root].add=(tag[root].add+k)%m;
		return;
	}
	pushdown(root,nl,nr);
	ll ls=root<<1,rs=root<<1|1,mid=(nl+nr)>>1;
	updata_add(ls,ul,ur,nl,mid,k);
	updata_add(rs,ul,ur,mid+1,nr,k);
	pushup(root);
}

void updata_mul(ll root,ll ul,ll ur,ll nl,ll nr,ll k)
{
	if(nr<ul||nl>ur)	return;
	ll ls=root<<1,rs=root<<1|1,mid=(nl+nr)>>1;
	if(ul<=nl&&nr<=ur)
	{
		stree[root]=stree[root]*k%m;
		tag[root].mul=tag[root].mul*k%m;
		tag[root].add=tag[root].add*k%m;
		return;
	}
	
	pushdown(root,nl,nr);
	
	updata_mul(ls,ul,ur,nl,mid,k);
	updata_mul(rs,ul,ur,mid+1,nr,k);
	pushup(root);
}

int main()
{
	scanf("%d%d%lld",&n,&q,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
	build(1,1,n);//////////
	for(int i=1;i<=q;i++)
	{
		int opt;
		scanf("%d",&opt);
		ll x,y;
		ll k;
		if(opt==1)
		{
			scanf("%d%d%lld",&x,&y,&k);
			updata_mul(1,x,y,1,n,k);
		}
		else if(opt==2)
		{
			scanf("%d%d%lld",&x,&y,&k);
			updata_add(1,x,y,1,n,k);
		}
		else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

然而WA代码的输出结果似乎是正确的（下载了一个数据 是正确的 并且能过样例）在洛谷IDE运行似乎也是正确的 然而为什么会WA呢？

2023/8/19 21:17