出题人题解 | #Rabbit的数列#

原题解链接：https://ac.nowcoder.com/discuss/151166

因为$A\mathrm{，}BA，B$是随机的，所以分块维护一下颜色即可。

当然用其他方法也可以，验题人表示还可以用一个$set\mathrm{/}mapset/map$存下所有的相同的段，每次把$[l,r][l,r]$这一段分离出来，然后把这一段里面的相同段修改之后合并成一段。

#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 100005;
const ll INF = 1e18;
const ll mod=1e9+7;
const double eps = 1e-7;

int n,m,q,gap;
int a[maxn];
int num[maxn];
int tag[maxn];
int tree[maxn],bl[maxn];

void reset(int x)
{
    if(tag[x]==-1) return;
    for(int i=(x-1)*gap+1;i<=min(n,x*gap);i++) a[i]=tag[x];
    tag[x]=-1;
}

void solve(int l,int r,int val)
{
    reset(bl[l]);
    for(int i=l;i<=min(bl[l]*gap,r);i++)
    {
        if(a[i]!=val) num[a[i]]--,num[val]++,a[i]=val;
    }
    if(bl[l]!=bl[r])
    {
        reset(bl[r]);
        for(int i=(bl[r]-1)*gap+1;i<=r;i++)
        {
            if(a[i]!=val) num[a[i]]--,num[val]++,a[i]=val;
        }
    }
    for(int i=bl[l]+1;i<=bl[r]-1;i++)
    {
        if(tag[i]!=-1)
        {
            if(tag[i]!=val) num[tag[i]]-=gap,num[val]+=gap,tag[i]=val;
        }
        else
        {
            for(int j=(i-1)*gap+1;j<=i*gap;j++)
            {
                if(a[j]!=val) num[a[j]]--,num[val]++,a[j]=val;
            }
            tag[i]=val;
        }
    }
}


int main()
{
    scanf("%d%d%d",&n,&m,&q);
    gap=sqrt(n*1.0);
    mst(tag,-1);
    mst(num,0);
    for(int i=1;i<=n;i++) bl[i]=(i-1)/gap+1;
    solve(1,n,1);
    for(int i=1;i<=q;i++)
    {
        int x,y;
        ll A,B;
        scanf("%d%d%lld%lld",&x,&y,&A,&B);
        ll S=num[x];

        ll tmp1=(A+(S+B)*(S+B)%(ll)n)%(ll)n+1;
        ll tmp2=(A+S*B%n*(S*B%n)%(ll)n)%(ll)n+1;

        if(tmp1>tmp2) swap(tmp1,tmp2);
        solve((int)tmp1,(int)tmp2,y);
    }
    int ans=0;
    for(int i=1;i<=m;i++) ans=max(ans,num[i]);
    printf("%d\n",ans);
}