BZOj 4540: [Hnoi2016]序列 [莫队 st表 预处理]

时间:2022-09-24 13:58:17

4540: [Hnoi2016]序列

题意:询问区间所有子串的最小值的和


不强制在线当然上莫队啦

但是没想出来,因为不知道该维护当前区间的什么信息,维护前后缀最小值的话不好做

想到单调栈求一下,但是对于\([l,r]\)还是可能有很多最小值,数据不随机的话会被卡

预处理!!!

预处理\(l_i,\ r_i\)以i为最小值的范围,\(fl[i],\ fr[i]\)为从i开始 / 以i结尾的的前缀 / 后缀 最小值的和

\(fr[i] = (i - l_i + 1) * a_i + fr[i] - fr[l_i - 1]\)

这是可减的!!!

\([l, r] \rightarrow [l, r+1]\),求出\(p=rmq(l, r+1)\),对于\(p-l+1\)这些后缀最小值就是\(a_p\),剩下的直接用预处理的信息就行了 \(fr[r] - fr[p]\)

遇到不好处理的情况一定要想一下预处理 / DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
inline ll read() {
char c=getchar(); ll x=0,f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
} int n, a[N], Q, l, r, block, pos[N]; ll ans[N];
struct meow{
int l, r, id;
bool operator <(const meow &a) const {return pos[l] == pos[a.l] ? r < a.r : pos[l] < pos[a.l];}
} q[N]; namespace cat {
int l[N], r[N], st[N], top; ll fl[N], fr[N];
int f[N][18], log[N];
inline int min(int x, int y) {return a[x]<a[y] ? x : y;} void init() {
for(int i=1; i<=n; i++) {
while(top && a[ st[top] ] > a[i]) r[ st[top] ] = i-1, top--;
l[i] = st[top]+1;
st[++top] = i;
}
while(top) r[ st[top--] ] = n;
//for(int i=1; i<=n; i++) printf("%d [%d, %d]\n", i, l[i], r[i]);
for(int i=1; i<=n; i++) fr[i] = (ll) (i - l[i] + 1) * a[i] + fr[l[i] - 1];
for(int i=n; i>=1; i--) fl[i] = (ll) (r[i] - i + 1) * a[i] + fl[r[i] + 1];// printf("fl %d %lld\n",i,fl[i]); ; for(int i=1; i<=n; i++) f[i][0] = i;
for(int j=1; j<=16; j++)
for(int i=1; i+(1<<j)-1 <= n; i++)
f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);// printf("f %d %d %d\n", i, j, f[i][j]);
log[1]=0; for(int i=2; i<=n; i++) log[i] = log[i>>1]+1;
}
inline int rmq(int l, int r) {
int t = log[r-l+1];
return min(f[l][t], f[r-(1<<t)+1][t]);
} ll now;
inline void addr(int l, int r, ll flag) {
int p = rmq(l, r);
now += flag * ( (ll) (p-l+1) * a[p] + fr[r] - fr[p] );
}
inline void addl(int l, int r, ll flag) {
int p = rmq(l, r);
now += flag * ( (ll) (r-p+1) * a[p] + fl[l] - fl[p] );
} void modui() {
sort(q+1, q+1+Q);
int l=1, r=0;
for(int i=1; i<=Q; i++) {
while(r < q[i].r) cat::addr(l, ++r, 1);
while(r > q[i].r) cat::addr(l, r--, -1);
while(l < q[i].l) cat::addl(l++, r, -1);
while(l > q[i].l) cat::addl(--l, r, 1);
ans[ q[i].id ] = now;
}
}
} int main() {
freopen("in", "r", stdin);
n=read(); Q=read(); block = sqrt(n);
for(int i=1; i<=n; i++) a[i]=read(), pos[i] = (i-1)/block+1;
for(int i=1; i<=Q; i++) l=read(), r=read(), q[i] = (meow){l, r, i};
cat::init();
cat::modui();
for(int i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

BZOj 4540: [Hnoi2016]序列 [莫队 st表 预处理]的更多相关文章

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

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

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

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

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

  4. &lbrack;Bzoj4540&rsqb;&lbrack;Hnoi2016&rsqb; 序列(莫队 &plus; ST表 &plus; 单调队列)

    4540: [Hnoi2016]序列 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 1567  Solved: 718[Submit][Status] ...

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

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

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

  7. BZOJ 4540 &lbrack;Hnoi2016&rsqb;序列 (单调栈 &plus; ST表 &plus; 莫队算法)

    题目链接  BZOJ4540 考虑莫队算法. 这题难在$[l, r]$到$[l, r+1]$的转移. 根据莫队算法的原理,这个时候答案应该加上 $cal(l, r+1) + cal(l+1, r+1) ...

  8. BZOJ4540 &lbrack;Hnoi2016&rsqb;序列 【莫队 &plus; ST表 &plus; 单调栈】

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

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

随机推荐

  1. 桥牌笔记:Skill 4 Series A–Deal 5

    南主打5C. 此牌的难点在于:如果黑桃4-2分布时,有没有打成的希望?看来黑桃.红桃.方块各1个失张无法避免? 但希望还是有的,那就是东家拿2张黑桃,并且有3张将牌. 这时庄家可以清2轮将牌,拔2轮黑 ...

  2. 16&period;如何设置Quartus II Programmer,保护pof不被读出

    Program时,把security bit勾上,点击start 这样examine时就不能正确的读出pof 读出来的pof 除文件头外,其余的内容全为0 怎么样,大家试试!

  3. c&num; 修改appConfig文件节点

    配置文件对于程序的帮助是不可小视的,尤其是java工程师们,当然了,我这里说的是c#的配置文件.废话不多说了,直接上代码了,想必大家一看就会明白了 private string UpdateConfi ...

  4. 为什么用linear regression可以做classification

    输出空间 错误衡量方式 能不能直接用linear regression for classification 当成一个分类器回传回去 heuristic(启发式的:试探) 错误衡量 complexit ...

  5. LDAP错误代码221

    ---------------------------命令方式启动失败报错-------------------------------[root@rusky bin]# ./dsadm start ...

  6. 项目总结之SSI &lpar;一&rpar;

    这是我进公司之后做的第一个新项目,从无到有. 去年夏天和同事在会议室里度过的日子还恍如昨日啊,时光啊,你慢些走... 作为一个外部项目,美工设计了一个Win8风格的界面,看到现在做前台的同学做的一样是 ...

  7. iOS &quot&semi;此证书由未知颁发机构签名&quot&semi;此问题的解决方法

    前段时间制作证书时把以前钥匙串中的证书全删除了,然后在制作新证书的时候就出现了"此证书由未知颁发机构签名"的红色警告,通过查找资料发现出现此问题的原因是:我把钥匙串中的此证书给删除 ...

  8. 解锁scott账户方法

    装完了数据库,忘了给scott账户解锁.这时可以在sql plus工具里,也可以在控制台通过命令行给scott账户解锁. 在第一种情况下,以system账户+自己安装时设置的密码,登录SQL Plus ...

  9. Python redis交互

    1.首先安装模块 pip3 install redis 2.代码模板如下: from redis import StrictRedis if __name__ == '__main__': # 设置连 ...

  10. 爬虫之selenium使用

    详细使用链接: 点击链接 selenium介绍: selenium最初是一个自动化测试工具,而爬虫中使用它主要是为了解决requests无法直接执行JavaScript代码的问题 selenium本质 ...