problem

有這樣一道簡單題：給定一個序列求所有區(qū)間的最大值的和。

還有這樣一道簡單題：給定一個序列求所有區(qū)間的乘積的和。

眾所周知：簡單題 + 簡單題 = 簡單題。

所以，給定一個長為 $n$ 的正整數(shù)序列，定義一個區(qū)間的權(quán)值是該區(qū)間的數(shù)的乘積乘上該區(qū)間的最大值，
求該序列所有區(qū)間的權(quán)值和，答案對 $mod$ 取模。

solution

套路地枚舉最大值。

得到其作為最大值時管轄的范圍 $[l,r]$。

然后就是計(jì)算所有的情況，${?}_{l\le i<pos}{?}_{pos<j\le r}{\prod }_{k=i}^j{a}_k?a_{pos}$

這種橫跨中間點(diǎn)需要左右的子樹信息的操作，很容易聯(lián)想到二叉樹之類的樹形結(jié)構(gòu)。

這里有“最大值”要求，所以我們選擇建立大根堆的笛卡爾樹。

天然地左右兩個兒子的子樹內(nèi)的點(diǎn)都是小于自己權(quán)值的。

然后就是搜樹，在搜笛卡爾樹時從下往上地類似線段樹維護(hù)區(qū)間內(nèi)一段連續(xù)前綴，一段連續(xù)后綴，整體區(qū)間的相關(guān)信息轉(zhuǎn)移合并。

code

#include <bits/stdc++.h> using namespace std; #define maxn 10000005 #define int long long int n, s, l, r, mod; vector < int > a;namespace GenHelper {unsigned z1, z2, z3, z4, b;unsigned rand_() {b = ((z1 << 6) ^ z1) >> 13;z1 = ((z1 & 4294967294U) << 18) ^ b;b = ((z2 << 2) ^ z2) >> 27;z2 = ((z2 & 4294967288U) << 2) ^ b;b = ((z3 << 13) ^ z3) >> 21;z3 = ((z3 & 4294967280U) << 7) ^ b;b = ((z4 << 3) ^ z4) >> 12;z4 = ((z4 & 4294967168U) << 13) ^ b;return (z1 ^ z2 ^ z3 ^ z4);}}std::vector<int> get (int n, unsigned s, int l, int r) {std::vector<int> a;using namespace GenHelper;z1 = s;z2 = unsigned((~s) ^ 0x233333333U);z3 = unsigned(s ^ 0x1234598766U);z4 = (~s) + 51;for (int i = 1; i <= n; i ++) {int x = rand_() & 32767;int y = rand_() & 32767;a.push_back(l + (x * 32768 + y) % (r - l + 1));}return a; }int root, ans; int lson[maxn], rson[maxn]; struct node { int pre, suf, all; };void build() {for( int i = 0;i < n;i ++ ) lson[i] = -1, rson[i] = -1;stack < int > sta;for( int i = 0;i < n;i ++ ) {while( ! sta.empty() and a[sta.top()] <= a[i] ) lson[i] = sta.top(), sta.pop();if( ! sta.empty() ) rson[sta.top()] = i;sta.push( i );}while( ! sta.empty() ) root = sta.top(), sta.pop(); }node dfs( int now, int l, int r ) {node L = { 1, 1, 1 }, R = { 1, 1, 1 };if( ~ lson[now] ) L = dfs( lson[now], l, now - 1 );if( ~ rson[now] ) R = dfs( rson[now], now + 1, r );ans = ( ans + a[now] * a[now] % mod * L.suf % mod * R.pre ) % mod;int pre = ( L.pre + L.all * R.pre % mod * a[now] ) % mod;int suf = ( R.suf + R.all * L.suf % mod * a[now] ) % mod;int all = L.all * R.all % mod * a[now] % mod;return { pre, suf, all }; }signed main() {freopen( "tio.in", "r", stdin );freopen( "tio.out", "w", stdout );scanf( "%lld %lld %lld %lld %lld", &n, &s, &l, &r, &mod );a = get( n, s, l, r );build();dfs( root, 0, n - 1 );printf( "%lld\n", ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的技术情报局（笛卡尔树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。