- 1
- /*
- 2 http://acm.hdu.edu.cn/showproblem.php?pid=4893
- 3 题意:三个操作 某点增加n, 某段 全部变成 最近最小的斐波那契,查询某段和
- 4 思路:就是个线段树,爆炸
- 5 线段树时从下往上更新,我是zz
- 6 2017年02月27日20:49:32
- 7 */
- 8#include 9#include 10#define N 100010 11 long long xds[N << 2];
- 12 bool xdsisfb[N << 2];
- 13 long long fb[92] = {
- 14 1,
- 15 1,
- 16 2,
- 17 3,
- 18 5,
- 19 8,
- 20 13,
- 21 21,
- 22 34,
- 23 55,
- 24 89,
- 25 144,
- 26 233,
- 27 377,
- 28 610,
- 29 987,
- 30 1597,
- 31 2584,
- 32 4181,
- 33 6765,
- 34 10946,
- 35 17711,
- 36 28657,
- 37 46368,
- 38 75025,
- 39 121393,
- 40 196418,
- 41 317811,
- 42 514229,
- 43 832040,
- 44 1346269,
- 45 2178309,
- 46 3524578,
- 47 5702887,
- 48 9227465,
- 49 14930352,
- 50 24157817,
- 51 39088169,
- 52 63245986,
- 53 102334155,
- 54 165580141,
- 55 267914296,
- 56 433494437,
- 57 701408733,
- 58 1134903170,
- 59 1836311903,
- 60 2971215073,
- 61 4807526976,
- 62 7778742049,
- 63 12586269025,
- 64 20365011074,
- 65 32951280099,
- 66 53316291173,
- 67 86267571272,
- 68 139583862445,
- 69 225851433717,
- 70 365435296162,
- 71 591286729879,
- 72 956722026041,
- 73 1548008755920,
- 74 2504730781961,
- 75 4052739537881,
- 76 6557470319842,
- 77 10610209857723,
- 78 17167680177565,
- 79 27777890035288,
- 80 44945570212853,
- 81 72723460248141,
- 82 117669030460994,
- 83 190392490709135,
- 84 308061521170129,
- 85 498454011879264,
- 86 806515533049393,
- 87 1304969544928657,
- 88 2111485077978050,
- 89 3416454622906707,
- 90 5527939700884757,
- 91 8944394323791464,
- 92 14472334024676221,
- 93 23416728348467685,
- 94 37889062373143906,
- 95 61305790721611591,
- 96 99194853094755497,
- 97 160500643816367088,
- 98 259695496911122585,
- 99 420196140727489673,
- 100 679891637638612258,
- 101 1100087778366101931,
- 102 1779979416004714189,
- 103 2880067194370816120,
- 104 4660046610375530309,
- 105 7540113804746346429
- };
- 106 long long findfb(long long val) {
- 107 int l = 0,
- r = 91,
- m;
- 108
- while (l != r) {
- 109 m = (l + r) / 2;
- 110
- if (fb[m] < val) {
- 111 l = m + 1;
- 112
- } else {
- 113 r = m;
- 114
- }
- 115
- }
- 116
- if (l != 0 && val - fb[l - 1] <= fb[l] - val) {
- 117
- return fb[l - 1];
- 118
- } else {
- 119
- return fb[l];
- 120
- }
- 121
- }
- 122 void add(int l, int r, int now, int id, long long value) {
- 123
- if (l == r) {
- 124 xdsisfb[now] = false;
- 125 xds[now] += value;
- 126
- return;
- 127
- }
- 128 int m = (l + r) / 2;
- 129
- if (m < id) {
- 130 add(m + 1, r, now << 1 | 1, id, value);
- 131
- } else {
- 132 add(l, m, now << 1, id, value);
- 133
- }
- 134 xds[now] = xds[now << 1] + xds[now << 1 | 1];
- 135 xdsisfb[now] = xdsisfb[now << 1] && xdsisfb[now << 1 | 1];
- 136
- }
- 137 long long query(int l, int r, int now, int zz, int yy) {
- 138
- if (zz <= l && yy >= r) return xds[now];
- 139 int m = (l + r) / 2;
- 140
- if (m < zz) {
- 141
- return query(m + 1, r, now << 1 | 1, zz, yy);
- 142
- } else if (m >= yy) {
- 143
- return query(l, m, now << 1, zz, yy);
- 144
- } else {
- 145
- return query(m + 1, r, now << 1 | 1, zz, yy) + query(l, m, now << 1, zz, yy);
- 146
- }
- 147
- }
- 148 void gxfb(int l, int r, int now, int zz, int yy) {
- 149
- if (xdsisfb[now]) return;
- 150
- if (l == r) {
- 151 xdsisfb[now] = true;
- 152 xds[now] = findfb(xds[now]);
- 153
- return;
- 154
- }
- 155 int m = (l + r) / 2;
- 156
- if (m < zz) {
- 157 gxfb(m + 1, r, now << 1 | 1, zz, yy);
- 158
- } else if (m >= yy) {
- 159 gxfb(l, m, now << 1, zz, yy);
- 160
- } else {
- 161 gxfb(m + 1, r, now << 1 | 1, zz, yy);
- 162 gxfb(l, m, now << 1, zz, yy);
- 163
- }
- 164 xds[now] = xds[now << 1] + xds[now << 1 | 1];
- 165 xdsisfb[now] = xdsisfb[now << 1] && xdsisfb[now << 1 | 1];
- 166
- }
- 167 int main() {
- 168 //freopen("test.in","r",stdin);
- 169 //freopen("outb","w",stdout);
- 170 int n,
- m;
- 171
- while (scanf("%d %d", &n, &m) != EOF) {
- 172 memset(xdsisfb, false, sizeof(xdsisfb));
- 173 memset(xds, 0, sizeof(xds));
- 174 long long a,
- b,
- c;
- 175
- while (m--) {
- 176 scanf("%lld %lld %lld", &a, &b, &c);
- 177
- if (a == 1) {
- 178 add(1, n, 1, b, c);
- 179
- } else if (a == 2) {
- 180 printf("%lld\n", query(1, n, 1, b, c));
- 181
- } else if (a == 3) {
- 182 gxfb(1, n, 1, b, c);
- 183
- }
- 184
- }
- 185
- }
- 186
- return 0;
- 187
- }
来源: http://www.bubuko.com/infodetail-1964962.html