首页 > 代码库 > HDOJ 4893 Wow! Such Sequence! 线段树

HDOJ 4893 Wow! Such Sequence! 线段树

2024-07-14 18:21:36   227人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4893

题意：10万的区间，初始都为0，10万次操作，三种操作为单点修改，区间将每个数改成最近的斐波那契数，以及区间求和。

分析：用一个flag记录该段是否被改成斐波那契数，同时多维护一个sum1表示如果该段改成斐波那契数，区间和为多少。开始sum1为区间长度，之后在单点做了修改以后对其更新，需要的时候用其覆盖sum。

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 using namespace std;  5   6 struct T{  7     long long sum, sum1;  8     bool flag;  9 }t[100100 << 2]; 10 int n, m; 11 int c, x, y; 12 long long f[100]; 13 void pushup(int x) 14 { 15     int ls = x << 1, rs = x << 1 | 1; 16     t[x].sum = t[ls].sum + t[rs].sum; 17     t[x].sum1 = t[ls].sum1 + t[rs].sum1; 18 } 19 void pushdown(int x) 20 { 21     if (t[x].flag){ 22         t[x<<1].sum = t[x<<1].sum1; 23         t[x<<1].flag = true; 24         t[x<<1|1].sum = t[x<<1|1].sum1; 25         t[x<<1|1].flag = true; 26         t[x].flag = false; 27     } 28 } 29 void build(int x, int l, int r) 30 { 31     t[x].flag = false; 32     if (l == r){ 33         t[x].flag = t[x].sum = 0; 34         t[x].sum1 = 1; 35         return; 36     } 37     int mid = l + r >> 1; 38     build(x<<1, l, mid); 39     build(x<<1|1, mid+1, r); 40     pushup(x); 41 } 42 void add(int x, int l, int r, int p, long long val) 43 { 44     if (l == r){ 45         t[x].sum += val; 46         if (t[x].sum >= f[91]) 47             t[x].sum1 = f[91]; 48         else if (t[x].sum <= 1) 49             t[x].sum1 = 1; 50         else{ 51             long long * p = upper_bound(f, f+92, t[x].sum); 52             if (t[x].sum - *(p-1) <= *p - t[x].sum) 53                 t[x].sum1 = *(p-1); 54             else 55                 t[x].sum1 = *p; 56         } 57         return; 58     } 59     int mid = l + r >> 1; 60     pushdown(x); 61     if (p <= mid) 62         add(x<<1, l, mid, p, val); 63     if (p > mid) 64         add(x<<1|1, mid+1, r, p, val); 65     pushup(x); 66 } 67 void tra(int x, int l, int r, int s, int e) 68 { 69     if (l == r){ 70         t[x].sum = t[x].sum1; 71         return; 72     } 73     if (s <= l && r <= e){ 74         t[x].flag = true; 75         t[x].sum = t[x].sum1; 76         return; 77     } 78     int mid = l + r >> 1; 79     pushdown(x); 80     if (s <= mid) 81         tra(x<<1, l, mid, s, e); 82     if (mid < e) 83         tra(x<<1|1, mid+1, r, s, e); 84     pushup(x); 85 } 86 long long query(int x, int l, int r, int s, int e) 87 { 88     if (l == r) 89         return t[x].sum; 90     if (s <= l && r <= e) 91         return t[x].sum; 92     long long tmp = 0; 93     int mid = l + r >> 1; 94     pushdown(x); 95     if (s <= mid) 96         tmp += query(x<<1, l, mid, s, e); 97     if (mid < e) 98         tmp += query(x<<1|1, mid+1, r, s, e); 99     pushup(x);100     return tmp;101 }102 int main()103 {104     f[0] = 1; f[1] = 1;105     for (int i = 2; i <= 91; i++)106         f[i] = f[i-1] + f[i-2];107     while(scanf("%d %d", &n, &m) != EOF)108     {109         build(1, 1, n);110         while(m--){111             scanf("%d %d %d", &c, &x, &y);112             if (c == 1) add(1, 1, n, x, (long long)y);113             if (c == 2) printf("%I64d\n", query(1, 1, n, x, y));114             if (c == 3) tra(1, 1, n, x, y);115         }116     }117     return 0;118 }

 


联系
我们