[Bzoj4540][Hnoi2016] 序列(莫队 + ST表 + 单调队列)
4540: [Hnoi2016]序列
?
Time Limit:?20 Sec??Memory Limit:?512 MBSubmit:?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)是指序列:al,al+1,…,ar-
1,ar。若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)題。
- 上一篇: 细说php完美分页类
- 下一篇: 压缩及解压命令