ICPC 2017 Latin American Regional D（分块）
90nwyn
2020-10-20 17:14:09
[题目链接](https://vjudge.net/problem/Gym-101889D)
------------
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5+5,N=5e2+5;
int n,c,m,blo,cnt,id[M],L[N],R[N],tag[N],sum[N][M],col[M],mx;
void upd(int l,int r,int x)
{
for(int i=id[l];i<=id[r];i++)
{
if(l<=L[i]&&R[i]<=r)tag[i]=x;
else
{
if(tag[i])
{
for(int j=L[i];j<=R[i];j++)
{
sum[i][col[j]]--;
sum[i][col[j]=tag[i]]++;
}
tag[i]=0;
}
for(int j=max(L[i],l);j<=min(R[i],r);j++)
{
sum[i][col[j]]--;
sum[i][col[j]=x]++;
}
}
}
}
int que(int x)
{
int res=0;
for(int i=1;i<=cnt;i++)
{
if(tag[i])res+=(tag[i]==x)?(R[i]-L[i]+1):0;
else res+=sum[i][x];
}
return res;
}
int main()
{
scanf("%d%d%d",&n,&c,&m);
blo=sqrt(n);
cnt=(n-1)/blo+1;
for(int i=1;i<=cnt;i++)
{
L[i]=(i-1)*blo+1;
R[i]=min(i*blo,n);
sum[i][1]=R[i]-L[i]+1;
}
for(int i=1;i<=n;i++)
{
id[i]=(i-1)/blo+1;
col[i]=1;
}
for(int i=1;i<=m;i++)
{
int p,x,a,b;scanf("%d%d%d%d",&p,&x,&a,&b);
int s=que(p);
int m1=(a+(ll)s*s%n)%n+1;
int m2=(a+(ll)(s+b)*(s+b)%n)%n+1;
upd(min(m1,m2),max(m1,m2),x);
}
for(int i=1;i<=cnt;i++)
{
if(tag[i])sum[0][tag[i]]+=R[i]-L[i]+1;
else for(int j=L[i];j<=R[i];j++)sum[0][col[j]]++;
}
for(int i=1;i<=c;i++)mx=max(mx,sum[0][i]);
printf("%d\n",mx);
return 0;
}
```