多校省选模拟3

T1 人脑图灵机

归纳一下，对于\(m<=(n-1)b-\frac{b}{2}\)一定合法

然后\(((n-1)b-\frac{b}{2},n* b)\)内的合法点一定由\(a* x+b* y\)构成

ifelse+exgcd

T2 超脑星球

由于 T3 调了很久，就没时间了，，，

T3 暗星人

这个L,R和l,r的限制，可以使用主席树

加法标记和乘法标记在这个模数下不具有可减性，就树套树吧

然而空间不太够(可能够但是没写)，就分块+主席树

需要注意的是，因为这个标记具有结合律但是没交换律，并且在这个模数下不能通过将\(add->add',mul->mul'\)使得具有可交换性

然后就不能标记永久化，每次insert时push下去

在两个标记合并时，我直接给一个树节点赋值过去，然后把lc和rc覆盖了，，，加上卡常，就调到了20：30，恶心的很

代码

T1

#include
using namespace std;
#define int __int128_t 
#define il inline
int n,m,a,b;
int gcd(int a,int b){if(!b)return a;return gcd(b,a%b);}
il int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void exgcd(int a,int b,int &x,int &y)
{
	if(!b){x=1;return;}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return;
}
signed main()
{
	freopen("turing.in","r",stdin);
	freopen("turing.out","w",stdout);
//	freopen("data","r",stdin);
//	freopen("c.out","w",stdout);
	int n,m,a,b,ed,x,y,d,k;
	int t=read();
	while(t--)
	{
		n=read(),m=read();
		a=read(),b=read();
		ed=(n-1)*b+b/2;
		if(m<=ed||m==n*b){printf("%s\n","Yes");continue;}
		if(a<=0.5*b){printf("%s\n","No");continue;}
		else
		{
			d=gcd(a,b),k=m/d;
			if(m%d){printf("%s\n","No");continue;}
			exgcd(a,b,x,y);
			x=k*x,y=k*y;
			k=b/d;
			if(x<0) x=x+(-x/k+1)*k;
			else x=x-(x/k)*k;
			if(x==k)x=0;
			y=(m-a*x)/b;
			if(x>=0&&y>=0&&x+y<=n) printf("%s\n","Yes");
			else printf("%s\n","No");
		}
	}
	return 0;
}

T3

#include
using namespace std;
#define il inline
#define int long long
const int N=3e5+11;
const unsigned int mod=2677114440;
int siz;
il int max_(int x,int y){return x>y?x:y;}
struct tree{
	signed lc,rc;unsigned int mul,add,maxx;
	friend tree operator+(tree a,tree b)
	{
		b.maxx=max_(b.maxx,a.maxx);
		b.add=((b.mul*a.add)+b.add)%mod;
		b.mul=a.mul*b.mul%mod;
		b.lc=a.lc,b.rc=a.rc;
		return b;
	}
}tre[100*N],tmp,dw,now[N];
bool ty;
int n,m,ans,tot;
signed root[N];
signed bl[N],br[N];
int L[N],R[N],a[N],b[N];
il void upd(tree &a,tree b){a.mul=b.mul,a.add=b.add,a.maxx=b.maxx;return;}
il int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
il void rd(int &x){x=read()^(ty*ans);return;}
il void push(signed i)
{
	if(!tre[i].lc) tre[i].lc=++tot,tre[tot].mul=1;
	if(!tre[i].rc) tre[i].rc=++tot,tre[tot].mul=1;
	int lc=tre[i].lc,rc=tre[i].rc;
	tree tp1=tre[lc]+tre[i],tp2=tre[rc]+tre[i];
	upd(tre[lc],tp1),upd(tre[rc],tp2);
	tre[i].mul=1,tre[i].add=tre[i].maxx=0;
	return;
}
void ins(signed &i,signed l,signed r,int x)
{
	if(!i) i=++tot,tre[i]=dw;
	if(l!=r) push(i);
	if(l>=L[x]&&r<=R[x]) {tre[i]=tre[i]+now[x];return;}
	int mid=(l+r)>>1;
	if(L[x]<=mid) ins(tre[i].lc,l,mid,x);
	if(R[x]>mid) ins(tre[i].rc,mid+1,r,x);
	return;
}
tree qry(signed i,signed l,signed r,int x)
{
	if(!i) return dw;
	if(l==r) return tre[i];
	int mid=(l+r)>>1;
	if(x<=mid) return qry(tre[i].lc,l,mid,x)+tre[i];
	else return qry(tre[i].rc,mid+1,r,x)+tre[i];
}
signed main()
{
//	freopen("data","r",stdin);
//	freopen("zj1.out","w",stdout);
	freopen("dark.in","r",stdin);
	freopen("dark.out","w",stdout);
	dw={0,0,1,0,0};
	n=read(),m=read(),ty=read();
	siz=pow(m,0.6);
	for(int i=1;i<=m;++i){if(!bl[i/siz+1]) bl[i/siz+1]=i;br[i/siz+1]=i;}
	double x1=clock();
	for(int l,r,x,X,blo,i=1;i<=m;++i)
	{
		rd(L[i]),rd(R[i]),rd(a[i]),rd(b[i]);
		rd(l),rd(r),rd(X),rd(x);
		blo=i/siz+1,tmp=dw;
		now[i]=(tree){0,0,a[i],b[i],b[i]};
		ins(root[blo],1,n,i);
		int BL=l/siz+1,BR=r/siz+1;
		if(BL==BR)
		{
			for(int j=l;j<=r;++j) if(L[j]<=X&&R[j]>=X) tmp=tmp+now[j];
			ans=(tmp.mul*x%mod+tmp.add)%mod^tmp.maxx;
			printf("%lld\n",(long long)ans);
			continue;
		}
		for(int j=l;j<=br[BL];++j) if(L[j]<=X&&R[j]>=X) tmp=tmp+now[j];
		for(int j=BL+1;j<=BR-1;++j) tmp=tmp+qry(root[j],1,n,X);
		for(int j=bl[BR];j<=r;++j) if(L[j]<=X&&R[j]>=X) tmp=tmp+now[j];
		ans=(tmp.mul*x%mod+tmp.add)%mod^tmp.maxx;
		printf("%lld\n",(long long)ans);
	}
//	double x2=clock();
//	cout<<(x2-x1)/CLOCKS_PER_SEC<