P6604 [HNOI2016]序列加强版

考虑一次查询，比如查询 $[l,r]$ 区间。

首先找出区间内最小值的位置，设为 $pos$ 。

考虑把询问的区间的子区间分成三种：

跨过了 $pos$
左右端点都在 $[l,pos-1]$
左右端点都在 $[pos+1,r]$

考虑分别处理。对于第一种，明显贡献是 $(pos-l+1)(r-pos+1)$ 。

下面设 $[l,r][L,R]$ 表示左端点在 $[l,r]$ 内，右端点在 $[L,R]$ 内的所有区间的最小值的和。

我们考虑怎么求 $[l,r][l,r]$ 的值。我们把这个拆成：

$[l,n][l,n] - [r + 1,n][r + 1,n] - [l,r][r + 1,n]$

也就是左右端点都在 $[l,n]$ 减去左右都在 $[r+1,n]$ 再减去左端点在 $[l,r]$ 右端点在 $[r+1,n]$ 的贡献。

怎么求 $[l,n][l,n]$ 呢，考虑预处理出来。为了方便设 $f(i) = [i,n][i,n]$ ，于是可以发现

$f(i) = f(i + 1) + [i,i][i,n]$

再设 $F(i) = [i,i][i,n]$ 。考虑怎么递推出 $F$ 。对于每个位置 $i$ ，设 $r_i$ 为满足 $a_{r_i} < a_i$ 的最小值，也就是说 $a_i$ 小于 $[i,r_i-1]$ 的所有值。于是

$F_i = F_{r_i} + a_i(r_i-i)$

于是递推求出了 $F$ 也就求出了 $f$ 。

回到原来的问题，我们还需要求 $[l,r][r+1,n]$ 。这个东西看起来求不了。但是，对于第二种询问，我们要求的是

$[l,pos-1][pos,n]$

由于 $a_{pos}$ 是 $[l,r]$ 的最小值，这个东西直接等于 $(pos-l)F_{pos}$ 。因为左端点的选择是 $[l,pos-1]$ 中任意选择，且每个区间都一定是 $pos$ 后面更小，所以就是 $F_{pos}$ 的 $pos-l$ 倍了。

$[pos+1,r]$ 呢？倒过来（后缀变前缀）一样整一遍即可。

实现上，求 $l_i,r_i$ 直接单调栈即可。复杂度瓶颈在 ST 表的 $O(n\log n) -O(1)$ ，用转01 RMQ 后整线性的 ST 表也可以做到 $O(n)-O(1)$ 。

代码很好写+好调。。代码后面留了个 gen。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;
int A[MAXN] , p[19][MAXN] , L[MAXN] , R[MAXN] , lg[MAXN];
ll f[MAXN] , F[MAXN] , g[MAXN] , G[MAXN];
int stk[MAXN] , top;

namespace gen{
	typedef unsigned long long ull;
	ull s,a,b,c,lastans=0;
	void in( ) { cin >> s >> a >> b >> c; }
	ull rand(){
		return s^=(a+b*lastans)%c;
	}
};

void solve() {
	int typ; cin >> n >> q >> typ;
	lg[0] = -1;
	rep( i , 1 , n ) scanf("%d",&A[i]) , p[0][i] = i , lg[i] = lg[i >> 1] + 1;
	rep( i , 1 , 18 ) for( int j = 1 ; j + ( 1 << i ) - 1 <= n ; ++ j ) 
		p[i][j] = ( A[p[i - 1][j]] < A[p[i - 1][j + ( 1 << i - 1 )]] ? p[i - 1][j] : p[i - 1][j + ( 1 << i - 1 )] );
	rep( i , 1 , n ) {
		while( top && A[stk[top]] > A[i] ) R[stk[top]] = i , -- top;
		stk[++ top] = i;
	}
	while( top ) R[stk[top]] = n + 1 , -- top;
	per( i , n , 1 ) {
		while( top && A[stk[top]] > A[i] ) L[stk[top]] = i , -- top;
		stk[++ top] = i;
	}
	while( top ) L[stk[top]] = 0 , -- top;
	per( i , n , 1 ) F[i] = F[R[i]] + A[i] * 1ll * ( R[i] - i ) , f[i] = f[i + 1] + F[i];
	rep( i , 1 , n ) G[i] = G[L[i]] + A[i] * 1ll * ( i - L[i] ) , g[i] = g[i - 1] + G[i];
	int l , r , pos , len;
	unsigned long long re = 0 , res = 0;
	if( !typ ) {
		while( q-- ) {
			scanf("%d%d",&l,&r);
			len = lg[r - l + 1];
			pos = ( A[p[len][l]] < A[p[len][r - ( 1 << len ) + 1]] ? p[len][l] : p[len][r - ( 1 << len ) + 1] );
			res = f[l] - f[pos] - ( pos - l ) * F[pos] + g[r] - g[pos] - ( r - pos ) * G[pos] + ( pos - l + 1 ) * 1ll * ( r - pos + 1 ) * A[pos];
			re ^= res;
		}
	} else {
		gen::in();
		while( q-- ) {
			l = gen::rand() % n + 1 , r = gen::rand() % n + 1;
			if( l > r ) swap( l , r );
			len = lg[r - l + 1];
			pos = ( A[p[len][l]] < A[p[len][r - ( 1 << len ) + 1]] ? p[len][l] : p[len][r - ( 1 << len ) + 1] );
			res = f[l] - f[pos] - ( pos - l ) * F[pos] + g[r] - g[pos] - ( r - pos ) * G[pos] + ( pos - l + 1 ) * 1ll * ( r - pos + 1 ) * A[pos];
			gen::lastans = res;
			re ^= res;
		}
	}
	cout << re << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

/*
void solve() {
	srand( (long long) new char );
	n = 10 , m = 10;
	cout << n << ' ' << m << endl;
	rep( i , 1 , n ) printf("%d ",rand() % 2000000000 - 1000000000 + 1);
	puts("");
	rep( i , 1 , m ) {
		int l = rand() % n + 1 , r = rand() % n + 1;
		if( l > r ) swap( l , r );
		printf("%d %d\n",l,r);
	}
}
*/