Wow! Such Sequence! （线段树） hdu4893
2024-09-30 23:50:04
http://acm.hdu.edu.cn/showproblem.php?pid=4893
先贴上一份还没过的代码，不知道拿出错了 1 // by caonima
2 // hehe
3 #include <cstring>
4 #include <algorithm>
5 #include <cstdio>
6 #include <queue>
7 #include <stack>
8 #include <vector>
9 #include <map>
10 #include <cmath>
11 #include <set>
12 #include <iostream>
13 #include <string>
14 using namespace std;
15 #define LL __int64
16 const int MAX = 1e6+;
17 const LL inf = 1LL<<;
18 LL sum[MAX<<],col[MAX<<],fib_sum[MAX<<],fib[MAX];
19 int cur=;
20 void init() {
21 fib[]=fib[]=;
22 for(int i=;i<MAX;i++) {
23 if(fib[i-]+fib[i-]>inf) break;
24 fib[i]=fib[i-]+fib[i-];
25 cur++;
26 }
27 return ;
28 }
29 void push_up(int o) {
30 fib_sum[o]=fib_sum[o<<]+fib_sum[o<<|];
31 sum[o]=sum[o<<]+sum[o<<|];
32 }
33 void push_down(int o) {
34 if(col[o]!=-) {
35 col[o<<]=col[o<<|]=col[o];
36 sum[o<<]=fib_sum[o<<];
37 sum[o<<|]=fib_sum[o<<|];
38 col[o]=-;
39 }
40 return;
41 }
42 void build(int L,int R,int o) {
43 if(L==R) {
44 sum[o]=;
45 fib_sum[o]=; col[o]=-;
46 return ;
47 }
48 int mid=(L+R)>>;
49 build(L,mid,o<<);
50 build(mid+,R,o<<|);
51 push_up(o);
52 }
53 void add(int L,int R,int o,int k,int val) {
54 if(L==R) {
55 sum[o]+=(LL)val;
56 int x=(int)(lower_bound(fib,fib+cur,sum[o])-fib);
57 // printf("%I64d %I64d\n",fib[x],fib[x-1]);
58 // printf("%I64d\n",sum[o]);
59
60 if(x==) fib_sum[o]=fib[x];
61 else if((-fib[x]+sum[o])>=(-fib[x-]+sum[o])) fib_sum[o]=fib[x-];
62 else fib_sum[o]=fib[x];
63 // printf("%I64d\n",fib_sum[o]);
64 return ;
65 }
66 push_down(o);
67 int mid=(L+R)>>;
68 if(k<=mid) add(L,mid,o<<,k,val);
69 else add(mid+,R,o<<|,k,val);
70 push_up(o);
71 }
72
73 void Update(int L,int R,int o,int ls,int rs) {
74 if(ls<=L&&rs>=R) {
75 sum[o]=fib_sum[o];
76 col[o]=;
77 return ;
78 }
79 push_down(o);
80 int mid=(L+R)>>;
81 if(ls<=mid) Update(L,mid,o<<,ls,rs);
82 if(rs>mid) Update(mid+,R,o<<|,ls,rs);
83 push_up(o);
84 }
85 LL Query(int L,int R,int o,int ls,int rs) {
86 if(ls<=L&&rs>=R) {
87 return sum[o];
88 }
89 push_down(o);
90 int mid=(L+R)>>;
91 LL res=;
92 if(ls<=mid) res+=Query(L,mid,o<<,ls,rs);
93 if(rs>mid) res+=Query(mid+,R,o<<|,ls,rs);
94 return res;
95
96 }
97 int main() {
98 int n,m,op,ls,rs;
99 init();
while(scanf("%d %d",&n,&m)==) {
build(,n,);
for(int i=;i<m;i++) {
scanf("%d %d %d",&op,&ls,&rs);
if(op==) {
add(,n,,ls,rs);
}
else if(op==) {
printf("%I64d\n",Query(,n,,ls,rs));
}
else {
Update(,n,,ls,rs);
}
}
}
return ;
116 }
最新文章
- 【白话设计模式四】单例模式(Singleton)
- ionic实现上拉到底内容提示
- php实现木桶排序
- Nginx学习笔记（五） 源码分析&内存模块&内存对齐
- VirtualBox clonevdi文件和修改vdi的uuid
- Python 强大而易用的文件操作（转载）
- 浙大PTA - - File Transfer
- IO流输入 输出流 字符字节流
- [EXTJS5学习笔记]第二十六节 在eclipse/myeclipse中使用sencha extjs的插件
- 第一课：Hadoop集群环境搭建
- flask实战-留言板-Web程序开发流程
- Linux基础入门-用户及文件权限管理
- Yii2控制台命令
- SNF软件开发机器人产品白皮书
- C++ map的方法
- 本文档教授大家在yii2.0里实现文件上传 首先我们来实现单文件上传
- Breeze 部署 Kubernetes 1.12.1高可用集群
- mysql binglog server的设置方法【原创】
- IOS绘图详解
- AngularJS中实现显示或隐藏动画效果的3种方式