#define MAX(x,y) x>y?x:y
从昨天晚上到今天晚上,一直在调试一道线段树求最值的简单题,就是hdu的1754,一直TLE,无语,如此简单的题怎么会这样。搜索别人的代码,发现思路都一样,怎么会这样。
晚上重新写了一遍,结果AC了。然后就找原因,唯一不同的是一个用了
另一个AC的用了
int max(int x, int y)
{
return x > y ? x : y;
}
这下当我调用MAX对query的结果进行取最值的时候就出现了问题。重复计算了一次,导致了致命的超时!。
作为证据贴下自己的两个代码:
//超时的代码:
#include <stdio.h>
#define N 200010
#define MAX(x,y) x>y?x:y
typedef struct{
int left, right, mid;
int score;
}SegNode;
SegNode a[4 * N + 1];
int p[N + 1];
void build(int left, int right, int ind)
{
int mid, tl, tr;
a[ind].left = left;
a[ind].right = right;
if(left == right)
{
a[ind].score = p[left];
return ;
}
a[ind].mid = (left + right) / 2;
build(left, a[ind].mid, ind * 2);
build(a[ind].mid +1, right, ind * 2 + 1);
a[ind].score = MAX( a[ind * 2].score, a[ind * 2 + 1].score ); // sum of the num
}
int query(int left, int right, int ind)
{
if(a[ind].left == left && right == a[ind].right)
return a[ind].score;
if(right <= a[ind].mid)
return query(left, right, ind * 2);
else if(left > a[ind].mid)
return query(left, right, ind * 2 + 1);
else
return MAX(query(left, a[ind].mid, ind * 2) , query(a[ind].mid +1, right, ind * 2 + 1));
}
void modify(int site, int var, int ind)
{
if(a[ind].left == a[ind].right)
{
a[ind].score = var;
return;
}
if(site <= a[ind].mid)
modify(site, var, ind * 2);
else
modify(site, var, ind * 2 + 1);
a[ind].score = MAX(a[ind * 2].score , a[ind * 2 + 1].score);
}
int main()
{
int t;
int n;
int i, j, k;
int st, ed;
char cmd[10];
while(scanf("%d%d", &n, &k) == 2)
{
for(i = 1; i <= n; i++)
{
scanf("%d", &p[i]);
}
build(1, n, 1);
while(k--)
{
getchar();
scanf("%c%d%d", &cmd[0], &st, &ed);
if(cmd[0] == 'Q')
printf("%d\n", query(st, ed, 1));
else
modify(st, ed, 1);
}
}
return 0;
}
//AC的代码:
#include <stdio.h>
#define N 200010
typedef struct{
int l, r, mid;
int mmax;
}NODE;
static inline int MAX(int x, int y)
{
return x>y?x:y;
}
NODE node[N * 4 + 1];
int val[N];
void build_tree(int ll, int rr, int ind)
{
node[ind].l = ll;
node[ind].r = rr;
if(ll == rr)
{
node[ind].mmax = val[ll];
return ;
}
node[ind].mid = (ll + rr) / 2;
build_tree(ll, node[ind].mid, ind * 2);
build_tree(node[ind].mid + 1 , rr, ind * 2 + 1);
node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1 ].mmax);
}
int query(int ll, int rr, int ind)
{
if(ll == node[ind].l && rr == node[ind].r)
return node[ind].mmax;
if(rr <= node[ind].mid)
return query(ll, rr, ind * 2);
if(ll > node[ind].mid)
return query(ll, rr, ind * 2 + 1);
return MAX(query(ll, node[ind].mid, ind * 2), query(node[ind].mid + 1, rr, ind * 2 + 1));
}
void update(int site, int b, int ind)
{
if(node[ind].l == node[ind].r)
{
node[ind].mmax = b;
return ;
}
if(site <= node[ind].mid)
update(site, b, ind * 2);
else
update(site, b, ind * 2 + 1);
node[ind].mmax = MAX(node[ind * 2].mmax, node[ind * 2 + 1].mmax);
}
int main()
{
int n, k;
int i;
int a, b;
char c;
while(scanf("%d%d", &n, &k) != EOF)
{
for(i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
}
//printf("yes\n");
build_tree(1, n, 1);
//printf("over\n");
while(k--)
{
getchar();
scanf("%c%d%d", &c, &a, &b);
//printf("%c %d %d\n", c, a, b);
if(c == 'Q')
printf("%d\n", query(a, b, 1));
else
update(a, b, 1);
}
}
return 0;
}
分享到:
相关推荐
更加清楚明了得学懂c语言,明确宏定义在c中是怎样表示的,让大家少走弯路。
Excel VBA 或者 WPS JS宏 要批量生成二维码或者条形码,一般通过网络请求的方式从网站上获取,对于不能联网的电脑非常麻烦。 另类的解决办法:利用bwip-js包,通过node.js环境搭建本地服务器 ,将其打包成exe可执行...
仓库管理中,有时需要同时记录多个仓库账目。比如分为材料科库、成品库等;也有按地区 分的,比如北京仓、上海仓等。此Exce1表格,能同时管理多个仓库账目,提高工作效率...注意使用前先安装好wps宏插件,压缩包中有。
(原始宏返回一个与传递给它们的第一个表单具有相同元数据的表单,这些宏不会复制这种行为) (要更清楚地描述他们的行为,请查看测试。)部分的一个不完全准备好的partial实现,额外支持在后面的参数应该传入的...
汇编教程 非常详细 说明的非常清楚 学汇编很好的教程 课程介绍 第1章 预备知识 1.1 汇编语言的由来及其特点 1 机器语言 2 汇编语言 3 汇编程序 4 汇编语言的主要特点 5 汇编语言的使用领域 1.2 ...
要学或正在学计算机汇编的同学可能用的上哈,都是一些基础的宏和DEMO程序,初学者适用。 <br> 下面附上源程序以及DEMO程序,由于汇编程序受计算机环境影响较大,今天发现这些以前的DEMO程序运行效果和以前大不...
在我还在学习这门语言时,极大地帮助了我通过示例样式的宏来理解宏。 不幸的是,原书自 2016 年 4 月以来就没有更新过,而 Rust 语言及其宏系统也在不断发展。 这就是为什么我负责更新这本书并尽可能保持更新,同时...
我们可以使用Gateway的宏轻松地做到这一点,如下所示: 在lib/stripe.ex ,我们将Gateway与标头和相应值的列表一起使用。 网关会自动将这些内容放入HTTPoison.Base使用的process_request_headers/1方法中defmodule ...
5.10但是如果NULL的值改变了,比如在使用非零内部空指针的机器上,用NULL(而不是0) 不是更好吗? 5.11 我曾经使用过一个编译器,不使用NULL就不能编译。 5.12 我用预处理宏#defineNullptr(type)(type*)0帮助...
5.10 但是如果NULL的值改变了,比如在使用非零内部空指针的机器上,用NULL(而不是0) 不是更好吗? 58 5.11 我曾经使用过一个编译器,不使用NULL就不能编译。 58 5.12 我用预处理宏#define Nullptr(type)(type...
再举一个例子,假设正在进行帐目的结算,想要用蓝色显示结余超过$50,000的帐目,负数值用红色显示在括号中,其余的值用缺省颜色显示,可以创建如下的格式: “[蓝色][>50000] $#,##0.00_);[红色][]( $#,##0.00); $#...
clear(),del()分别是清楚控制台所有字符,删除光标前一个字符 HideCursor(),RevealCursor(),SaveCursor(),RecoverCursor();分别是隐藏、显示光标,保存、恢复光标位置 RED,GREEN,YELLOW,BLUE,PURPLE,CYAN,GREY都是...
第三个参数指明我们想要查找的错误代码的号码,第四个参数指明我们想要文本描述使用什么语言。 如果FormatMessage函数运行成功,那么错误代码的文本描述就位于内存块中,我将它拷贝到对话框底部的滚动窗口中。如果...
也不是每个人都喜欢新的自定义级别布局,直到 log4cxx 正确支持自定义级别添加(不清楚何时会发生)。 好消息是它可以被编辑:推荐的使用 ITRLogging 的方法是将它嵌入到一个公共共享库中。 已选择默认布局来解决...
一个漂亮的程序,不是在于你应用的技术多么高深,而是能够把高深的技术描述的清楚易懂。 在Java的IDE环境——Eclispe中,有很多中注释的,并且设置注释也是很方便的,因为现在从事C++,嘻嘻,Eclispe已经卸载,至于...
很多小伙伴找不到官网 但是还需要下载,雷狼鼠标驱动软件,windows安装即可使用。如果不清楚自己的版本,可以尝试下载另外两个版本。
很多小伙伴找不到官网 但是还需要下载,雷狼鼠标驱动软件,windows安装即可使用。如果不清楚自己的版本,可以尝试下载另外两个版本。
Scheme的静态类型方言的想法 名称:我将在这里使用Steme,但它可能是Statics或其他... 宏:在Steme中与Scheme中的宏相同(不清楚要支持哪些R7RS-large宏); 宏扩展位于类型推断之前。 不清楚是否可以用Steme编写低级宏