序列
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 2 4 1 3
1 5
1 3
2 4
3 5
2 5
Sample Output
17
11
11
17
HINT
1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9
Solution
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = ;
const int INF = ; int n,m;
int block[ONE],Q;
int a[ONE],pL[ONE],pR[ONE];
int stk[ONE],top;
int Log[ONE],Bin[ONE],MinD[ONE][],NumD[ONE][];
s64 Fl[ONE],Fr[ONE];
s64 ans,Ans[ONE]; struct power
{
int id;
int l,r;
}oper[ONE]; inline bool cmp(const power &a,const power &b)
{
if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];
return a.r < b.r;
} inline int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} inline void Pre_Rmq()
{
Log[]=-; for(int i=;i<=n;i++) Log[i] = Log[i>>] + ;
Bin[]=; for(int i=;i<=; i++) Bin[i] = Bin[i-] << ; for(int j=;j<=;j++)
for(int i=;i<=n;i++)
if(i+Bin[j]- <= n)
{
int Next = i + Bin[j-];
if(MinD[i][j-] < MinD[Next][j-])
MinD[i][j] = MinD[i][j-], NumD[i][j] = NumD[i][j-];
else
MinD[i][j] = MinD[Next][j-], NumD[i][j] = NumD[Next][j-];
}
else break;
} inline int Get(int x,int y)
{
int T = Log[y - x +];
if(MinD[x][T] < MinD[y-Bin[T]+][T]) return NumD[x][T];
return NumD[y-Bin[T]+][T];
} inline void MakepL()
{
top = ;
for(int i=n;i>=;i--)
{
while(top && a[stk[top]] > a[i])
pL[stk[top--]] = i;
stk[++top] = i;
}
while(top) pL[stk[top--]] = ;
for(int i=;i<=n;i++) pL[i]++;
} inline void MakepR()
{
top = ;
for(int i=;i<=n;i++)
{
while(top && a[stk[top]] > a[i])
pR[stk[top--]] = i;
stk[++top] = i;
}
while(top) pR[stk[top--]] = n+;
for(int i=;i<=n;i++) pR[i]--;
} inline s64 DealL(int l,int r)
{
int pos = Get(l,r);
return (s64)a[pos] * (r-pos+) + Fr[l] - Fr[pos];
} inline s64 DealR(int l,int r)
{
int pos = Get(l,r);
return (s64)a[pos] * (pos-l+) + Fl[r] - Fl[pos];
} int main()
{
n = get(); m = get(); Q = sqrt(n);
for(int i=;i<=n;i++)
{
a[i] = get(); block[i] = (i-)/Q+;
MinD[i][] = a[i]; NumD[i][] = i;
} Pre_Rmq(); MakepL(); MakepR();
for(int i=;i<=n;i++) Fl[i] = Fl[pL[i]-] + (s64)(i-pL[i]+) * a[i];
for(int i=n;i>=;i--) Fr[i] = Fr[pR[i]+] + (s64)(pR[i]-i+) * a[i]; for(int i=;i<=m;i++)
{
oper[i].id = i;
oper[i].l = get(); oper[i].r = get();
}
sort(oper+, oper+m+, cmp); int l = , r = ;
for(int i=;i<=m;i++)
{
while(r < oper[i].r) ans += DealR(l,++r);
while(oper[i].l < l) ans += DealL(--l,r);
while(r > oper[i].r) ans -= DealR(l,r--);
while(oper[i].l > l) ans -= DealL(l++,r); Ans[oper[i].id] = ans;
} for(int i=;i<=m;i++)
printf("%lld\n",Ans[i]);
}
【BZOJ4540】【HNOI2016】序列 [莫队][RMQ]的更多相关文章
-
[BZOJ4540][HNOI2016]序列 莫队
4540: [Hnoi2016]序列 Time Limit: 20 Sec Memory Limit: 512 MB Description 给定长度为n的序列:a1,a2,…,an,记为a[1:n ...
-
[bzoj4540][Hnoi2016][序列] (莫队算法+单调栈+st表)
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 ...
-
【BZOJ4540】[Hnoi2016]序列 莫队算法+单调栈
[BZOJ4540][Hnoi2016]序列 Description 给定长度为n的序列:a1,a2,…,an,记为a[1:n].类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,…,a ...
-
BZOJ.4540.[HNOI2016]序列(莫队/前缀和/线段树 单调栈 RMQ)
BZOJ 洛谷 ST表的一二维顺序一定要改过来. 改了就rank1了哈哈哈哈.自带小常数没办法. \(Description\) 给定长为\(n\)的序列\(A_i\).\(q\)次询问,每次给定\( ...
-
BZOj 4540: [Hnoi2016]序列 [莫队 st表 预处理]
4540: [Hnoi2016]序列 题意:询问区间所有子串的最小值的和 不强制在线当然上莫队啦 但是没想出来,因为不知道该维护当前区间的什么信息,维护前后缀最小值的话不好做 想到单调栈求一下,但是对 ...
-
洛谷P3246 [HNOI2016]序列 [莫队]
传送门 思路 看到可离线.无修改.区间询问,相信一定可以想到莫队. 然而,莫队怎么转移是个大问题. 考虑\([l,r]\rightarrow[l,r+1]\)时答案会怎样变化?(左端点变化时同理) \ ...
-
bzoj 4540: [Hnoi2016]序列 莫队
题目: 给定长度为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 ...
-
BZOJ 4540 [Hnoi2016]序列 | 莫队 详细题解
传送门 BZOJ 4540 题解 --怎么说呢--本来想写线段树+矩阵乘法的-- --但是嘛--yali的机房太热了--困--写不出来-- 于是弃疗,写起了莫队.(但是我连莫队都想不出来!) 首先用单 ...
-
BZOJ4540 Hnoi2016 序列 【莫队+RMQ+单调栈预处理】*
BZOJ4540 Hnoi2016 序列 Description 给定长度为n的序列:a1,a2,-,an,记为a[1:n].类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,-,ar- ...
随机推荐
-
OpenCV2邻域和模板操作
在图像处理中,通过当前位置的邻域像素计算新的像素值是很常见的操作.当邻域包含图像的上几行和下几行时,就需要同时扫描图像的若干行,这就是图像的邻域操作了.至于模板操作是实现空间滤波的基础,通常是使用一个 ...
-
HttpClient_4 用法 由HttpClient_3 升级到 HttpClient_4 必看
转自:http://www.blogjava.net/stevenjohn/archive/2012/09/26/388609.html HttpClient程序包是一个实现了 HTTP 协议的客户端 ...
-
Windows Server 2016软件定义存储:Storage Spaces Direct的关键特性
[TechTarget中国原创] 微软在Windows Server 2016 Technical Preview 2中引入了Storage Spaces Direct.这个特性将本地存储扩展为高可用 ...
-
python 代码片段4
#coding=utf-8 # 任何等于0的数值被认为是False,所有非零的数字被认为True, # 空的容器为False,飞控容器酒味True. download_complete=False p ...
-
get 与 post
<form action="Default.aspx" method="get"> get 服务器端 用request.querystring来获 ...
-
javascript中的substr和substring
1.substr 方法 返回一个从指定位置开始的指定长度的子字符串. stringvar.substr(start [, length ]) 参数: stringvar 必选项. 要提取子字符串的字 ...
-
无法连接ssh,fatal: daemon() failed: No such device
今天发现一个服务器的sshd无法启动,查看/var/log/secure里发现:fatal: daemon() failed: No such device 解决办法: rm /dev/null /d ...
-
JS开发之CommonJs和AMD/CMD规范
CommonJS是主要为了JS在后端的表现制定的,他是不适合前端的,AMD(异步模块定义)出现了,它就主要为前端JS的表现制定规范. 在兼容CommonJS的系统中,你可以使用JavaScript开发 ...
-
如何识别网页类型(wap页面还是wise页面)
思路很简单,就是通过网页结构的一些特征来区分,当然也可以通过url的格式来区分,不过这个错误率较高,因为有很多小网站的url设计不规范. 网页特征包括两大类: 1.meta信息: 一般wap页面都会为 ...
-
【转 :Hibernate 缓存机制】
转自:http://www.cnblogs.com/wean/archive/2012/05/16/2502724.html Hibernate 缓存机制 一.why(为什么要用Hibernate缓存 ...