#2051. 「HNOI2016」序列
题目描述
给定长度为 n nn 的序列：a1,a2,⋯,an a_1, a_2, \cdots , a_na1,a2,⋯,an，记为 a[1:n] a[1 \colon n]a[1:n]。类似地，a[l:r] a[l \colon r]a[l:r]（1≤l≤r≤N 1 \leq l \leq r \leq N1≤l≤r≤N）是指序列：al,al+1,⋯,ar−1,ar a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_ral,al+1,⋯,ar−1,ar。若 1≤l≤s≤t≤r≤n1\leq l \leq s \leq t \leq r \leq n1≤l≤s≤t≤r≤n，则称 a[s:t] a[s \colon t]a[s:t]是 a[l:r] a[l \colon r]a[l:r] 的子序列。
现在有 q qq 个询问，每个询问给定两个数 l ll 和 r rr，1≤l≤r≤n 1 \leq l \leq r \leq n1≤l≤r≤n，求 a[l:r] a[l \colon r]a[l:r] 的不同子序列的最小值之和。例如，给定序列 5,2,4,1,3 5, 2, 4, 1, 35,2,4,1,3，询问给定的两个数为 1 11 和 3 33，那么 a[1:3] a[1 \colon 3]a[1:3] 有 6 66 个子序列 a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3]a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这 666 个子序列的最小值之和为 5+2+4+2+2+2=175+2+4+2+2+2=175+2+4+2+2+2=17。
输入格式
输入文件的第一行包含两个整数 n nn 和 q qq，分别代表序列长度和询问数。
接下来一行，包含 n nn 个整数，以空格隔开，第 i ii 个整数为 ai a_iai，即序列第 iii 个元素的值。
接下来 q qq 行，每行包含两个整数 l ll 和 r rr，代表一次询问。
输出格式
对于每次询问，输出一行，代表询问的答案。
样例
样例输入
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5样例输出
28
17
11
11
17数据范围与提示
对于 100%100\%100% 的数据，1≤n,q≤100000,∣ai∣≤109 1 \leq n,q \leq 100000 ,|a_i| \leq 10^91≤n,q≤100000,∣ai∣≤109
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,q,a[maxn],L[maxn],R[maxn],to[maxn];
void make(int i){
L[i]=R[i]=i;
int l=i,r=i;
while(a[l-]>=a[i]&&l>)l--;
while(a[r+]>=a[i]&&r<n)r++;
L[i]=l;R[i]=r;
}
int main(){
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)make(i);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(a[i]==a[j]){to[i]=j;break;}
int x,y;
while(q--){
long long ans=;
scanf("%d%d",&x,&y);
for(int i=x;i<=y;i++){
if(to[i]&&i>=L[to[i]])continue;
int l=max(x,L[i]),r=min(y,R[i]);
ans+=1LL*(i-l+)*(r-i+)*a[i];
}
cout<<ans<<endl;
}
}
40分 暴力
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 200010
using namespace std;
long long lg[maxn],mn[maxn][],a[maxn],mnid[maxn][];
long long belong[maxn],Ans[maxn],fl[maxn],fr[maxn],sta[maxn],top;
struct node{
int l,r,id;
bool operator < (const node &b)const{
if(belong[l]==belong[b.l])return r<b.r;
return belong[l]<belong[b.l];
}
}q[maxn];
long long qread(){
long long i=,j=;
char ch=getchar();
while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
return i*j;
}
void pre(long long n){//st表
lg[]=;
for(int i=;i<=n;i++){
lg[i]=lg[i-];
if(i==(<<lg[i]+))lg[i]++;
}
for(int i=n;i>=;i--){
mn[i][]=a[i];
mnid[i][]=i;
for(int j=;i+(<<j)-<=n;j++){
mn[i][j]=min(mn[i][j-],mn[i+(<<j-)][j-]);
if(mn[i][j]==mn[i][j-])mnid[i][j]=mnid[i][j-];
if(mn[i][j]==mn[i+(<<j-)][j-])mnid[i][j]=mnid[i+(<<j-)][j-];
}
}
}
long long query(long long l,long long r){
long long k=lg[r-l+];
if(mn[l][k]<mn[r-(<<k)+][k])return mnid[l][k];
return mnid[r-(<<k)+][k];
}
void dp(long long n,long long *f){//单调栈
sta[top=]=;
for(int i=;i<=n;i++){
while(a[sta[top]]>a[i])top--;
f[i]=(i-sta[top])*a[i]+f[sta[top]];
sta[++top]=i;
}
}
long long up_r(long long l,long long r){
long long p=query(l,r+);
return (p-l+)*a[p]+fl[r+]-fl[p];
}
long long up_l(long long l,long long r){
long long p=query(l-,r);
return (r-p+)*a[p]+fr[l-]-fr[p];
}
int main(){
freopen("Cola.txt","r",stdin);
int n,Q;
n=qread();Q=qread();
a[]=-(1LL<<);
for(int i=;i<=n;i++)a[i]=qread();
pre(n);dp(n,fl);
reverse(a+,a+n+);
dp(n,fr);
reverse(a+,a+n+);reverse(fr+,fr+n+);
int block=sqrt(n)+;
for(int i=;i<=n;i++)belong[i]=(i/block)+;
for(int i=;i<=Q;i++){
q[i].l=qread();q[i].r=qread();
q[i].id=i;
}
sort(q+,q+Q+);
a[]=;
int l=,r=;long long ans=a[];
for(int i=;i<=Q;i++){
while(r<q[i].r)ans+=up_r(l,r++);
while(r>q[i].r)ans-=up_r(l,--r);
while(l>q[i].l)ans+=up_l(l--,r);
while(l<q[i].l)ans-=up_l(++l,r);
Ans[q[i].id]=ans;
}
for(int i=;i<=Q;i++)cout<<Ans[i]<<endl;
return ;
}
100分 莫队+st表+单调栈