题目名称 2964. 数列操作η
输入输出 eta.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2018-07-25
开放分组 全部用户
提交状态
分类标签
线段树
通过:6, 提交:13, 通过率:46.15%
Gravatarsdzwyq 100 1.127 s C++
Gravatarldxoi 100 1.189 s C++
Gravatarldxoi 100 1.192 s C++
Gravatarzhoushuyu 100 1.193 s C++
Gravatarldxoi 100 1.193 s C++
GravatarAntiLeaf 100 1.271 s C++
Gravatar小一米 100 2.268 s C++
Gravatarwfff 100 2.975 s C++
Gravatarldxoi 0 0.581 s C++
Gravatarldxoi 0 0.621 s C++
关于 数列操作η 的讨论
求过审
Gravatar小一米
2018-07-26 17:36 1楼
复杂度两只log
Gravatarzhoushuyu
2018-07-26 22:45 2楼
回复 @zhoushuyu :
%%%
Gravatarsdzwyq
2018-07-26 22:08 3楼
时间复杂度怎么证啊?
Gravatardoremi
2018-07-26 23:24 4楼

2964. 数列操作η

★★★   输入文件:eta.in   输出文件:eta.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

给定长度均为 $n$ 的数列 $a,b$,其中 $b$ 数列为 $[1,n]$ 的全排列,$a$ 数列全为 $0$。

你需要支持 $q$ 次操作,操作分为 $add$ 和 $query$ 两种。

$add\ l\ r$ 表示 $a_{l},a_{l+1},...,a_{r-1},a_r$均加 $1$。

$query\ l\ r$ 表示求 $\displaystyle\sum^r_{i=l}\lfloor\frac{a_i}{b_i}\rfloor$。

其中 $\lfloor x\rfloor$ 表示对 $x$ 下取整。

【输入格式】

第一行有两个整数 $n,q$,$n$ 表示 $a,b$ 数列长度,$q$ 表示操作次数

接下来一行 $n$ 个整数,表示 $b$ 数列

接下来 $q$ 行,每行表示 $add$ 或 $query$ 操作

【输出格式】

对于每一个 $query$ 操作,输出一行整数表示对应的答案

【样例输入】

5 12
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5

【样例输出】

1
1
2
4
4
6

【提示】

对于100%的数据,$n,q\leq 100000,1\leq l,r\leq n$。

保证 $b$ 数列是 $[1,n]$ 的全排列

【来源】

2018多校训练-Naive Operations