蒟蒻C++样例未过求助
查看原帖
蒟蒻C++样例未过求助
722468
MrJC_Pandingding楼主2023/6/27 16:50
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
struct node
{
	int ad,ls,rs,tim,sumn;
}b[maxn+10];
int i,m,n,w,tot,x,y;
bool a[maxn+10];
void bld(int&q,int lt,int rt)
{
	int md=lt+rt>>1;
	if(!q)
		q=++tot;
	if(lt==rt)
	{
		b[q].sumn=a[lt];
		return;
	}
	bld(b[q].ls,lt,md);
	bld(b[q].rs,md+1,rt);
	b[q].sumn=b[b[q].ls].sumn+b[b[q].rs].sumn;
	return;
}
void pushtms(int q,int lt,int rt,int md);
void add(int q,int lt,int rt,int v)
{
	pushtms(1,lt,rt,lt+rt>>1);
	b[q].ad+=v;
	b[q].sumn+=1ll*v*(rt-lt+1);
	return; 
}
void tms(int q,int lt,int rt,int v)
{
	b[q].tim*=v;
	b[q].sumn*=v;
	b[q].ad*=v;
	return;
}
void pushdn(int q,int lt,int rt,int md)
{
	if(!b[q].ad)
		return;
	add(b[q].ls,lt,md,b[q].ad);
	add(b[q].rs,md+1,rt,b[q].ad);
	b[q].ad=0;
	return;
}
void pushtms(int q,int lt,int rt,int md)
{
	if(b[q].tim==1)
		return;
	tms(b[q].ls,lt,md,b[q].tim);
	tms(b[q].rs,md+1,rt,b[q].tim);
	b[q].tim=1;
	return;
}
long long qry(int q,int lt,int rt,int x,int y)
{
	int md=lt+rt>>1;
	long long ans=0;
	if(lt>=x&&rt<=y)
		return b[q].sumn;
	pushtms(q,lt,rt,md);
	pushdn(q,lt,rt,md);
	if(x<=md)
		ans+=qry(b[q].ls,lt,md,x,y);
	if(md<=y-1)
		ans+=qry(b[q].rs,md+1,rt,x,y);
	return ans;
}
void mdf(int q,int lt,int rt,int x,int y,long long v)
{
	int md=lt+rt>>1;
	if(lt>=x&&rt<=y)
	{
		add(q,lt,rt,v);
		return;
	}
	pushtms(q,lt,rt,md);
	pushdn(q,lt,rt,md);
	if(x<=md)
		mdf(b[q].ls,lt,md,x,y,v);
	if(md<=y-1)
		mdf(b[q].rs,md+1,rt,x,y,v);
	b[q].sumn=b[b[q].ls].sumn+b[b[q].rs].sumn;
	return;
}
void mdftms(int q,int lt,int rt,int x,int y,long long v)
{
	int md=lt+rt>>1;
	if(lt>=x&&rt<=y)
	{
		tms(q,lt,rt,v);
		return;
	}
	pushtms(q,lt,rt,md);
	pushdn(q,lt,rt,md);
	if(x<=md)
		mdftms(b[q].ls,lt,md,x,y,v);
	if(md<=y-1)
		mdftms(b[q].rs,md+1,rt,x,y,v);
	b[q].sumn=b[b[q].ls].sumn+b[b[q].rs].sumn;
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	bld(b[0].ls,1,n);
	for(i=1;i<=n;++i)
		a[i]=1;
	for(i=1;i<=n<<1;++i)
		b[i].tim=1;
	while(m--)
	{
		scanf("%d%d%d",&x,&y,&w);
		mdftms(1,1,n,x,y,0);
		if(w==2)
			mdf(1,1,n,x,y,1);
		printf("%lld\n",qry(1,1,n,1,n));
	}
	return 0;
}

我的输出:

0
0
2
3
1
4

不知道第一个输出为何不对,大佬帮帮我,悬赏关注。

2023/6/27 16:50
加载中...