题目链接:hdu 4983 Wow! Such Sequence!
题目大意:就是三种操作
1 k d, 修改k的为值增加d
2 l r, 查询l到r的区间和
3 l r, 间l到r区间上的所以数变成最近的斐波那契数,相等的话取向下取。
解题思路:线段树,对于每个节点新增一个bool表示该节点以下的位置是否都是斐波那契数。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)|1)
using namespace std;
typedef __int64 ll;
const int maxn = 100005;
const int maxf = 100;
const ll INF = 2000000000000000LL;
int n, m;
ll fib[maxf], fn, num[maxn];
struct maxnode {
int l, r;
ll sum;
bool isfib;
void set (int l, int r, ll sum, bool isfib) {
this->l = l;
this->r = r;
this->sum = sum;
this->isfib = isfib;
}
} node[4 * maxn];
void init () {
fib[0] = fib[1] = 1;
for (fn = 2;; fn++) {
fib[fn] = fib[fn - 2] + fib[fn - 1];
if (fib[fn] > INF)
break;
}
}
void pushup(int x) {
int l = lson(x), r = rson(x);
node[x].isfib = (node[l].isfib && node[r].isfib);
node[x].sum = node[l].sum + node[r].sum;;
}
void build(int l, int r, int x) {
node[x].set(l, r, 0, false);
if (l == r)
return;
int mid = (l + r) / 2;
build(l, mid, lson(x));
build(mid + 1, r, rson(x));
}
ll find (ll x) {
int id;
ll ans = INF;
for (int i = 0; i < fn; i++) {
ll k = (fib[i] > x ? fib[i] - x : x - fib[i]);
if (k < ans) {
ans = k;
id = i;
}
}
return fib[id];
}
void add (int k, ll v, int x) {
if (node[x].l == k && node[x].r == k) {
node[x].sum += v;
node[x].isfib = (find(node[x].sum) == node[x].sum ? true : false);
return;
}
int mid = (node[x].l + node[x].r) / 2;
if (k <= mid)
add(k, v, lson(x));
else if (k > mid)
add(k, v, rson(x));
pushup(x);
}
void insert(int l, int r, int x) {
if (node[x].isfib)
return;
if (node[x].l == node[x].r) {
node[x].sum = find(node[x].sum);
node[x].isfib = true;
return;
}
int mid = (node[x].l + node[x].r) / 2;
if (l <= mid)
insert(l, r, lson(x));
if (r > mid)
insert(l, r, rson(x));
pushup(x);
}
ll query(int l, int r, int x) {
if (node[x].l >= l && node[x].r <= r)
return node[x].sum;
int mid = (node[x].l + node[x].r) / 2;
ll ans = 0;
if (l <= mid)
ans += query(l, r, lson(x));
if (r > mid)
ans += query(l, r, rson(x));
return ans;
}
int main() {
init();
while (scanf("%d%d", &n, &m) == 2) {
build(1, n, 1);
int Q, a, b;
ll v;
while (m--) {
scanf("%d", &Q);
if (Q == 1) {
scanf("%d%I64d", &a, &v);
add(a, v, 1);
} else if (Q == 2) {
scanf("%d%d", &a, &b);
printf("%I64d\n", query(a, b, 1));
} else {
scanf("%d%d", &a, &b);
insert(a, b, 1);
}
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
NULL 博文链接:https://128kj.iteye.com/blog/1734821
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码