這個題首先不能暴力，然後我們考慮發現一下這個每次修改的區間的性質

我們發現這個區間的迴圈節為 $n$ ?!

線段樹維護即可！

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
constexpr int N=3*1e6+10;
int _=1,n,k,A,B;
struct tree{
	int l,r,lzy;
	void tag(int p,int d){lzy=d;}
}t[N<<2];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("D.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void builds(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].lzy=-1;
	if(l==r) return;
	int mid=(l+r)>>1;
	int x=p<<1,y=p<<1|1;
	builds(x,l,mid),builds(y,mid+1,r);
}
void pushdown(int p){
	if(~t[p].lzy){
		int x=p<<1,y=p<<1|1;
		t[x].tag(x,t[p].lzy),t[y].tag(y,t[p].lzy);
		t[p].lzy=-1;
	}
}
void changes(int p,int l,int r,int d){
	if(l<=t[p].l&&t[p].r<=r){t[p].tag(p,d);return;}
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;pushdown(p);
	if(l<=mid) changes(x,l,r,d);
	if(r>mid) changes(y,l,r,d);
}
int asks(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].lzy;
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;pushdown(p);
	if(l<=mid) return asks(x,l,r);
	if(r>mid) return asks(y,l,r);
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),k=reads(),A=reads(),B=reads();builds(1,1,n);
		for(int i=max(k-n+1,1),L,R;i<=k;i++){
			L=(A*i+B)%n+1,R=(B*i+A)%n+1;
			if(L>R) L^=R^=L^=R;
			changes(1,L,R,i);
		}
		for(int i=1;i<=n;i++) printf("%d\n",max(asks(1,i,i),0));
	}
	return 0;
}

不用线段树看这里

namespace syr
{
	const ll N = 1e6+10;
	ll n, k, a, b;
	ll l[N];
	bool v[N*10];
	priority_queue <ll> q;
	vector <ll> r[N];
	ll mol (ll x, ll y) {
		if (x>y) x -= y;
		return x;
	}
	void work()
	{
		cin>>n>>k>>a>>b;
		ll st = max(1, k-n+1);
		for (ll i=st; i<=k; i++) {
			ll x = (i*a+b) %n + 1;
			ll y = (i*b+a) %n + 1;
			if (x>y) swap(x, y);
			l[x] = i, r[y+1].push_back(i);
		}
		q.push(0);
		for (ll i=1; i<=n; i++) {
			for (ll j=0; j<r[i].size(); j++)
				v[r[i][j]] = 1;
			while (v[q.top()]) q.pop();
			if (l[i]) q.push(l[i]);
			cout<<q.top()<<'\n';
		}
	}
}

两个细节：

1.if(x > y) swap(x, y);

2.fa[n+1]=n+1;

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int fa[N], ans[N];
int n, k, a, b, cnt;
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main()
{
	scanf("%d%d%d%d", &n, &k, &a, &b);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	fa[n+1]=n+1;
	for(int i = k; i >= 1; --i)
	{
		int x = (1ll * i * a + b) % n + 1, y = (1ll * i * b + a) % n + 1;
		if(x > y) swap(x, y);
		for(int j = find(x); j <= y; j = find(j))
		{
			ans[j] = i; fa[j] = find(j + 1); cnt++;
		}
		if(cnt==n)break;
	}
	for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int fa[N], ans[N];
int n, k, a, b, cnt;
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main()
{
	scanf("%d%d%d%d", &n, &k, &a, &b);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	fa[n+1] = n+1;
	for(int i = k; i >= 1; --i)
	{
		int x = (1ll * i * a + b) % n + 1, y = (1ll * i * b + a) % n + 1;
		if(x > y) swap(x, y);
		for(int j = find(x); j <= y; j = find(j+1))
		{
			//if(j > y)break;
			ans[j] = i;
			fa[j] = find(y + 1);
			cnt++;
		}
		if(cnt==n)break;
	}
	for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
	return 0;
}

首先80分线段树白送。然后注意到给定的公式看似是为了减小输入量，其实蕴含了一个性质，(i*a+b)%N+1=((i%N)*a+b)%N+1。

所以只需要考虑最后 $n$ 次操作。所以就是线段树模板。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e-'0');
		e=getchar();
	}
	return x*y;
}
const int N=1000005;
int n,k,a,b;
#define lo (nw<<1)
#define ro (nw<<1|1)
#define md ((l+r)>>1)
struct node {
	int laz,d;
} t[N<<2];
void pushdown(int nw) {
	if(t[nw].laz) {
		t[lo].laz=t[ro].laz=t[lo].d=t[ro].d=t[nw].laz;
		t[nw].laz=0;
	}
}
void chg(int nw,int l,int r,int x,int y,int c) {
	if(x<=l&&r<=y) {
		t[nw].laz=t[nw].d=c;
		return ;
	}
	pushdown(nw);
	if(x<=md) chg(lo,l,md,x,y,c);
	if(y>md) chg(ro,md+1,r,x,y,c);
}
int ask(int nw,int l,int r,int x) {
	if(l==r) {
		return t[nw].d;
	}
	pushdown(nw);
	if(x<=md)return ask(lo,l,md,x);
	else return ask(ro,md+1,r,x);
}
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen(".out","w",stdout);
	R(n),R(k),R(a),R(b);
	for(int i=max(k-n+1,1ll); i<=k; ++i) {
		int l=(i*a+b)%n+1,r=(i*b+a)%n+1;
		if(l>r)swap(l,r);
//		cout<<l<<" "<<r<<" "<<i<<"\n";
		chg(1,1,n,l,r,i);
	}
	for(int i=1; i<=n; ++i) {
		cout<<ask(1,1,n,i)<<"\n";
	}
	return 0;
}

大家是不是觉得线段树很勾石不想写

其实线段树可以写得很短的

这可能需要一定的技巧

#include<bits/stdc++.h>
#define I long long
#define R return
#define o (W<<1)
#define O (W<<1|1)
#define M (l+r>>1)
const I N=4e6+5;
I n,k,a,b,L[N],d[N];
void p(I W){if(L[W])L[o]=L[O]=d[o]=d[O]=L[W],L[W]=0;}
void C(I W,I l,I r,I x,I y,I c){if(x<=l&&r<=y){L[W]=d[W]=c;R;}p(W);if(x<=M)C(o,l,M,x,y,c);if(y>M)C(O,M+1,r,x,y,c);}
I A(I W,I l,I r,I x){if(l==r)R d[W];p(W);if(x<=M)R A(o,l,M,x);else R A(O,M+1,r,x);}
signed main(){
	std::cin>>n>>k>>a>>b;
	for(I i=std::max(k-n+1,1ll),l,r;i<=k;++i){l=(i*a+b)%n+1,r=(i*b+a)%n+1;if(l>r)std::swap(l,r);C(1,1,n,l,r,i);}
	for(I i=1;i<=n;++i)std::cout<<A(1,1,n,i)<<"\n";
	exit(0);
}