4540: [Hnoi2016]序列
Time Limit: 20 Sec Memory Limit: 512 MB
[ Submit][ Status][ Discuss]
Description
给定长度为n的序列：a1,a2,…,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个询问，每个询问给定两个数l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。
Input
输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。
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
Source
昨天晚上搞到现在终于过了,WA了几发,结果是没开long long
首先要先RMQ,处理前后第一个比它小的数
然后预处理转移时改变的值
感觉有些复杂
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
int n,m,st[N][20],last[N],next[N],bel[N],sta[N];
ll ans,Ans[N],sl[N],sr[N],a[N];
struct data{ int l,r,last,id; }da[N];
bool cmp( data a, data b ){ return a.last != b.last ? a.last < b.last : a.r < b.r; }
int query( int l, int r ){
int pr = bel[r-l+1], las = r-(1<<pr)+1;
if( a[st[l][pr]] <= a[st[las][pr]] ) return st[l][pr]; return st[las][pr];
}
ll call( int l, int r ){int mn = query(l,r); ll res = (r-mn+1)*a[mn] + sr[l] - sr[mn]; return res;}
ll calr( int l, int r ){int mn = query(l,r); ll res = (mn-l+1)*a[mn] + sl[r] - sl[mn]; return res;}
void init(){
for( int p = 1; p <= 17; p++ )
for( int i = 1; i <= n; i++ ){
if( i+(1<<(p-1)) <= n && a[st[i][p-1]] <= a[st[i+(1<<(p-1))][p-1]] ) st[i][p] = st[i][p-1];
else st[i][p] = st[i+(1<<(p-1))][p-1];
}
int top = 0; sta[0]=0;
for( int i = 1; i <= n; i++ ){
while( top > 0 && a[i] < a[sta[top]] ) next[sta[top]] = i,top--;
last[i] = sta[top]; sta[++top] = i;
}
while( top > 0 ) next[sta[top--]] = n+1;
for( int i = 1; i <= n; i++ ) sl[i] = sl[last[i]] + (ll)(i-last[i])*a[i];
for( int i = n; i >= 1; i-- ) sr[i] = sr[next[i]] + (ll)(next[i]-i)*a[i];
bel[1] = 0; for( int i = 2; i <= n; i++ ) bel[i] = bel[i>>1]+1;
}
void capmo(){
ans = a[1];
for (int i = 1, l = 1, r = 1; i <= m; i++ ){
while( r < da[i].r ) ans += calr(l,++r);
while( r > da[i].r ) ans -= calr(l,r--);
while( l < da[i].l ) ans -= call(l++,r);
while( l > da[i].l ) ans += call(--l,r);
Ans[da[i].id] = ans;
}
}
int main(){
scanf("%d%d", &n, &m);
for( int i = 1; i <= n; i++ ) scanf("%lld", &a[i]), st[i][0] = i;
int block = (int)sqrt(n);
for( int i = 1; i <= m; i++ ) {
scanf("%d%d", &da[i].l, &da[i].r);
da[i].id = i; da[i].last = (da[i].l-1)/block+1;
}
std::sort(da+1,da+m+1,cmp);
init(); capmo();
for( int i = 1; i <= m; i++ ) printf("%lld\n", Ans[i]);
return 0;
}