HDU 4893

Wow! Such Sequence!

线段树。加个标记就可以了。

Wow! Such Sequence!

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2403 Accepted Submission(s): 710

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.

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.

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

Author

Fudan University

Source

2014 Multi-University Training Contest 3

只需要使用线段树，加个懒得标记。 sum1表示当前的和，sum2表示当前最近的斐波那契数列的和。 然后直接搞就可以了。

/* ***
Author :kuangbin
Created Time :2014/8/3 15:06:42
File Name :E:\2014ACM\比赛\2014多校训练\2014多校3\HDU4893.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
long long f[72];
const int MAXN = 100010;
struct Node
{
int l,r;
int lazy;
long long sum1,sum2;
}segTree[MAXN<<2];
void Update(int i)
{
segTree[i].sum1 = segTree[i].sum2;
segTree[i].lazy = 1;
}
void push_up(int i)
{
segTree[i].sum1 = segTree[i<<1].sum1 + segTree[(i<<1)|1].sum1;
segTree[i].sum2 = segTree[i<<1].sum2 + segTree[(i<<1)|1].sum2;
}
void push_down(int i)
{
if(segTree[i].lazy)
{
Update(i<<1);
Update((i<<1)|1);
segTree[i].lazy = 0;
}
}
void build(int i,int l,int r)
{
segTree[i].l = l;
segTree[i].r = r;
segTree[i].lazy = 0;
if(l == r)
{
segTree[i].sum1 = 0;
segTree[i].sum2 = 1;
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
push_up(i);
}

void Add(int i,int k,int d)
{
if(segTree[i].l == k && segTree[i].r == k)
{
segTree[i].sum1 += d;
int id = lower_bound(f,f+70,segTree[i].sum1) - f;
segTree[i].sum2 = f[id];
if(id > 0)
{
if(segTree[i].sum1-f[id-1] <= f[id]-segTree[i].sum1)
segTree[i].sum2 = f[id-1];
}
return;
}
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(k <= mid)Add(i<<1,k,d);
else Add((i<<1)|1,k,d);
push_up(i);
}
long long query(int i,int l,int r)
{
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].sum1;
push_down(i);
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)return query(i<<1,l,r);
else if(l > mid)return query((i<<1)|1,l,r);
else return query(i<<1,l,mid) + query((i<<1)|1,mid+1,r);
}
void Change(int i,int l,int r)
{
if(segTree[i].l == l && segTree[i].r == r)
{
Update(i);
return;
}
if(segTree[i].lazy)return;
int mid = (segTree[i].l + segTree[i].r)/2;
if(r <= mid)Change(i<<1,l,r);
else if(l > mid)Change((i<<1)|1,l,r);
else
{
Change(i<<1,l,mid);
Change((i<<1)|1,mid+1,r);
}
push_up(i);
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
f[0] = 1;
f[1] = 1;
for(int i = 2;i < 70;i++)
{
f[i] = f[i-1]+f[i-2];
}
int n,m;
while(scanf(“%d%d”,&n,&m) == 2)
{
build(1,1,n);
int op;
int l,r;
while(m–)
{
scanf(“%d%d%d”,&op,&l,&r);
if(op == 1)Add(1,l,r);
else if(op == 2)printf(“%I64d\n”,query(1,l,r));
else Change(1,l,r);
}
}
return 0;
}