首页 > 代码库 > HDU4893--Wow! Such Sequence! （线段树 延迟标记）
HDU4893--Wow! Such Sequence! （线段树 延迟标记）
Wow! Such Sequence!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3354 Accepted Submission(s): 966
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
Source
2014 Multi-University Training Contest 3
题意：
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. 就这三句话
1 #include <cmath> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 typedef long long ll; 8 const int maxn = 1e5 + 100; 9 ll fab[100]; 10 int lazy[maxn<<2]; //lazy[pos]为1 表示该区间的数为Fibonacci number。 11 ll sum1[maxn<<2],sum2[maxn<<2]; // sum1为原数组的和，sum2为变为Fibonacci number之后的和，维护这两个数组 12 void pre_solve() //预处理数前90个斐波那契数 13 { 14 fab[0] = fab[1] = 1; 15 for (int i = 2; i <= 90; i++) 16 fab[i] = fab[i-1] + fab[i-2]; 17 } 18 ll find_fab(ll x) //找到距离x最近的斐波那契数 19 { 20 ll ans = fab[0],delta= abs(fab[0] - x); 21 for (int i = 0; i <= 90; i++) 22 { 23 if (delta > abs(x - fab[i])) 24 { 25 delta = abs (x - fab[i]); 26 ans = fab[i]; 27 } 28 } 29 return ans; 30 } 31 void push_down(int pos) 32 { 33 if (lazy[pos]) 34 { 35 lazy[pos<<1] = lazy[pos<<1|1] = lazy[pos]; 36 lazy[pos] = 0; 37 sum1[pos<<1] = sum2[pos<<1]; 38 sum1[pos<<1|1] = sum2[pos<<1|1]; 39 } 40 } 41 void push_up(int pos) 42 { 43 sum1[pos] = sum1[pos<<1] + sum1[pos<<1|1]; 44 sum2[pos] = sum2[pos<<1] + sum2[pos<<1|1]; 45 } 46 void build(int l,int r,int pos) 47 { 48 sum1[pos] = lazy[pos] = 0; 49 if (l == r) 50 { 51 sum2[pos] = 1; //初始状态 所有数都为0，距离0最近的斐波那契数是1 52 return; 53 } 54 int mid = (l + r) >> 1; 55 build(l,mid,pos<<1); 56 build(mid+1,r,pos<<1|1); 57 push_up(pos); 58 } 59 void update_add(int l,int r,int pos,int x,int val) 60 { 61 if (l == r) 62 { 63 if (lazy[pos]) 64 sum1[pos] = sum2[pos] + val; //如果该位置的数字为斐波那契数，那么在此基础上加val 65 else 66 sum1[pos] += val; //不是斐波那契数 直接加val 67 sum2[pos] = find_fab(sum1[pos]); //sum1[pos] 改变，相应的sum2也要改变 68 lazy[pos] = 0; 69 return; 70 } 71 push_down(pos); 72 int mid = (l + r) >> 1; 73 if (x <= mid) 74 update_add(l,mid,pos<<1,x,val); 75 else 76 update_add(mid+1,r,pos<<1|1,x,val); 77 push_up(pos); 78 } 79 void update_fab(int l,int r,int pos,int ua,int ub) 80 { 81 if (ua <= l && ub >= r) 82 { 83 sum1[pos] = sum2[pos]; 84 lazy[pos] = 1; 85 return; 86 } 87 push_down(pos); 88 int mid = (l + r) >> 1; 89 if (ua <= mid) 90 update_fab(l,mid,pos<<1,ua,ub); 91 if (ub > mid) 92 update_fab(mid+1,r,pos<<1|1,ua,ub); 93 push_up(pos); 94 } 95 ll query(int l,int r,int pos,int ua,int ub) 96 { 97 if (ua <= l && ub >= r ) 98 return sum1[pos]; 99 push_down(pos);100 int mid = (l + r) >> 1;101 ll ans = 0;102 if (ua <= mid)103 ans += query(l,mid,pos<<1,ua,ub);104 if (ub > mid)105 ans += query(mid+1,r,pos<<1|1,ua,ub);106 return ans;107 }108 int main(void)109 {110 #ifndef ONLINE_JUDGE111 freopen("in.txt","r",stdin);112 freopen("out.txt","w",stdout);113 #endif114 pre_solve();115 int n,m;116 while (~scanf ("%d%d",&n,&m))117 {118 build(1,n,1);119 for (int i = 0; i < m; i++)120 {121 int op,x,y;122 scanf ("%d%d%d",&op,&x,&y);123 if (op == 1)124 update_add(1,n,1,x,y);125 if (op == 3)126 update_fab(1,n,1,x,y);127 if (op == 2)128 printf("%I64d\n",query(1,n,1,x,y));129 }130 }131 return 0;132 }
HDU4893--Wow! Such Sequence! （线段树 延迟标记）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。