首页 > 代码库 > HDU 4893 线段树
HDU 4893 线段树
Wow! Such Sequence!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 781 Accepted Submission(s): 225
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
题目意思:
一个长度为n的数组,初始化为0,接下来m次操作,操作有3种:
1 a b 即把数组中第a个位置元素+b
2 a b 即求数组中[a,b]元素总和
3 a b 把数组[a,b]中元素变成和该元素最相近的斐波那契数(若两个斐波那契数和该元素差的绝对值一样,取最小的斐波那契数)
思路:
若每次进行3操作,都在线段树里变换一下,那么就会超时。
咱们注意到:如果某一段已经进行过3操作,那么再次进行3操作时该段可以忽略。
若某一段已经进行过3操作,且某几个元素进行过1操作,那么再次进行3操作时只需对这几个进行过1操作得元素变换斐波那契数即可。
所以根据这个进行优化写线段树就行了。
代码:
1 //主要优化部分 :若某一段进行过3操作且没进行过1操作,那么再次对该段进行3操作时可以忽略此段 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define N 100005 7 #define ll root*2 8 #define rr root*2+1 9 #define mid (a[root].l+a[root].r)/2 10 11 __int64 fi[100]; 12 13 struct node{ 14 int l, r; 15 __int64 sum; 16 int flag3; 17 }a[N*4]; 18 19 void build(int l,int r,int root){ 20 a[root].l=l;a[root].r=r; 21 a[root].sum=0;a[root].flag3=0; 22 if(l==r) return; 23 build(l,mid,ll); 24 build(mid+1,r,rr); 25 } 26 27 __int64 find(__int64 key,int n){ //二分查找和key最相近的斐波那契数 28 int l=1, r=n; 29 while(l<=r){ 30 int mm=(l+r)/2; 31 if(fi[mm]<=key&&mm==n) return fi[mm]; 32 else if(fi[mm]>=key&&mm==1) return fi[mm]; 33 else if(fi[mm]<=key&&fi[mm+1]>=key) { 34 if(abs(fi[mm]-key)<=abs(fi[mm+1]-key)) 35 return fi[mm]; 36 else return fi[mm+1]; 37 } 38 else if(fi[mm]>=key&&fi[mm-1]<=key) { 39 if(abs(fi[mm-1]-key)<=abs(fi[mm]-key)) 40 return fi[mm-1]; 41 else return fi[mm]; 42 } 43 else if(fi[mm]<key){ 44 l=mm+1; 45 } 46 else if(fi[mm]>key){ 47 r=mm-1; 48 } 49 } 50 } 51 52 void init(){ 53 fi[0]=1;fi[1]=1;fi[2]=2; 54 for(int i=3;i<=90;i++){ 55 fi[i]=fi[i-1]+fi[i-2]; 56 } 57 } 58 59 void down(int root){ 60 if(a[root].flag3==1)return; //若进行过3操作则跳过 61 a[root].flag3=1; //把进行3操作标志改成1,说明该段进行过3操作 62 if(a[root].l==a[root].r){ 63 a[root].sum=find(a[root].sum,90); 64 return ; 65 } 66 down(ll); 67 down(rr); 68 a[root].sum=a[ll].sum+a[rr].sum; //往上更新 69 } 70 71 void add(int p,__int64 val,int root){ 72 a[root].flag3=0; //进行过1操作,那么此段就不完全进行过3操作,所以把标志改成0 73 if(a[root].l==p&&a[root].r==p){ 74 a[root].sum+=val; 75 return; 76 } 77 if(p<=mid) add(p,val,ll); 78 else add(p,val,rr); 79 a[root].sum=a[ll].sum+a[rr].sum; //往上更新 80 a[root].flag3=min(a[ll].flag3,a[rr].flag3); 81 } 82 83 void update(int l,int r,int root){ 84 85 if(a[root].flag3) return; //若此段进行过3操作 则跳过 86 if(a[root].l>=l&&a[root].r<=r){ 87 down(root); //向下更新 88 return; 89 } 90 if(l<=mid) update(l,r,ll); 91 if(r>mid) update(l,r,rr); 92 a[root].sum=a[ll].sum+a[rr].sum; //往上更新 93 a[root].flag3=min(a[ll].flag3,a[rr].flag3); 94 } 95 96 __int64 query(int l,int r,int root){ 97 if(a[root].l==l&&a[root].r==r)return a[root].sum; 98 if(r<=mid) return query(l,r,ll); 99 else if(l>mid) return query(l,r,rr);100 else return query(l,mid,ll)+query(mid+1,r,rr);101 }102 103 main(){104 int x, z, n, m;105 int y;106 __int64 yy;107 init();108 while(scanf("%d %d",&n,&m)==2){109 110 build(1,n,1);111 while(m--){112 scanf("%d%d",&z,&x);113 if(z==1){114 scanf("%I64d",&yy);115 add(x,yy,1);116 }117 else if(z==2){118 scanf("%d",&y);119 printf("%I64d\n",120 query(x,y,1));121 }122 else {123 scanf("%d",&y);124 update(x,y,1);125 }126 }127 }128 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。