题意:一个数组n个操作每次先查询p颜色的数量然后求出区间,区间染色成x,然后求最大染色数
题解:odt裸题,多维护一个color个数数组就好了
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const int N=100000+10,inf=0x3f3f3f3f;;
int co[N];
struct ODT{
struct node{
int l,r;mutable int val;
bool operator <(const node&rhs)const{
return l<rhs.l || l==rhs.l&&r<rhs.r;
}
};
set<node>s;
typedef set<node>::iterator sit;
void ins(int l,int r,int val){s.insert({l,r,val});}
void split(int pos)
{
if(pos<=0)return ;
sit p=s.upper_bound(node{pos,inf,inf});
if(p==s.begin())return ;
p--;
// printf("--------%d %d %d
",p->l,p->r,p->val);
if(pos < p->l || pos >= p->r)return ;
node te=*p;
s.erase(te);
ins(te.l,pos,te.val);
ins(pos+1,te.r,te.val);
}
void color(int l,int r,int val)
{
split(l-1);split(r);
sit x=s.lower_bound(node{l,-inf,-inf});
sit y=s.lower_bound(node{r,inf,inf});
sit xx=x,yy=y;
for(;x!=y;x++)co[x->val]-=x->r-x->l+1;
co[val]+=r-l+1;
// printf("%d %d %d %d
",x->l,x->r,y->l,y->r);
s.erase(xx,yy);
ins(l,r,val);
}
void debug()
{
for(auto x:s)
printf("%d %d %d
",x.l,x.r,x.val);
puts("");
}
}o;
int main()
{
int l,c,n;
scanf("%d%d%d",&l,&c,&n);
o.ins(1,l,1);co[1]=l;
while(n--)
{
int p,x,a,b;
scanf("%d%d%d%d",&p,&x,&a,&b);
int s=co[p],m1=(1ll*s*s+a)%l,m2=(1ll*(s+b)*(s+b)+a)%l;
if(m1>m2)swap(m1,m2);
o.color(m1+1,m2+1,x);
}
int ma=0;
for(int i=1;i<=c;i++)ma=max(ma,co[i]);
printf("%d
",ma);
return 0;
}
/***************
****************/