NC20555. [HNOI2016]序列
描述
输入描述
输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开 ,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。
输出描述
对于每次询问，输出一行，代表询问的答案。
示例1
输入:
5 5 5 2 4 1 3 1 5 1 3 2 4 3 5 2 5
输出:
28 17 11 11 17
C++14(g++5.4) 解法, 执行用时: 203ms, 内存消耗: 13920K, 提交时间: 2019-10-29 22:09:16
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,m,block;
int a[N];
struct query { int l,r,id; } q[N];
int sta[N],top=0;
int L[N],R[N];
ll f[N],g[N],ans[N];
int st[20][N],lg[N];
inline int cmp(query a,query b) {
return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void build() {
for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for (re int i=1;i<=n;++i) st[0][i]=i;
for (re int i=1;i<=lg[n];++i)
for (re int j=1;j+(1<<(i-1))<=n;++j) {
int x=st[i-1][j],y=st[i-1][j+(1<<(i-1))];
st[i][j]=a[x]<=a[y]?x:y;
}
}
inline int query(int l,int r) {
int t=lg[r-l+1],x=st[t][l],y=st[t][r-(1<<t)+1];
return a[x]<=a[y]?x:y;
}
inline ll calcL(int l,int r) {
int p=query(l,r);
return 1ll*(r-p+1)*a[p]+g[l]-g[p];
}
inline ll calcR(int l,int r) {
int p=query(l,r);
return 1ll*(p-l+1)*a[p]+f[r]-f[p];
}
int main() {
n=read(),m=read(),block=sqrt(n);
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
//calc L R f g
for (re int i=1;i<=n;++i) {
while (top&&a[sta[top]]>a[i]) --top;
L[i]=sta[top],sta[++top]=i;
}
sta[top=0]=n+1;
for (re int i=n;i>=1;--i) {
while (top&&a[sta[top]]>a[i]) --top;
R[i]=sta[top],sta[++top]=i;
}
for (re int i=1;i<=n;++i) f[i]=f[L[i]]+1ll*(i-L[i])*a[i];
for (re int i=n;i>=1;--i) g[i]=g[R[i]]+1ll*(R[i]-i)*a[i];
//init RMQ
build();
//solve
ll res=0;
for (re int i=1,l=1,r=0;i<=m;++i) {
while (r<q[i].r) res+=calcR(l,++r);
while (l>q[i].l) res+=calcL(--l,r);
while (r>q[i].r) res-=calcR(l,r--);
while (l<q[i].l) res-=calcL(l++,r);
ans[q[i].id]=res;
}
for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}
C++ 解法, 执行用时: 84ms, 内存消耗: 15996K, 提交时间: 2021-08-19 17:04:43
#include <bits/stdc++.h>
#define ri int
#define ll long long
using namespace std;
const int Maxn=1e5;
const int Lgn=17;
stack<int>s;
int pre[Maxn+5],suf[Maxn+5],n,m;
int st[Maxn+5][Lgn+5],lg[Maxn+5];
ll f_pre[Maxn+5],g_pre[Maxn+5],f_suf[Maxn+5],g_suf[Maxn+5],a[Maxn+5];
int query(int l,int r) {
int t=lg[r-l+1];
if(a[st[l][t]]<a[st[r-(1<<t)+1][t]])return st[l][t];
return st[r-(1<<t)+1][t];
}
int main() {
scanf("%d%d",&n,&m);
lg[0]=-1;
for(ri i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
for(ri i=1;i<=n;i++)scanf("%lld",&a[i]),st[i][0]=i;
a[0]=a[n+1]=-1e9-1;
for(ri j=1;j<=lg[n];j++)
for(ri i=1;i<=n-(1<<j)+1;i++) {
int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
if(a[x]<a[y])st[i][j]=x;
else st[i][j]=y;
}
s.push(0);
for(ri i=1;i<=n;i++) {
while(!s.empty()&&a[s.top()]>a[i])s.pop();
pre[i]=s.top();
s.push(i);
}
while(!s.empty())s.pop();
s.push(n+1);
for(ri i=n;i>=1;i--) {
while(!s.empty()&&a[s.top()]>a[i])s.pop();
suf[i]=s.top();
s.push(i);
}
for(ri i=1;i<=n;i++) {
f_pre[i]=f_pre[pre[i]]+a[i]*(i-pre[i]);
g_pre[i]=g_pre[i-1]+f_pre[i];
}
for(ri i=n;i>=1;i--) {
f_suf[i]=f_suf[suf[i]]+a[i]*(suf[i]-i);
g_suf[i]=g_suf[i+1]+f_suf[i];
}
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
int x=query(l,r);
printf("%lld\n",a[x]*(r-x+1)*(x-l+1)+g_pre[r]-g_pre[x]-f_pre[x]*(r-x)+g_suf[l]-g_suf[x]-f_suf[x]*(x-l));
}
return 0;
}