C++11(clang++ 3.9) 解法, 执行用时: 295ms, 内存消耗: 6524K, 提交时间: 2019-01-07 16:38:23

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
int vis[maxn],tag[maxn*4],ans;
int mx[maxn*4],mn[maxn*4];
void pushdown(int o,int ls,int rs,int l,int r)
{
	if(tag[o])
	{
		mx[o]=mn[o]=tag[o];
		if(l!=r)
		{
			tag[ls]=tag[rs]=tag[o];	
			mx[ls]=mx[rs]=tag[o];
			mn[ls]=mn[rs]=tag[o];
		}
		tag[o]=0;
	}
}
void up(int o,int l,int r,int ql,int qr,int v)
{
	int ls=o*2,rs=o*2+1,m=(l+r)/2;
	pushdown(o,ls,rs,l,r);
	if(l>=ql&&r<=qr&&mx[o]==mn[o])
	{
		vis[mx[o]]-=(r-l+1);
		vis[v]+=(r-l+1);
		tag[o]=v;
		pushdown(o,ls,rs,l,r);
		return;
	}
	if(ql<=m)up(ls,l,m,ql,qr,v);
	if(qr>m)up(rs,m+1,r,ql,qr,v);
	mx[o]=max(mx[ls],mx[rs]);
	mn[o]=min(mn[ls],mn[rs]);
}
int main()
{
	int n,c,q,x,y;
	ll a,b;
	scanf("%d%d%d",&n,&c,&q);
	tag[1]=1;
	vis[1]=n;
	while(q--)
	{
		scanf("%d%d%lld%lld",&x,&y,&a,&b);
		int p=vis[x];
		int l=(a+(p+b)%n*(p+b)%n)%n+1;
		int r=(a+p*b%n*p%n*b%n)%n+1;
		if(l>r)swap(l,r);
		up(1,1,n,l,r,y);
	}
	for(int i=1;i<=c;i++)
	ans=max(ans,vis[i]);
	printf("%d\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 183ms, 内存消耗: 3628K, 提交时间: 2020-08-04 23:53:14

#include<bits/stdc++.h>
using namespace std;

int y,Max[400005],Min[400005],T[400005]={0},V[100005]={0};
void down(int L,int R,int x)
{
	if(!T[x])return;
	Max[x]=Min[x]=T[x];
	if(L!=R)Max[x<<1]=Min[x<<1]=Max[x<<1|1]=Min[x<<1|1]=T[x<<1]=T[x<<1|1]=T[x];
	T[x]=0;
}
void update(int L,int R,int l,int r,int x)
{
	down(L,R,x);
	if(l<=L&&R<=r&&Max[x]==Min[x])
	{
		V[Max[x]]-=(R-L+1),V[y]+=R-L+1;
		T[x]=y,down(L,R,x);
		return;
	}
	int M=(L+R)>>1;
	if(M>=l)update(L,M,l,r,x<<1);
	if(M<r)update(M+1,R,l,r,x<<1|1);
	Max[x]=max(Max[x<<1],Max[x<<1|1]);
	Min[x]=min(Min[x<<1],Min[x<<1|1]);
}
int main()
{
    int i,n,c,q,x,p,l,r,ans=0;
    long long a,b;
    scanf("%d%d%d",&n,&c,&q);
	T[1]=1,V[1]=n;
    while(q--)
    {
    	scanf("%d%d%lld%lld",&x,&y,&a,&b);
    	p=V[x],l=(a+(p+b)*(p+b))%n+1,r=(a+b*b%n*p%n*p)%n+1;
		if(l>r)swap(l,r);
		update(1,n,l,r,1);
	}
	for(i=1;i<=c;i++)ans=max(ans,V[i]);
	printf("%d\n",ans);
    return 0;
}