【BZOJ4540】【HNOI2016】序列 [莫队][RMQ]

时间:2022-09-28 20:31:01

序列

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

Solution

  【BZOJ4540】【HNOI2016】序列 [莫队][RMQ]

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]的更多相关文章

  1. &lbrack;BZOJ4540&rsqb;&lbrack;HNOI2016&rsqb;序列 莫队

    4540: [Hnoi2016]序列 Time Limit: 20 Sec  Memory Limit: 512 MB Description 给定长度为n的序列:a1,a2,…,an,记为a[1:n ...

  2. &lbrack;bzoj4540&rsqb;&lbrack;Hnoi2016&rsqb;&lbrack;序列&rsqb; &lpar;莫队算法&plus;单调栈&plus;st表&rpar;

    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 ...

  3. 【BZOJ4540】&lbrack;Hnoi2016&rsqb;序列 莫队算法&plus;单调栈

    [BZOJ4540][Hnoi2016]序列 Description 给定长度为n的序列:a1,a2,…,an,记为a[1:n].类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,…,a ...

  4. BZOJ&period;4540&period;&lbrack;HNOI2016&rsqb;序列&lpar;莫队&sol;前缀和&sol;线段树 单调栈 RMQ&rpar;

    BZOJ 洛谷 ST表的一二维顺序一定要改过来. 改了就rank1了哈哈哈哈.自带小常数没办法. \(Description\) 给定长为\(n\)的序列\(A_i\).\(q\)次询问,每次给定\( ...

  5. BZOj 4540&colon; &lbrack;Hnoi2016&rsqb;序列 &lbrack;莫队 st表 预处理&rsqb;

    4540: [Hnoi2016]序列 题意:询问区间所有子串的最小值的和 不强制在线当然上莫队啦 但是没想出来,因为不知道该维护当前区间的什么信息,维护前后缀最小值的话不好做 想到单调栈求一下,但是对 ...

  6. 洛谷P3246 &lbrack;HNOI2016&rsqb;序列 &lbrack;莫队&rsqb;

    传送门 思路 看到可离线.无修改.区间询问,相信一定可以想到莫队. 然而,莫队怎么转移是个大问题. 考虑\([l,r]\rightarrow[l,r+1]\)时答案会怎样变化?(左端点变化时同理) \ ...

  7. bzoj 4540&colon; &lbrack;Hnoi2016&rsqb;序列 莫队

    题目: 给定长度为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 ...

  8. BZOJ 4540 &lbrack;Hnoi2016&rsqb;序列 &vert; 莫队 详细题解

    传送门 BZOJ 4540 题解 --怎么说呢--本来想写线段树+矩阵乘法的-- --但是嘛--yali的机房太热了--困--写不出来-- 于是弃疗,写起了莫队.(但是我连莫队都想不出来!) 首先用单 ...

  9. BZOJ4540 Hnoi2016 序列 【莫队&plus;RMQ&plus;单调栈预处理】&ast;

    BZOJ4540 Hnoi2016 序列 Description 给定长度为n的序列:a1,a2,-,an,记为a[1:n].类似地,a[l:r](1≤l≤r≤N)是指序列:al,al+1,-,ar- ...

随机推荐

  1. OpenCV2邻域和模板操作

    在图像处理中,通过当前位置的邻域像素计算新的像素值是很常见的操作.当邻域包含图像的上几行和下几行时,就需要同时扫描图像的若干行,这就是图像的邻域操作了.至于模板操作是实现空间滤波的基础,通常是使用一个 ...

  2. HttpClient&lowbar;4 用法 由HttpClient&lowbar;3 升级到 HttpClient&lowbar;4 必看

    转自:http://www.blogjava.net/stevenjohn/archive/2012/09/26/388609.html HttpClient程序包是一个实现了 HTTP 协议的客户端 ...

  3. Windows Server 2016软件定义存储:Storage Spaces Direct的关键特性

    [TechTarget中国原创] 微软在Windows Server 2016 Technical Preview 2中引入了Storage Spaces Direct.这个特性将本地存储扩展为高可用 ...

  4. python 代码片段4

    #coding=utf-8 # 任何等于0的数值被认为是False,所有非零的数字被认为True, # 空的容器为False,飞控容器酒味True. download_complete=False p ...

  5. get 与 post

    <form action="Default.aspx" method="get"> get  服务器端 用request.querystring来获 ...

  6. javascript中的substr和substring

    1.substr 方法 返回一个从指定位置开始的指定长度的子字符串. stringvar.substr(start [, length ]) 参数: stringvar 必选项.  要提取子字符串的字 ...

  7. 无法连接ssh,fatal&colon; daemon&lpar;&rpar; failed&colon; No such device

    今天发现一个服务器的sshd无法启动,查看/var/log/secure里发现:fatal: daemon() failed: No such device 解决办法: rm /dev/null /d ...

  8. JS开发之CommonJs和AMD&sol;CMD规范

    CommonJS是主要为了JS在后端的表现制定的,他是不适合前端的,AMD(异步模块定义)出现了,它就主要为前端JS的表现制定规范. 在兼容CommonJS的系统中,你可以使用JavaScript开发 ...

  9. 如何识别网页类型&lpar;wap页面还是wise页面&rpar;

    思路很简单,就是通过网页结构的一些特征来区分,当然也可以通过url的格式来区分,不过这个错误率较高,因为有很多小网站的url设计不规范. 网页特征包括两大类: 1.meta信息: 一般wap页面都会为 ...

  10. 【转 :Hibernate 缓存机制】

    转自:http://www.cnblogs.com/wean/archive/2012/05/16/2502724.html Hibernate 缓存机制 一.why(为什么要用Hibernate缓存 ...