记录编号	333573	评测结果	AAAAAAAWAW
题目名称	2193.[HZOI 2015] 区间统计	最终得分	80
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	2.580 s
提交时间	2016-10-31 05:58:27	内存使用	76.61 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn = 2000005, INF = ~0ULL>>1, mod = 1000000007;
ll N, a[maxn], A, B, C, L[maxn], R[maxn], LO[maxn], RO[maxn];
int main(int argc, const char *argv[]) {
	freopen("s.in","r",stdin); freopen("s.out","w",stdout); 
	cin >>N >>a[0] >>A >>B >>C;
	A %= C, B %= C;
	for(int i=1; i<=N; ++i) a[i] = (a[i-1]*A%C+B)%C;
	for(int i=1; i<=N; ++i) a[i] = a[i]*(N+1)+i;
	// for(int i=1; i<=N; ++i) printf("%lld ", a[i]); puts("");
	a[0] = a[N+1] = INF;
	for(int i=1; i<=N; ++i) {
		L[i] = i-1;
		while(a[i]>a[L[i]]) L[i] = L[L[i]];
		LO[i] = L[i]-(i!=1);
		while(a[i]>a[LO[i]]) LO[i] = L[LO[i]];
	}
	for(int i=N; i>=0; --i) {
		R[i] = i+1;
		while(a[i]>a[R[i]]) R[i] = R[R[i]];
		RO[i] = R[i]+(i!=N);
		while(a[i]>a[RO[i]]) RO[i] = R[RO[i]];
	}
	for(int i=1; i<=N; ++i) 
		++L[i], ++LO[i], --R[i], --RO[i];
	// for(int i=1; i<=N; ++i) 
	// 	printf("%lld %lld %lld %lld\n", L[i], R[i], LO[i], RO[i]);
	ll ans = 0;
	for(int i=1; i<=N; ++i) {
		// printf("0 %d\n", ans);
		if(R[i]!=N) 
			ans += (a[i]/(N+1))*(a[R[i]+1]/(N+1))%mod*(i-L[i]+1)*(RO[i]-R[i])%mod;
		// printf("1 %d %d %d\n", ans, l, r);
		if(a[L[i]-1]==a[i]) continue;
		if(L[i]!=1) 
			ans += (a[i]/(N+1))*(a[L[i]-1]/(N+1))%mod*(L[i]-LO[i])*(R[i]-i+1)%mod;
		ans %= mod;
		// printf("2 %d %d %d\n", ans, l, r);
	}
	cout <<ans <<endl;
	getchar(), getchar();
	return 0;
}
// http://cogs.pw/cogs/problem/problem.php?pid=2193
// http://cogs.pw/cogs/problem/problem.php?pid=1917
// http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1564
// http://www.51nod.com/question/index.html#!questionId=1449