70TLE,求大佬教导状压
查看原帖
70TLE,求大佬教导状压
665772
Haoyue_06432楼主2023/10/12 18:04
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e18
using namespace std;
ll n,m,q,opt,x,y,ans[maxn],k,sum,num;
string a[maxn],b,d[maxn],e;
bool bj[maxn];
void build(ll l,ll r,ll s)
{
	if(l==r)
	{
		d[s]=a[l];
		return;
	}
	build(l,(l+r)/2,s*2);
	build((l+r)/2+1,r,s*2+1);
	bj[s]=(bj[s*2]|bj[s*2+1]);
	if(!bj[s])
	{
		for(int i=0;i<m;i++)
		{
			if(d[s*2][i]==d[s*2+1][i])d[s]+=d[s*2][i];
			else if(d[s*2][i]=='?')d[s]+=d[s*2+1][i];
			else if(d[s*2+1][i]=='?')d[s]+=d[s*2][i];
			else
			{
				bj[s]=true;
				break;
			}
		}		
	}
}
void update(ll x,string z,ll l,ll r,ll s)
{
	if(l>x||r<x)return;
	d[s]="";bj[s]=false;
	if(l==r&&l==x)
	{
		d[s]=z;
		return;
	}
	update(x,z,l,(l+r)/2,s*2);
	update(x,z,(l+r)/2+1,r,s*2+1);
	bj[s]=(bj[s*2]|bj[s*2+1]);
	if(!bj[s])
	{
		for(int i=0;i<m;i++)
		{
			if(d[s*2][i]==d[s*2+1][i])d[s]+=d[s*2][i];
			else if(d[s*2][i]=='?')d[s]+=d[s*2+1][i];
			else if(d[s*2+1][i]=='?')d[s]+=d[s*2][i];
			else
			{
				bj[s]=true;
				break;
			}
		}		
	}
}
bool find(ll x,ll y,ll l,ll r,ll s)
{
	if(l>y||r<x)return false;
	if(x<=l&&r<=y)
	{
		ll bj2=false;
		if((bj[s*2]|bj[s*2+1]))bj2=true;
		else
		{
			if(e=="")e=d[s];
			else 
			{
				for(int i=0;i<m;i++)
				{
					if(e[i]!=d[s][i])
					{
						if(e[i]=='?')e[i]=d[s][i];
						else if(d[s][i]!='?')
						{
							bj2=true;
							break;
						}		
					}
	
				}
			}			
		}
		return (bj[s]|bj2);
	}
	return (find(x,y,l,(l+r)/2,s*2)|find(x,y,(l+r)/2+1,r,s*2+1));
}
int main()
{
	scanf("%lld%lld%lld",&m,&n,&q);
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	for(int i=1;i<=q;i++)
	{
		scanf("%lld%lld",&opt,&x);
		if(opt==0)
		{
			scanf("%lld",&y);		
			num=0;e="";k++;
			if(!find(x,y,1,n,1))
			{
				for(int j=0;j<m;j++)if(e[j]=='?')num++;
				ans[k]=pow(2,num);
			}
		}
		if(opt==1)
		{
			cin>>b;
			update(x,b,1,n,1);
		}
	}
	for(int i=1;i<=k;i++)sum=(sum^ans[i]);
	printf("%lld",sum);
	return 0;
}
2023/10/12 18:04
加载中...