题解 P6604 【[HNOI2016]序列 加强版】
yijan
·
·
题解
考虑一次查询，比如查询 [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 倍了。
实现上，求 $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);
}
}
*/
```