當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

[Bzoj4540][Hnoi2016] 序列（莫队 + ST表 + 单调队列）

發(fā)布時(shí)間：2023/12/10 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了 [Bzoj4540][Hnoi2016] 序列（莫队 + ST表 + 单调队列）小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

4540: [Hnoi2016]序列

Time Limit:?20 Sec??Memory Limit:?512 MB
Submit:?1567??Solved:?718
[Submit][Status][Discuss]

Description

　　給定長(zhǎng)度為n的序列：a1,a2,…,an，記為a[1:n]。類(lèi)似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-
1,a_r。若1≤l≤s≤t≤r≤n，則稱(chēng)a[s:t]是a[l:r]的子序列。現(xiàn)在有q個(gè)詢(xún)問(wèn)，每個(gè)詢(xún)問(wèn)給定兩個(gè)數(shù)l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，給定序列5,2,4,1,3，詢(xún)問(wèn)給定的兩個(gè)數(shù)為1和3，那么a[1:3]有
6個(gè)子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，這6個(gè)子序列的最小值之和為5+2+4+2+2+2=17。

Input

　　輸入文件的第一行包含兩個(gè)整數(shù)n和q，分別代表序列長(zhǎng)度和詢(xún)問(wèn)數(shù)。接下來(lái)一行，包含n個(gè)整數(shù)，以空格隔開(kāi)
,第i個(gè)整數(shù)為ai，即序列第i個(gè)元素的值。接下來(lái)q行，每行包含兩個(gè)整數(shù)l和r，代表一次詢(xún)問(wèn)。

Output

　　對(duì)于每次詢(xún)問(wèn)，輸出一行，代表詢(xún)問(wèn)的答案。

Sample Input

5 5 5 2 4 1 3 1 5 1 3 2 4 3 5 2 5

Sample Output

28 17 11 11 17

HINT

1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

分析：

也許是我比較傻吧，我把分塊那里block[i] = i / tot +1打成了 block[i] = block[i] / tot + 1，超時(shí)了半天，調(diào)不出來(lái)……

題目又是沒(méi)有修改，只有查詢(xún)，可以聯(lián)想到莫隊(duì)算法。

題目要求是求一個(gè)大區(qū)間內(nèi)，每個(gè)子區(qū)間最小值之和。我們可以看一下，如果已知一個(gè)區(qū)間[l，r]，那么如果要得到[l，r + 1]，我們會(huì)把[r + 1]的數(shù)添加進(jìn)來(lái)。當(dāng)這個(gè)數(shù)添加進(jìn)來(lái)會(huì)多產(chǎn)生r - l + 2個(gè)子區(qū)間，那么如何處理這個(gè)子區(qū)間呢，就算是用st表暴力去查詢(xún) 這 r - l + 2個(gè)區(qū)間復(fù)雜度結(jié)合每一次也是很高的。

我們可以分析一下：如果我們找到[l，r + 1]里面的最小值，它所在位置為k。那么[l，k]這段區(qū)間的點(diǎn)為左端點(diǎn)和[r +1]所產(chǎn)生的 k - l + 1個(gè)區(qū)間都是以[k]所在數(shù)為最小值，那么貢獻(xiàn)為（k - l + 1） * a[k]，剩下的就是[k + 1，r + 1]這段區(qū)間了。

當(dāng)我們知道一個(gè)數(shù)i左邊第一個(gè)小于等于它的數(shù)的下標(biāo)lm[i]，所以[lm[i] + 1，i - 1]中間的值都是大于[i]的數(shù)的。所以以[lm[i] +1，i]的數(shù)都以[i]的數(shù)為最小值。設(shè)sumr[i]表示以i為右端點(diǎn)的合法區(qū)間的答案，那么sumr[i] = sumr[lm[i]] + （i? - lm[i]） * a[i]。發(fā)現(xiàn)我們的sumr數(shù)組是類(lèi)似于前綴和的形式，最后我們用sum[r +1] - sum[k]就為[k + 1，r + 1]這段區(qū)間答案。

最終一個(gè)區(qū)間答案為ans =? （k - l + 1） * a[k] + sumr[r +1] - sum[k]。

刪除同理，在左端點(diǎn)處添加刪除只需維護(hù)rm[i]和suml[i]。求區(qū)間最小值的位置可以用st表，o（nlogn）的轉(zhuǎn)移，o(1）的查詢(xún)。求一個(gè)數(shù)左右第一個(gè)不大于它的數(shù)可以用單調(diào)隊(duì)列，當(dāng)一個(gè)數(shù)被另一個(gè)數(shù)踢出時(shí)，這個(gè)數(shù)離它最近的相應(yīng)方向上的第一個(gè)不大于它的數(shù)就為另一個(gè)數(shù)。再加上莫隊(duì)算法（nsqrt（n））總時(shí)間復(fù)制度為o（nlogn + nsqrt（n））

?ST表：

類(lèi)似于動(dòng)態(tài)轉(zhuǎn)移的思想，我們知道區(qū)間[l，r]的最小值，就可以推出區(qū)間[l，r + 1]的最小值，但是st表運(yùn)用了倍增的思想（類(lèi)似lca）。

我們知道了每個(gè)數(shù)向右2^（j - 1）的最小值，就能拓展到每個(gè)數(shù)向右2 ^ j 的最小值。

轉(zhuǎn)移方程為?

st[i][j] = min（st[i][j - 1],st[i + (1 << j - 1)][j - 1]）；

具體詳見(jiàn)代碼

附上AC代碼：?

# include <iostream> # include <cmath> # include <cstdio> # include <cstring> # include <algorithm> using namespace std; const int N = 2e5 + 12; int block[N],tot,n,m; struct data{int l,r,id; bool operator <(const data & other)const{if(block[l] == block[other.l])return r < other.r;return block[l] < block[other.l]; } }q[N]; int st[N][31],a[N],mn[N]; int stack[N],cnt; int lm[N],rm[N]; long long suml[N],sumr[N],num,ans[N]; int query(int x,int y){return a[x] < a[y] ? x : y; } int Rmq(int L,int R) { if(L > R)swap(L,R);int k = mn[R - L + 1];return query(st[L][k],st[R - (1 << k) + 1][k]); } void updatal(int x,int y,int z){int pos = Rmq(x,y);num +=(1ll * (y - pos + 1) * a[pos] + sumr[x] - sumr[pos]) * z; }; void updatar(int x,int y,int z){int pos = Rmq(x,y);num +=(1LL * (pos - x + 1) * a[pos] + suml[y] - suml[pos]) * z; }; void Modui(){int L = 1,R = 0; num = 0;for (int i = 1;i <= m;++i){while (R < q[i].r) updatar(L,R + 1,1),R++;while (L > q[i].l) updatal(L - 1,R,1),L--;while (R > q[i].r) updatar(L,R,-1),R--;while (L < q[i].l) updatal(L,R,-1),L++;ans[q[i].id] = num;} } void work(){cnt = 0;for(int i = 1;i <= n;i++){while(cnt && a[stack[cnt]] >= a[i])rm[stack[cnt--]] = i;stack[++cnt] = i;}while(cnt)rm[stack[cnt--]] = n + 1;for(int i = n;i >= 1;i--){while(cnt && a[stack[cnt]] >= a[i])lm[stack[cnt--]] = i;stack[++cnt] = i;}for(int i = 1;i <= n;i++){suml[i] = suml[lm[i]] + 1LL * (i - lm[i]) * a[i];}for(int i = n;i >= 1;i--){sumr[i] = sumr[rm[i]] + 1LL * (rm[i] - i) * a[i];} } void init(){mn[0] = -1;for(int i = 1;i <= n;i++){mn[i]=((i & (i-1))==0) ? mn[i-1]+1 : mn[i-1];st[i][0] = i;}for (int j = 1;j <= mn[n];j++){for (int i = 1;i + (1 << j) - 1 <= n;i++){st[i][j] = query(st[i][j - 1],st[i + (1 << j - 1)][j - 1]);}}work(); } int main(){scanf("%d %d",&n,&m);tot = sqrt(n);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);block[i] = i / tot + 1;}init();for(int i = 1;i <= m;i++){scanf("%d %d",&q[i].l,&q[i].r);q[i].id = i;}sort(q + 1,q + m + 1); Modui();for(int i = 1;i <= m;i++){printf("%lld\n",ans[i]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lzdhydzzh/p/7656539.html

總結(jié)

以上是生活随笔為你收集整理的[Bzoj4540][Hnoi2016] 序列（莫队 + ST表 + 单调队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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