首页 > 代码库 > HDOJ 4893 Wow! Such Sequence!
HDOJ 4893 Wow! Such Sequence!
题意是这样的，给定一个n个元素的数组，初始值为0，3种操作：
1 k d将第k个数增加d；
2 l r 询问区间l...r范围内数之和；
3 l r 表示将区间l...r内的数变成离他最近的斐波那契数，要求尽量小。
线段树操作题目，其中对于第三种操作用一个懒惰标记一下，表示l...r内的数是不是已经变成斐波那契数，如果是的话，求和就是其相应数的斐波那契数之和。
代码：
1 //Template updates date: 20140718 2 #include <bits/stdc++.h> 3 #define esp 1e-6 4 #define inf 0x3f3f3f3f 5 #define pi acos(-1.0) 6 #define pb push_back 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define lowbit(x) (x&(-x)) 10 #define mp(a, b) make_pair((a), (b)) 11 #define bit(k) (1<<(k)) 12 #define iin freopen("pow.in", "r", stdin); 13 #define oout freopen("pow.out", "w", stdout); 14 #define in freopen("solve_in.txt", "r", stdin); 15 #define out freopen("solve_out.txt", "w", stdout); 16 #define bug puts("********))))))"); 17 #define Inout iin oout 18 #define inout in out 19 20 #define SET(a, v) memset(a, (v), sizeof(a)) 21 #define SORT(a) sort((a).begin(), (a).end()) 22 #define REV(a) reverse((a).begin(), (a).end()) 23 #define READ(a, n) {REP(i, n) cin>>(a)[i];} 24 #define REP(i, n) for(int i = 0; i < (n); i++) 25 #define VREP(i, n, base) for(int i = (n); i >= (base); i--) 26 #define Rep(i, base, n) for(int i = (base); i < (n); i++) 27 #define REPS(s, i) for(int i = 0; (s)[i]; i++) 28 #define pf(x) ((x)*(x)) 29 #define mod(n) ((n)) 30 #define Log(a, b) (log((double)b)/log((double)a)) 31 #define Srand() srand((int)time(0)) 32 #define random(number) (rand()%number) 33 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) 34 35 using namespace std; 36 typedef long long LL; 37 typedef unsigned long long ULL; 38 typedef vector<int> VI; 39 typedef pair<int,int> PII; 40 typedef vector<PII> VII; 41 typedef vector<PII, int> VIII; 42 typedef VI:: iterator IT; 43 typedef map<string, int> Mps; 44 typedef map<int, int> Mpi; 45 typedef map<int, PII> Mpii; 46 typedef map<PII, int> Mpiii; 47 const int maxm = 140000 + 1000; 48 49 LL f[92]; 50 int n, m; 51 LL sum[maxm<<2], sum1[maxm<<2], cover[maxm<<2]; 52 53 void pre() { 54 f[0] = f[1] = 1; 55 Rep(i, 2, 92) { 56 f[i] = f[i-1] + f[i-2]; 57 } 58 } 59 void PushDown(int rt) { 60 if(cover[rt]) { 61 cover[rt] = 0; 62 cover[rt<<1] = cover[rt<<1|1] = 1; 63 sum[rt<<1] = sum1[rt<<1]; 64 sum[rt<<1|1] = sum1[rt<<1|1]; 65 } 66 } 67 void PushUp(int rt) { 68 sum[rt] = sum[rt<<1]+sum[rt<<1|1]; 69 sum1[rt] = sum1[rt<<1]+sum1[rt<<1|1]; 70 } 71 void build(int l, int r, int rt) { 72 if(l == r) { 73 sum[rt] = 0; 74 sum1[rt] = 1; 75 cover[rt] = 0; 76 return ; 77 } 78 int m = (l+r)>>1; 79 build(lson); 80 build(rson); 81 PushUp(rt); 82 cover[rt] = 0; 83 } 84 85 void update(int l, int r, int rt, int k, int d) { 86 if(l == k && r == k) { 87 sum[rt] += d; 88 int b = upper_bound(f+1, f+92, sum[rt]) - f; 89 if(abs(f[b]-sum[rt]) >= abs(f[b-1]-sum[rt])) 90 sum1[rt] = f[b-1]; 91 else 92 sum1[rt] = f[b]; 93 return; 94 } 95 PushDown(rt); 96 int m = (l+r)>>1; 97 if(k <= m) 98 update(lson, k, d); 99 else update(rson, k, d);100 PushUp(rt);101 }102 void update1(int L, int R, int l, int r, int rt) {103 if(L <=l && R >= r) {104 cover[rt] = 1;105 sum[rt] = sum1[rt];106 return;107 }108 PushDown(rt);109 int m = (l+r)>>1;110 if(L <= m)111 update1(L, R, lson);112 if(R > m)113 update1(L, R, rson);114 PushUp(rt);115 }116 LL query(int L, int R, int l, int r, int rt) {117 if(L <= l && R >= r) {118 return sum[rt];119 }120 int m = (l+r)>>1;121 PushDown(rt);122 LL ans = 0;123 if(L <= m)124 ans += query(L, R, lson);125 if( R > m)126 ans += query(L, R, rson);127 return ans;128 }129 int main() {130 131 pre();132 while(scanf("%d%d", &n, &m) == 2) {133 build(1, n, 1);134 REP(i, m) {135 int u, l, r;136 scanf("%d%d%d", &u, &l, &r);137 if(u == 2) {138 printf("%I64d\n", query(l, r, 1, n, 1));139 } else if(u == 1) {140 update(1, n, 1, l, r);141 } else {142 update1(l, r, 1, n, 1);143 }144 }145 }146 return 0;147 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。