记录编号	333538	评测结果	AAAAAAAWWW
题目名称	2193.[HZOI 2015] 区间统计	最终得分	70
用户昵称	‎MistyEye	是否通过	未通过
代码语言	C++	运行时间	1.396 s
提交时间	2016-10-30 21:26:12	内存使用	34.61 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 2000005, INF = 0x3f3f3f3f, mod = 1000000007;
int 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;
	for(int i=1; i<=N; ++i) a[i] = (1LL*a[i-1]*A+B)%C;
	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) 
	// 	printf("%d %d %d %d %d\n", a[i], L[i], R[i], LO[i], RO[i]);
	ll ans = 0;
	for(int i=1; i<=N; ++i) {
		++L[i], ++LO[i], --R[i], --RO[i];
		// printf("0 %d\n", ans);
		if(R[i]!=N) 
			ans += 1LL*a[i]*a[R[i]+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 += 1LL*a[i]*a[L[i]-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