BZOJ 4540 Hnoi 2016シーケンス【莫隊+RMQ+単調スタック前処理】*
BZOJ 4540 Hnoi 2016シーケンス
Description
与えられた長さnのシーケンス:a 1,a 2,...,an,はa[1:n]と記す.同様に、a[l:r](1≦l≦r≦N)は、シーケンス:al,al+1,...,ar−1,arを指す.1≦l≦s≦t≦r≦nの場合、a[s:t]はa[l:r]のサブシーケンスと呼ばれる.現在、q個のクエリがあり、各クエリは2つの数lとr、1≦l≦r≦nを与え、a[l:r]の異なるサブシーケンスの最小値の和を求める.例えば、与えられたシーケンス5,2,4,1,3は、与えられた2つの数が1と3であることを尋ねると、a[1:3]には6個のサブシーケンスa[1:1]、a[2:2]、a[2:2]、a[2:3]、a[1:3]a[1:3]、a[1:3:2]、a[3:3]、a[1:2:2]、a[2:3]、a[1:3]があり、この6個のサブシーケンスの最小値の和は5+2+4+2+2=17である.
Input
入力ファイルの最初の行には、シーケンス長とクエリ数を表す2つの整数nとqが含まれます.次の行には、n個の整数が含まれ、スペースで区切られ、i番目の整数はai、すなわちシーケンスi番目の要素の値です.次にq行は、各行に2つの整数lとrを含み、1回のクエリを表す.
Output
質問のたびに、質問の答えを表す行を出力します.
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
まず、区間を左に延びる点を考えてみると、この新しい区間では、追加の寄与はlを左端点とし、l+1~rのすべてのノードを右ノードとする寄与であり、その後、iを左端点とし、i+1~nのすべての点を右ノードとする答えを接頭辞と処理することができることが明らかになった.しかし、接頭辞和の情報は、現在のノードよりも前のノードからしか変換できないことがわかりました.また、この区間では、区間の最小値が右の部分にある答えが区間の最小値であるため、STテーブルで前処理して、区間の最小値を見つけました.そして残りの部分は接頭辞と処理でいいです.そして接頭辞和を処理するときは正逆処理が必要です.単調スタックでメンテナンスすればいいです.
そしてモグ演算の順番に注意!!!
Description
与えられた長さnのシーケンス:a 1,a 2,...,an,はa[1:n]と記す.同様に、a[l:r](1≦l≦r≦N)は、シーケンス:al,al+1,...,ar−1,arを指す.1≦l≦s≦t≦r≦nの場合、a[s:t]はa[l:r]のサブシーケンスと呼ばれる.現在、q個のクエリがあり、各クエリは2つの数lとr、1≦l≦r≦nを与え、a[l:r]の異なるサブシーケンスの最小値の和を求める.例えば、与えられたシーケンス5,2,4,1,3は、与えられた2つの数が1と3であることを尋ねると、a[1:3]には6個のサブシーケンスa[1:1]、a[2:2]、a[2:2]、a[2:3]、a[1:3]a[1:3]、a[1:3:2]、a[3:3]、a[1:2:2]、a[2:3]、a[1:3]があり、この6個のサブシーケンスの最小値の和は5+2+4+2+2=17である.
Input
入力ファイルの最初の行には、シーケンス長とクエリ数を表す2つの整数nとqが含まれます.次の行には、n個の整数が含まれ、スペースで区切られ、i番目の整数はai、すなわちシーケンスi番目の要素の値です.次にq行は、各行に2つの整数lとrを含み、1回のクエリを表す.
Output
質問のたびに、質問の答えを表す行を出力します.
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
まず、区間を左に延びる点を考えてみると、この新しい区間では、追加の寄与はlを左端点とし、l+1~rのすべてのノードを右ノードとする寄与であり、その後、iを左端点とし、i+1~nのすべての点を右ノードとする答えを接頭辞と処理することができることが明らかになった.しかし、接頭辞和の情報は、現在のノードよりも前のノードからしか変換できないことがわかりました.また、この区間では、区間の最小値が右の部分にある答えが区間の最小値であるため、STテーブルで前処理して、区間の最小値を見つけました.そして残りの部分は接頭辞と処理でいいです.そして接頭辞和を処理するときは正逆処理が必要です.単調スタックでメンテナンスすればいいです.
そしてモグ演算の順番に注意!!!
#includereturn a.lreturn (a.first0]=-1;for(int i=1;i<=n;i++)lg2[i]=lg2[i>>1]+1;
for(LL i=1;i<=n;i++)ST[i][0]=(pi){w[i],i};
for(LL k=1;k<=18;k++)
for(LL i=1;i+(1<1<=n;i++)
ST[i][k]=compare(ST[i][k-1],ST[i+(1<1)][k-1]);
}
LL query(LL l,LL r){
LL k=lg2[r-l+1];
return compare(ST[l][k],ST[r-(1<1][k]).second;
}
void init(){
s[top=0]=0;
for(LL i=1;i<=n;i++){
while(top&&w[i]<=w[s[top]])top--;
sum1[i]=sum1[s[top]]+(i-s[top])*w[i];
s[++top]=i;
}
s[top=0]=n+1;
for(LL i=n;i>=1;i--){
while(top&&w[i]<=w[s[top]])top--;
sum2[i]=sum2[s[top]]+(s[top]-i)*w[i];
s[++top]=i;
}
}
LL queryL(int l,int r){
int tmp=query(l,r);
return (r-tmp+1)*w[tmp]+sum2[l]-sum2[tmp];
}
LL queryR(int l,int r){
int tmp=query(l,r);
return (tmp-l+1)*w[tmp]+sum1[r]-sum1[tmp];
}
int main(){
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;i++)scanf("%lld",&w[i]);
for(LL i=1;i<=m;i++)scanf("%lld%lld",&p[i].l,&p[i].r),p[i].id=i;
siz=sqrt(n);
for(LL i=1;i<=n;i++)block[i]=(i-1)/siz+1;
sort(p+1,p+m+1,cmp);
STpre();
init();
int l=1,r=0;
for(LL i=1;i<=m;i++){
while(rwhile(l>p[i].l)res+=queryL(--l,r);
while(r>p[i].r)res-=queryR(l,r--);
while(l
for(LL i=1;i<=m;i++)printf("%lld
",ans[i]);
return 0;
}