hdu4893 Wow! Such Sequence!,ツリー配列、線分ツリー、単点修正、区間更新
5982 ワード
2014 Multi-University Training Contest 3
1007題
クリックしてリンクを開く
単点修正、区間更新(線分ツリーLazyマーク)
ツリー配列:
線分ツリー:
1007題
クリックしてリンクを開く
単点修正、区間更新(線分ツリーLazyマーク)
ツリー配列:
/*
:
1、 set num[i] Nearest Fibonacci number i,
set ,num[i] -> Nearest Fibonacci number, i
set 。
。 。
2、 Nearest Fibonacci number。
3、 。
。。。。
*/
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
int n, m;
LL C[maxn], num[maxn], f[maxn];
vector<int> vec;
set<int> s;
void Init()
{
int i;
f[0]=1;
f[1]=1;
for(i=2; i<=91; i++) {
f[i]=f[i-1]+f[i-2];
}
}
int lowbit(int x)
{
return x&(-x);
}
void update(int i, LL v)
{
for(; i<=n; i += lowbit(i)) C[i] +=v;
}
LL getsum(int i)
{
LL ret=0;
for(; i>0; i-=lowbit(i)) ret +=C[i];
return ret;
}
//
template <class T>
inline void scan_d(T &ret)
{
char c;
ret=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
LL Find(LL x)
{
int t = lower_bound(f,f+92, x) - f;
LL k;
if(t==0) k = 1;
else {
if(abs(f[t]- x)<abs(x-f[t-1])) k =f[t];
else k = f[t-1];
}
return k;
}
int main()
{
Init();
int i, j;
int a, b, c;
//freopen("in.txt","r",stdin);
while(~scanf("%d%d", &n, &m)) {
memset(num, 0, sizeof(LL)*(n+2) );
memset(C, 0, sizeof(LL)*(n+2) );
s.clear();
set<int>::iterator pos;
for(i=1; i<=n; ++i) s.insert(i);
while(m--) {
scan_d(a);
scan_d(b);
scan_d(c);
//scanf("%d%d%d", &a, &b, &c);
if(a==1) {
update(b, c);
num[b] += c;
s.insert(b);
} else if(a==2) {
LL ans = getsum(c) - getsum(b-1);
printf("%I64d
", ans);
} else if(a==3) {
vec.clear();
for( pos = s.lower_bound(b); ((*pos)<=c)&&(pos!=s.end());pos++) {
int p = *pos;
LL New = Find(num[p]); //num[p] -> Nearest Fibonacci number
update(p, New - num[p]);
num[p] = New;
vec.push_back(p);
}
for(i=0; i<vec.size(); ++i)
s.erase(vec[i]);
}
}
}
return 0;
}
線分ツリー:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
struct node {
int l, r;
LL sum, fibsum;
int lazy;
} tree[maxn*4];
LL f[100];
void calc_fib()
{
int i;
f[0] = f[1] = 1;
for(i=2; i<=91; ++i) f[i] = f[i-1] + f[i-2];
}
LL Find(LL x)
{
int t = lower_bound(f, f+92, x) - f;
LL k;
if(t==0) k = 1;
else {
if(abs(f[t]- x)<abs(x-f[t-1])) k = f[t];
else k = f[t-1];
}
return k;
}
void PushUp(int rt)
{
tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
tree[rt].fibsum = tree[rt<<1].fibsum + tree[rt<<1|1].fibsum;
}
void PushDown(int rt)
{
if(tree[rt].lazy) {
tree[rt<<1].sum = tree[rt<<1].fibsum;
tree[rt<<1|1].sum = tree[rt<<1|1].fibsum;
tree[rt<<1].lazy = tree[rt<<1|1].lazy = 1;
tree[rt].lazy = 0;
}
}
void build(int rt, int l, int r)
{
tree[rt].l = l;
tree[rt].r = r;
tree[rt].sum = tree[rt].fibsum = 0;
tree[rt].lazy = 0;
if(l == r) {
tree[rt].sum = 0;
tree[rt].fibsum = 1;
return ;
}
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
PushUp(rt);
}
void add(int rt, int pos, LL v)
{
if(tree[rt].l == tree[rt].r) {
tree[rt].lazy = 0;
tree[rt].sum += v;
tree[rt].fibsum = Find(tree[rt].sum );
return ;
}
PushDown(rt);
int mid = (tree[rt].l + tree[rt].r)>>1;
if(pos<= mid) add(rt<<1, pos, v);
else add(rt<<1|1, pos, v);
PushUp(rt);
}
LL sum(int rt, int l, int r)
{
if(l <= tree[rt].l && tree[rt].r <= r) {
return tree[rt].sum;
}
PushDown(rt);
int mid = (tree[rt].l + tree[rt].r)>>1;
LL ret = 0;
if(l<=mid) ret += sum(rt<<1, l, r);
if(r > mid) ret += sum(rt<<1|1, l, r);
return ret;
}
void update(int rt, int l, int r)
{
if(l <= tree[rt].l && tree[rt].r <= r) {
tree[rt].lazy = 1;
tree[rt].sum = tree[rt].fibsum;
return ;
}
PushDown(rt);
int mid = (tree[rt].l + tree[rt].r)>>1;
if(l<=mid) update(rt<<1, l, r);
if(r >mid) update(rt<<1|1, l, r);
PushUp(rt);
}
//
template <class T>
inline void scan_d(T &ret)
{
char c;
ret=0;
while((c=getchar())<'0'||c>'9');
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
int main()
{
int n, m;
int op, l, r;
// freopen("in.txt","r",stdin);
calc_fib();
while(~scanf("%d%d", &n, &m)) {
build(1,1,n);
while(m--) {
scan_d(op);
scan_d(l);
scan_d(r);
//scanf("%d%d%d", &op, &l, &r);
if(op==1) add(1, l, r);
if(op==2) printf("%I64d
", sum(1, l, r));
if(op==3) update(1, l, r);
}
}
return 0;
}