牛客は大会を開きたいと思った2——C

リンクりんく:原題題のアドレスげんだいのろーど
タイトルの説明
Rabbitは長さNの数列(数列番号0からN−1)を得た.数列の各数valiは、1<=vali<=Cを満たす.初期時数列の各数は1であるが、Rabbitはこの数列に対してQ回の操作を行い、操作ごとに4つの数:XY A Bを与え、まず数列の中の値がXの個数Pを問合せ、それからL,R:L=(A+(P+B)2)mod N=(A+(P∗B)2)mod Nを計算し、範囲[min(L,R),max(L,R)]内のすべての数をYに変更する.最後にQ回操作後の数列で最も多く出現した数が何回出現したかを尋ねる.   
説明を入力:

       N，C，Q。

   Q ，      X，Y，A，B，      。

出力の説明:

      ，    Q                      。

例1
入力
 

4 2 1
2 2 1 1

しゅつりょく
 

2

コメント:

1<=N,C,Q<=10^5

1<=X,Y<=C，1<=A,B<=10^8

A,B      

 
 
 
私は言いたいのですが、この問題の区間メンテナンス方式は、思わず線分樹を思い出しました.pieはACコードのあの千言万語の怠け者マークと線分樹の標準的なk<<2とk<<2|1を見たとき、私は思い切ってページを消して、自分で線分樹の板を修正し続けましたが、依然として「赤とオレンジが付き添っている」ので、我慢できずにまたページを開けて、やっと分かりました.メンテナンスが単点値で区間最値をメンテナンスしないとタイムアウトしないのがおかしいです.(コードは本人オリジナルではありませんが、私が書くときっとこんなにはっきりしないでしょう.注釈はもう少し加えなければなりませんね.このコードはjioの美しさに足りないのは、下付きと区間がパラメータの形で変化していることです.私は区間を書くことに偏っています.最後に構造体になって、このupdate関数jioのパラメータが多すぎるのを見て、私が言ったことを考えてもいいですが、木を建てるのは多いです.時間が来るとタイムアウトになる可能性があります)

#include
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
int vis[maxn];
int lazy[maxn*4],mx[maxn*4],mn[maxn*4];//mn    ，mx    
void pushdown(int id,int l,int r)//     
{
	if(lazy[id])
	{
		mx[id]=mn[id]=lazy[id];
		if(l!=r)
		{
			lazy[id<<1|1]=lazy[id<<1]=lazy[id];
			mx[id<<1]=mx[id<<1|1]=lazy[id];
			mn[id<<1]=mn[id<<1|1]=lazy[id];
		}
		lazy[id]=0;
	}
}
void update(int id,int l,int r,int ql,int qr,int v)
{
	pushdown(id,l,r);//     ，        ，     ，         ，    cnt[]   ，      ，                。
	if(ql<=l&&r<=qr&&mx[id]==mn[id])//mx[id] == mn[id]  id          ，ql<=l&&r<=qr                 。
	{
		vis[mx[id]]-=(r-l+1);//         
		vis[v]+=(r-l+1);
		lazy[id]=v;
		pushdown(id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) update(id<<1,l,mid,ql,qr,v);
	if(qr>mid) update(id<<1|1,mid+1,r,ql,qr,v);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);//    
	mn[id]=min(mn[id<<1],mn[id<<1|1]);
}
int main()
{
	int n,c,q,x,y;
	ll a,b;
	scanf("%d%d%d",&n,&c,&q);
	vis[1]=n;
	lazy[1]=1;//        
	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);
		update(1,1,n,l,r,y);
	}
	int ans=0;
	for(int i=1;i<=c;i++)
	ans=max(ans,vis[i]);
	printf("%d
",ans);
    return 0;
}