【题解】【白雪皑皑】

本文主要是介绍【题解】【白雪皑皑】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目传送门

题目大意：
给定一个序列，初始全为0，每次区间赋值为一个数，求最终的序列。
Solution：
观察数据范围，nlog n的时间复杂度无法通过此题，考虑线性做法。
可以将操作离线下来，则每个点第一次被覆盖时即为答案。
那么我们需要一个数据结构，能够帮助我们快速跳过已修改过的点。
这是并查集的一个经典操作。
我们对每个点记录一个nxt（相当于并查集中的fa数组）,初始nxt[i]=i
每次操作，从nxt[l]不断跳直到超过r，记录答案，并修改nxt[i]=i+1;

Code

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e6+100;
int ans[N],nxt[N];
int n,m,p,q;
inline int find(int x)
{
	return x==nxt[x]?x:nxt[x]=find(nxt[x]);
}
int main()
{
    n=read();m=read();p=read();q=read();
    for(int i=1;i<=n+1;++i) nxt[i]=i;
    for(int i=m;i;--i)
    {
    	int l=(i*p+q)%n+1,r=(i*q+p)%n+1;
    	if(l>r) swap(l,r);
    	while(find(l)<=r)
    	{
    		ans[nxt[l]]=i;
    		nxt[nxt[l]]=nxt[l]+1;
		}
	}
	for(int i=1;i<=n;++i) write(ans[i]),puts("");
	return 0;
}

这篇关于【题解】【白雪皑皑】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！