脚本宝典收集整理的这篇文章主要介绍了「HNOI2016」序列，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
[HNOI2016]序列 草稿纸
P3246 [HNOI2016]序列 给定一个长度为n的序列，q个询问，每次询问[l,r]的所有子段的最小值之和。
设f[i]为以i为右端点的区间答案，PRe[i]为i左边第一个比a[i]小的数的位置。 可以发现如果这个左端点<=pre[i]，其实右端点放在Pre[i]和放在i答案是一样的。 所以有(f[i]=a[i]*(i-pre[i])+f[pre[i]]) (=>f[i]-f[pre[i]]=a[i]*(i-pre[i]))（其实是左端点在pre[i]+1~i之间，右端点在i的答案） 又或者(f[i]=a[i]*(i-pre[i])+a[pre[i]]*(pre[i]-pre[pre[i]])+f[pre[pre[i]]]) (=>f[i]-f[pre[pre[i]]]=(f[i]-f[pre[i]])+(f[pre[i]]-f[pre[pre[i]]])=a[i]*(i-pre[i])+a[pre[i]]*(pre[i]-pre[pre[i]]))（其实是左端点在pre[pre[i]]+1~i之间，右端点在i的答案）(这样一定可以处理左端点为i左边一个比i小的数到i这个区间的答案)
然后就考虑左端点在([l,r])，右端点在(r+1)的答案.... 那么其实可以p=r+1; while (pre[p]>=l) p=pre[p]; 其实发现这样最后得到的p就是[l,r+1]的最小值位置，用RMQ可以O1或OLOGn求出 r+1的时候答案的增量计算分为两部分 对于左端点在([p+1,r+1])，右端点在(r+1)的部分，答案就为(f[r+1]-f[p])； 对于左端点在([l,p])，右端点在(r+1)的部分，答案就为(a[p]*(p-l+1)) 这样可以离线询问Onsqrtn莫队完成
在线怎么写（ 直接考虑一个区间([l,r])的答案 w...怎么搞呢 考虑右端点在r的答案...同样找出一个最小值位置p。 那么左端点在([p+1,r])的答案是(f[r]-f[p]) 草 右端点在(r-1)，左端点在([p+1,r-1])的答案是(f[r-1]-f[p]) 那左端点在([p+1,右端点])，右端点在([p+1,r])，也即([p+1,r])区间内的答案为 (( Sigma_{i = p+1}^{r} f[i] ) - f[p]*(r-p)) 对f做个前缀和数组c 答案就是 (c[r]-c[p]-f[p]*(r-p))
([l,p-1])区间内的答案，可以倒过来求的样子（ 答案是 (c[p-1]-c[l-1]-f[p]*(p-l))
覆盖p的区间答案，(a[p]*(p-l+1)*(r-p+1))。
QAQ 完结....居然写了这么久思路才理清楚
code: 一遍过样例，爆long long 喜提0pts，暴躁kkz在线#define int long long
#include <algorIThm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN (int)(1e5+233)
#define MAXA (int)(1e9+233)
#include <stack>
struct qwq
{
long long a,id;
};
stack<qwq> st;
#define int long long
int a[MAXN];
int n,q;
int prer[MAXN],prel[MAXN];
inline void mostack()
{
for (int i=1;i<=n;i++)
{
while (!st.empty()&&st.top().a>a[i])
{
prer[st.top().id]=i;
st.pop();
}
st.push((qwq){a[i],i});
}
while (!st.empty()) st.pop();
for (int i=n;i;i--)
{
while (!st.empty()&&st.top().a>a[i])
{
prel[st.top().id]=i;
st.pop();
}
st.push((qwq){a[i],i});
}
return;
}
int ans[MAXN<<2];
#define leftson cur<<1
#define rightson cur<<1|1
#define mid ((l+r)>>1)
#define push_up if (a[ans[leftson]]<a[ans[rightson]]) ans[cur]=ans[leftson]; else ans[cur]=ans[rightson]
void build(int cur,int l,int r)
{
if (l==r)
{
ans[cur]=l;
return;
}
build(leftson,l,mid);
build(rightson,mid+1,r);
push_up;
}
int query(int ql,int qr,int cur,int l,int r)
{
if (ql<=l&&r<=qr) return ans[cur];
int answer=0;
if (ql<=mid) answer=query(ql,qr,leftson,l,mid);
if (qr>;mid) { int tt=query(ql,qr,rightson,mid+1,r); if (!answer) answer=tt; else answer=(a[tt]>a[answer]?answer:tt); }
return answer;
}
inline void RMQINIT() { build(1,1,n); return; }
long long fl[MAXN],cl[MAXN],fr[MAXN],cr[MAXN];
inline void FINIT()
{
for (int i=1;i<=n;i++)
fl[i]=a[i]*(i-prel[i])+fl[prel[i]];
for (int i=n;i;i--)
fr[i]=a[i]*(prer[i]-i)+fr[prer[i]];
for (int i=1;i<=n;i++)
cl[i]=cl[i-1]+fl[i];
for (int i=n;i;i--)
cr[i]=cr[i+1]+fr[i];
return;
}
signed main()
{
scanf("%lld%lld",&n,&q);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
mostack();
RMQINIT();
FINIT();
int l,r,p;
long long ans=0;
while (q--)
{
scanf("%lld%lld",&l,&r);
p=query(l,r,1,1,n);
ans=0;
if (p+1<=r) ans=cl[r]-cl[p]-fl[p]*(r-p);
if (p-1>=l) ans+=cr[l]-cr[p]-fr[p]*(p-l);
ans+=a[p]*(p-l+1)*(r-p+1);
printf("%lldn",ans);
}
return 0;
}
以上是脚本宝典为你收集整理的「HNOI2016」序列全部内容，希望文章能够帮你解决「HNOI2016」序列所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。