4
13
2015
0

我的线段树模板的一个坑点

我就是不听老人言……自己yy的模板果然出了问题……

这样的,我的写法里面必须push之后节点内的信息才是正确的

但是在modify中

注:#define lcq lc,l,mid             #define rcq rc,mid+1,r

if (a <= mid) modify(lcq,wq,d);

if (b >   mid) modify(rcq,wq,d);

upd(x);

碉堡了!可能只是递归到一边,然后另外一边没有push!真可怕!

所以应该改成

if (a <= mid) modify(lcq,wq,d); else push(lcq);

if (b >   mid) modify(rcq,wq,d); else push(rcq);

upd(x);

或者在upd里面加上push(lcq);push(rcq); 反正都一样,这样大概常数小一些

一定不要忘啦

Category: 未分类 | Tags:
1
8
2015
0

写题的时候debug出的错误

 

  1. 【bzoj1798】sb的线段树居然在update的时候忘记mod p

  2. 【bzoj1293】在增加右边界r的时候没有考虑到r<=n

  3. 【bzoj1854】写数组模拟链表的时候(尤其是存图和hash)可以记录当前这个点最后的一个后继,这样插入就是O(1)的了

         

    procedure add_edge(a,b:longint);

    var

     i:longint;

    begin

     inc(l);v[l]:=b;next[l]:=0; 

     i:=ut[a];if i=0 then begin u[a]:=l;ut[a]:=l;exit;end; 

     next[i]:=l;ut[a]:=l;

    end;

     

  4. 【bzoj3631】倍增LCA调整到同一深度的时候不!要!暴!力!要用倍增数组调整……

               u,v是双向的,边是2n的……傻逼就开了n的数组是闹咋样啊……(论跑随机大数据的重要性

5.  【bzoj1406】这题最后对答案排序可能无解……然后如果无解快排看起来就是这个样子sort(1,0)一定会死循环!所以小心                    sort(l,r) 一定要有l<=r

                还有开始枚举约数的时候n mod j<>0没有continue掉时什么心态……

6.【bzoj1857】 囧掉了囧掉了囧掉了!注意1.向量a,b的a b顺序很重要,所以swap了l r之后就不能用a b了 要用l r

               前后继的两个红色特的特判也很重要,总之斜率就是小心delta x=3或者dealta x=0 & delta y=0的

               

 

function next(x,a,b:dot):dot;

begin

 if check(a,b) then exit(x);

 if b.x-a.x<eps then begin 

     x.y:=x.y+eps;exit(x);

 end;

 x.x:=x.x+eps;

 x.y:=x.y+((b.y-a.y)*eps)/(b.x-a.x);

 exit(x); 

end;

7.【bzoj1986】喷头是向两边喷的囧……所以要把奇数过滤掉

8.【bzoj1856】注意费马小定理算乘法逆是p-2次方

9.【bzoj2440】注意在线性筛法计算欧拉函数的时候特殊处理i mod p[j]=0的情况(其实也不用太特殊啦)

              10^9二分就要开int64了

10.【bzoj1610】由于x y都是1000的范围的,eps取10^(-8)才行

11.【bzoj1614】无向图当做双向的有向图来存的时候原本边数是n,那么现在就要变成2n,数组要开够!

               (要跑随机大数据……&

12.【bzoj1046】在函数里返回一个值一定要记得写exit

13.【bzoj2007】swap居然没加var……感受一下……太傻逼了

               嗯……i j两个变量不要打反了

               (其实这次的堆的写法我从以前繁琐的写法稍微修改了一下,感觉好多了

14.【bzoj2957】写线段树的时候要 先判断是否到了叶子(别忘了exit) 然后再递归

               这道题在update的时候相当有讲究

15.【bzoj2115】写1 shl 60会爆longint 要写成int64(1) shl 60

16.【bzoj2242】:

  1. a的逆元在 mod质数p意义下是a^(p-2)而非a^(p-1)

  2. 小心,所有东西重复使用之前都要清0,比如hash

  3. 不要混用halt exit break(多傻逼的错误)

  4.  注意特判,0是没有逆元的。所以 a mod p=0 的情况要特殊处理

  5. 小心代码的常数 能用mod p搞定 坚决不 while x<0 do inc(x,p) 改过之后一下子快了3s+

17.【bzoj3144】最大流的s和t是全局定义的,之后在main()里千万不能写成int s=,t= 而应该写成s=;t=;

18.【bzoj2154】: 分块的时候做了前缀和,在统计的时候就不用*(r-l+1)了

19.【bzoj1014】:

    1.o->upd() in insert() && build();
    2.char数组 scanf("%c");的时候是从0开始的 所以build的时候应该用s[l-1]
    3.insert之后记得n++
    4.l1 r1比较之前应该把负数变成正的并% Mod 过程中关键的地方应该使用long long 避免溢出
Category: 未分类 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com