记录编号	483615	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	颓题面	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	1.796 s
提交时间	2018-01-18 11:16:57	内存使用	30.74 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;
typedef long long ll;
const int N = 600010;
int _w;

int n, m, a[N], p[N];

void input() {
	ll x, a, b, c;
	ll y, u, v, w;
	cin >> x >> a >> b >> c;
	cin >> y >> u >> v >> w;
	for( int i = 1; i <= n; ++i )
		::a[i] = i;
	while( m-- ) {
		x = (a*x%n*x + b*x + c) % n + 1;
		y = (u*y%n*y + v*y + w) % n + 1;
		swap( ::a[x], ::a[y] );
	}
	for( int i = 1; i <= n; ++i )
		p[::a[i]] = i;
	for( int i = 1; i <= n; ++i )
		swap( ::a[i], p[i] );
}

namespace SGT {
	int minv[N*4], maxv[N*4], addv[N*4];
	int ql, qr, qv;
	void _add( int o, int L, int R ) {
		if( L >= ql && R <= qr ) {
			addv[o] += qv;
			minv[o] += qv;
			maxv[o] += qv;
		} else {
			int M = (L+R)/2, lc = o<<1, rc = lc|1;
			if( ql <= M ) _add(lc, L, M);
			if( qr > M ) _add(rc, M+1, R);
			minv[o] = min( minv[lc], minv[rc] ) + addv[o];
			maxv[o] = max( maxv[lc], maxv[rc] ) + addv[o];
		}
	}
	void add( int l, int r, int v ) {
		ql = l, qr = r, qv = v;
		_add(1, 1, n);
	}
	void _query( int o, int L, int R, int adv ) {
		if( maxv[o] + adv <= 2 ) {
			qv += R-L+1;
			return;
		}
		if( minv[o] + adv > 2 ) {
			return;
		}
		if( L != R ) {
			int M = (L+R)/2, lc = o<<1, rc = lc|1;
			adv += addv[o];
			_query(lc, L, M, adv), _query(rc, M+1, R, adv);
		}
	}
	int query( int l, int r ) {
		ql = l, qr = r, qv = 0;
		_query(1, 1, n, 0);
		return qv;
	}
}

int main() {
	freopen( "tui_problem.in", "r", stdin );
	freopen( "tui_problem.out", "w", stdout );
	cin >> n >> m;
	input();
	ll ans = 0;
	for( int i = 1; i <= n; ++i ) {
		int x = a[i];
		SGT::add(1, i, 1);
		if( x != 1 && p[x-1] <= i )
			SGT::add(1, p[x-1], -1);
		if( x != n && p[x+1] <= i )
			SGT::add(1, p[x+1], -1);
		ans += SGT::query(1, i) - (n-i);
	}
	cout << ans-n << endl;
	return 0;
}