Wow! Such Sequence!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 823 Accepted Submission(s): 239
Problem Description
Recently, Doge got a funny birthday present from his new friend, Protein Tiger from St. Beeze College. No, not cactuses. It's a mysterious blackbox.
After some research, Doge found that the box is maintaining a sequence an of n numbers internally, initially all numbers are zero, and there are THREE "operations":
1.Add d to the k-th number of the sequence.
2.Query the sum of ai where l ≤ i ≤ r.
3.Change ai to the nearest Fibonacci number, where l ≤ i ≤ r.
4.Play sound "Chee-rio!", a bit useless.
Let F0 = 1,F1 = 1,Fibonacci number Fn is defined as Fn = Fn - 1 + Fn - 2 for n ≥ 2.
Nearest Fibonacci number of number x means the smallest Fn where |Fn - x| is also smallest.
Doge doesn't believe the machine could respond each request in less than 10ms. Help Doge figure out the reason.
After some research, Doge found that the box is maintaining a sequence an of n numbers internally, initially all numbers are zero, and there are THREE "operations":
1.Add d to the k-th number of the sequence.
2.Query the sum of ai where l ≤ i ≤ r.
3.Change ai to the nearest Fibonacci number, where l ≤ i ≤ r.
4.Play sound "Chee-rio!", a bit useless.
Let F0 = 1,F1 = 1,Fibonacci number Fn is defined as Fn = Fn - 1 + Fn - 2 for n ≥ 2.
Nearest Fibonacci number of number x means the smallest Fn where |Fn - x| is also smallest.
Doge doesn't believe the machine could respond each request in less than 10ms. Help Doge figure out the reason.
Input
Input contains several test cases, please process till EOF.
For each test case, there will be one line containing two integers n, m.
Next m lines, each line indicates a query:
1 k d - "add"
2 l r - "query sum"
3 l r - "change to nearest Fibonacci"
1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231, all queries will be valid.
For each test case, there will be one line containing two integers n, m.
Next m lines, each line indicates a query:
1 k d - "add"
2 l r - "query sum"
3 l r - "change to nearest Fibonacci"
1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231, all queries will be valid.
Output
For each Type 2 ("query sum") operation, output one line containing an integer represent the answer of this query.
Sample Input
1 1
2 1 1
5 4
1 1 7
1 3 17
3 2 4
2 1 5
Sample Output
0
22
Author
Fudan University
题意:
给出 n(1 ~ 100000),m (1 ~ 100000) ,代表存在一个初始化为 0 ,数量为 n 的数列,后给出 m 个操作。
1 a b,代表将数列中第 k 个数增加 b( -2 ^ 31 <= b <= 2 ^ 31);
2 a b,代表输出数列 a 到 b 的总和;
3 a b,代表将数列 l 到 r 区间的数更改成最近的斐波那契数。
输出所有 2 操作的结果。
思路:
线段树。想预处理斐波那契数,开到 70 足以把所有的数更改为斐波那契数。后线段树维护两个值,sum 为总和值,change 为更改后的总和值,同时运用延迟标记。每次 1 操作只是单纯的单点更新,2 操作查询操作。3 操作的话则延迟标记为 1,代表有需要改变值,同时将 change 的总和赋值给 sum 即可。寻找最近的斐波那契数二分查找即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int MAXN = 100000; ll fin[75], sum[MAXN * 3], change[MAXN * 3]; int cover[MAXN * 3]; ll find_min (ll num) { if (num <= 0) return fin[1]; ll it = lower_bound(fin + 1, fin + 70 + 1, num) - fin; if (fin[it] == num) return num; if (abs(fin[it] - num) < abs(fin[it - 1] - num)) return fin[it]; return fin[it - 1]; } void init() { fin[1] = 1; fin[2] = 1; for (ll i = 3; i <= 70; ++i) { fin[i] = fin[i - 1] + fin[i - 2]; } } void push_up (ll node) { sum[node] = sum[node << 1] + sum[node << 1 | 1]; change[node] = change[node << 1] + change[node << 1 | 1]; } void push_down (ll node) { if (cover[node] != -1) { cover[node << 1] = cover[node << 1 | 1] = cover[node]; sum[node << 1] = change[node << 1]; sum[node << 1 | 1] = change[node << 1 | 1]; cover[node] = -1; } } void build (ll node, ll l, ll r) { if (l == r) { sum[node] = 0; change[node] = 1; cover[node] = -1; } else { ll mid = (r + l) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); cover[node] = -1; push_up(node); } } void updata_add (ll node, ll l, ll r, ll k, ll d) { if (l == r) { if (l == k) { sum[node] += d; change[node] = find_min( sum[node] ); } return; } push_down(node); ll mid = (r + l) >> 1; if (k <= mid) updata_add(node << 1, l, mid, k, d); else updata_add(node << 1 | 1, mid + 1, r, k, d); push_up(node); } void updata_change (int node, int l, int r, int cl, int cr) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { cover[node] = 1; sum[node] = change[node]; return; } push_down(node); ll mid = (r + l) >> 1; if (cl <= mid) updata_change(node << 1, l, mid, cl, cr); if (cr >= mid + 1) updata_change(node << 1 | 1, mid + 1, r, cl, cr); push_up(node); } ll query (ll node, ll l, ll r, ll cl, ll cr) { if (cl > r || cr < l) return 0; if (cl <= l && cr >= r) return sum[node]; if (r == l) return 0; push_down(node); ll mid = (r + l) >> 1; return query(node << 1, l, mid, cl, cr) + query(node << 1 | 1, mid + 1, r, cl, cr); } int main() { ll n, m; init(); while (~scanf("%I64d%I64d", &n, &m)) { build(1, 1, n); while (m--) { ll op, a, b; scanf("%I64d%I64d%I64d", &op, &a, &b); if (op == 2) printf("%I64d\n", query(1, 1, n, a, b)); else if (op == 1) updata_add(1, 1, n, a, b); else updata_change(1, 1, n, a, b); } } return 0; }
相关推荐
在Oracle数据库中,sequence等同于序列号,每次取的时候sequence会自动增加,一般会作用于需要按序列号排序的地方。 1、Create Sequence (注释:你需要有CREATE SEQUENCE或CREATE ANY SEQUENCE权限) CREATE ...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
Sequence to Sequence Learning with Neural Networksv论文PDF版
机器学习之sequence to sequence learning。(Sequence Generation-----Hung-yi Lee 李宏毅.ppt)
SequenceDiagram-3.0.5.zip
Edward Grefenstette - Beyond Sequence to Sequence with Augmented RNNs
A method for assembly sequence planning is proposed in this paper. First, two methods for assembly sequence planning are compared, which are indirect method and direct method. Then, the limits of the ...
基于循环神经网络和注意力机制的Sequence-to-Sequence模型神经网络方法在信息抽取和自动摘要生成方面发挥了重要作用。然而,该方法不能充分利用文本的语言特征信息,且生成结果中存在未登录词问题,从而影响文本摘要...
在Oracle数据库移植过程中,sequence可能失效,本资源可使失效的sequence重新恢复作用
sequence-to-sequence-learning-with-neural-networks.
Sequence Diagrams of UML
memory networks, are extremely appealing for sequence-tosequence learning tasks. Despite their great success, they typically suffer from a fundamental shortcoming: they are prone to generate ...
oracle中sequence介绍及应用
sequence-diagram-js 所需jar包,其中sequence-diagram-js支持自定义颜色
sequence.txt
invalid multibyte character sequence 870告警1
字体,圈码类。适用于加圈脚注各用书稿论文文档排版。
搜狐2017笔试题一:Kolakoski sequence完整源代码