【NOI五连测】[D1T1] 咏叹

题目传送门:http://pan.baidu.com/s/1i52O6xR

这题,试一试,可以发现(我真的是试出来的QAQ),我们可以用一个数,在他前面,且大于他的数的个数来更新答案
这个,证明的话,不难发现,每一次排序,都一定会使一个大于a的数跑到a的右边去。
所以搞个BIT就可以O(nlogn)搞,70分。

当然,这个做法有一点奇技淫巧可以让他A掉:
不难发现“在他前面,且大于他的数的个数”是单增的。
所以,我们倒着来的话,既可以提前break掉
这样的话,O(nlogn)就变成了O((n-ans)logn)因为ans一般很大,所以实际耗时和std差不多。

再来说一说std
再一次观察冒泡排序,不难发现,每一次排序,任意一个元素(现在的位置在最终位置的右边的那一部分),
如果不在最终的位置,那么一定会向前移动一格。(证明同算法一)
于是我们就可以直接用i-arr[i]来更新答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define LL long long
#define low(x) (x&-(x))
using namespace std;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

const int MAXN = 30000000+9;

int n,vout,arr[MAXN],sum[MAXN],S,B,C,D;

int main(){
	freopen("aria.in","r",stdin);
	freopen("aria.out","w",stdout);
	n=read(); S=read(); B=read();
	C=read(); D=read();
	for (int i=1;i<=n;i++){
		arr[i] = i;
		S = ((LL)S*(LL)B+(LL)C)%(LL)D;
		swap(arr[i], arr[(S%i)+1]);
	}	
	for (int i=n,tmp;i>=vout;i--)
		vout = max(vout, i-arr[i]);
	printf("%d\n",vout);
}