自动搬运

查看原文

来自洛谷，原作者为

	颓_废_人 这个人很勤快，什么都来不及留下...

搬运于2025-08-24 21:43:32，当前版本为作者最后更新于2019-09-13 11:41:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

线段树？ 不用吧

还是要分成C个序列来处理
我的思路是将每个序列分成k个颜色相同的块，然后每个块都算一下有几个满足要求就行了。
具体就是用队列，存三个变量l,r,g,分别表示这个块的左端点，右端点和颜色，每次询问就过一遍，将要加入的一段颜色加入，再分类讨论原有块和加入块的位置关系保证一个点不出现在两个块里就行了。
ps：为了提升运算的速度，要将队列中相邻的颜色一样的块合并。
时间复杂度：俺也不知道，反正过了。
代码略长（反正分类讨论写了一种情况就可以复制粘贴了）

#include<bits/stdc++.h>
using namespace std;
int R,C,q,sum[16][50010],que[16][2][50010][3],len[16];
int main()
{
	scanf("%d%d%d",&R,&C,&q);
	for(int i=1;i<=R;i++)
	{
		getchar();
		for(int j=1;j<=C;j++)
		{
			bool tmp=getchar()-'0';
			sum[j][i]=sum[j][i-1]+tmp;
		}
	}
	for(int i=1;i<=C;i++)
	{
		que[i][0][1][0]=1;
		que[i][0][1][1]=R;
		que[i][0][1][2]=0;
		len[i]=1;
	}//一开始只有一个块
	for(int i=1;i<=q;i++)
	{
		bool nw=i%2;
		int x1,x2,y1,y2,kd;
		scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&kd);
		for(int j=1;j<y1;j++)
		{
			for(int e=1;e<=len[j];e++)
			{
				que[j][nw][e][0]=que[j][!nw][e][0];
				que[j][nw][e][1]=que[j][!nw][e][1];
				que[j][nw][e][2]=que[j][!nw][e][2];
			}
		}
		for(int j=y2+1;j<=C;j++)
		{
			for(int e=1;e<=len[j];e++)
			{
				que[j][nw][e][0]=que[j][!nw][e][0];
				que[j][nw][e][1]=que[j][!nw][e][1];
				que[j][nw][e][2]=que[j][!nw][e][2];
			}
		}
		for(int j=y1;j<=y2;j++)
		{
			int tmp=0;
			for(int e=1;e<=len[j];e++)
			{
				bool hv=0;
				int l=que[j][!nw][e][0],r=que[j][!nw][e][1];
				if(l>=x1&&r<=x2) hv=1;//被要加入的块压住了就可以不管了
				if(x1==l)
				{
					hv=1;
					if(tmp!=0&&que[j][nw][tmp][2]==kd) que[j][nw][tmp][1]=x2;
					else
					{
						que[j][nw][++tmp][2]=kd;
						que[j][nw][tmp][1]=x2;
						que[j][nw][tmp][0]=x1;
					}
				}
				if(que[j][!nw][e][1]>=x1&&que[j][!nw][e][0]<x1)
				{
					hv=1;
					que[j][nw][++tmp][0]=que[j][!nw][e][0];
					que[j][nw][tmp][1]=x1-1;
					que[j][nw][tmp][2]=que[j][!nw][e][2];
					if(tmp!=0&&que[j][nw][tmp][2]==kd) que[j][nw][tmp][1]=x2;
					else
					{
						que[j][nw][++tmp][2]=kd;
						que[j][nw][tmp][1]=x2;
						que[j][nw][tmp][0]=x1;
					}
				}
				if(que[j][!nw][e][1]>x2&&que[j][!nw][e][0]<=x2)
				{
					if(tmp!=0&&que[j][nw][tmp][2]==que[j][!nw][e][2])
					{
						que[j][nw][tmp][1]=r;
						continue;
					}
					que[j][nw][++tmp][0]=x2+1;
					que[j][nw][tmp][1]=r;
					que[j][nw][tmp][2]=que[j][!nw][e][2];
					continue;
				}
				if(hv) continue;//以上是分类讨论
				if(tmp!=0&&que[j][!nw][e][2]==que[j][nw][tmp][2]) que[j][nw][tmp][1]=r;
				else
				{
					que[j][nw][++tmp][0]=l;
					que[j][nw][tmp][1]=r;
					que[j][nw][tmp][2]=que[j][!nw][e][2];
				}
			}
			len[j]=tmp;
		}
		int ans=0;
		for(int j=1;j<=C;j++)
		{
			for(int e=1;e<=len[j];e++)
			{
				int tmp=sum[j][que[j][nw][e][1]]-sum[j][que[j][nw][e][0]-1];
				if(que[j][nw][e][2]) ans+=tmp;
				else ans+=(que[j][nw][e][1]-que[j][nw][e][0]+1-tmp);
			}
		}
		printf("%d\n",ans);
	}
}