社区讨论

萌新求助,线段树莫名全输出0

P1558色板游戏参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi7yznc2
此快照首次捕获于
2025/11/21 05:55
4 个月前
此快照最后确认于
2025/11/21 05:55
4 个月前
查看原帖
RT,思路:建30棵线段树。。。
CPP
#include <bits/stdc++.h>

using namespace std;
int n,m,k;
struct Node
{
	int l,r,la;
	int mx;
}t[35][100005];
void BuildT(int it,int id,int l,int r)
{
	t[it][id].l=l;
	t[it][id].r=r;
	t[it][id].la=0;
	t[it][id].mx=0;
	if(l==r)
	{
		return;
	}
	int Mid=(l+r)/2;
	BuildT(it,id*2,l,Mid);
	BuildT(it,id*2+1,Mid+1,r);
}
void Push(int it,int id)
{
    if(t[it][id].la)
    {
        t[it][id*2].la+=t[it][id].la;
        t[it][id*2+1].la+=t[it][id].la;
        t[it][id].mx+=t[it][id].la*(t[it][id].r-t[it][id].l+1);
        t[it][id].mx=max(t[it][id].mx,0);
        t[it][id].la=0;
    }
}
void Max(int it,int id,int l,int r,int c)
{
	cout << it << " " << id << " " << t[it][id].l << " " << t[it][id].r << " " << l << " " << r <<endl;
	if(t[it][id].l==l&&t[it][id].r==r)
	{
		t[it][id].la+=c;
		Push(it,id);
		return;
	}
	Push(it,id);
	if(t[it][id*2].r>=r)
	{
		Max(it,id*2,l,r,c);
	}
	else if(t[it][id*2+1].l<=l)
	{
		Max(it,id*2+1,l,r,c);
	}
	else
	{
		Max(it,id*2,l,t[it][id*2].r,c);
		Max(it,id*2+1,t[it][id*2+1].l,r,c);
	}
}
int Query(int it,int id,int l,int r)
{
	Push(it,id);
	if(t[it][id].l==l&&t[it][id].r==r)
	{
		return t[it][id].mx;
	}
	if(t[it][id*2].r>=r)
	{
		return Query(it,id*2,l,r);
	}
	else if(t[it][id*2+1].l<=l)
	{
		return Query(it,id*2+1,l,r);
	}
	else
	{
		return Query(it,id*2,l,t[it][id*2].r)+Query(it,id*2+1,t[it][id*2+1].l,r);
	}
}

int main()
{	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;++i)
	{
		BuildT(i,1,1,n);
	}
//	for(int i=1;i<=m;++i)
//	{
//		for(int j=1;j<=4*n;++j)
//		{
//			printf("%d %d %d\n",t[i][j].l,t[i][j].r,t[i][j].mx);
//		}
//		printf("\n\n");
//	}
	Max(1,1,n,n,1);
	while(k--)
	{
		char c;
		int x,y,z;
		cin >> c;
		scanf("%d%d",&x,&y);
		if(c=='C')
		{
			scanf("%d",&z);
			Max(z,1,x,y,1);
			for(int i=1;i<=m;++i)
			{
				if(i==z)
				{
					continue;
				}
				Max(i,1,x,y,-1);
			}
		}
		else
		{
			int ans=0;
			for(int i=1;i<=n;++i)
			{
				if(Query(i,1,x,y)!=0)
				{
					ans++;
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...