Algorithm

线段树-两种操作

线段树是一种二叉树结构，能够在lg(n)的复杂度下完成一些计算。
最长见的就是数列求和之类的，而且还能够支持单点修改甚至是区间修改。

线段树的精髓在于懒惰标记，也就是说，在更新的时候，不更新全部子节点，只会打一个标记。

比如说一段区间要加一个值，它不会在每个叶子节点加上相应数值，而是在覆盖需要修改的子节点的区间上加一个tag要加多少，相应的因为要保证上层计算无误，所以要根据自己的孩子数更新自己的sum值。
如果下次要更新这段覆盖的区间的子区间，可以把相应的标记下放。

线段树支持两种操作其实也比较简单，就是考虑两种操作的优先级，根据优先级判断相关节点应该怎么操作。

下面是一个乘和加两种操作的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
Sample Input:
6 3
add 0 2 1
mul 2 4 3
sum 0 3
6 3
sum 0 5
mul 0 5 4
sum 0 5
Sample Output:
21
15
60
先输入两个数n和m,代表数组为0,1,2,3,...,n-1,要进行m种操作
下m行,每行开始是一个字符串,代表操作。
add 0 2 1
代表位置为0,1,2的数 都加1
mul 2 4 3
代表位置为2,3,4的数 都乘3
sum 0 3
代表求0,1,2,3的和
*/
/***********************************************\
 |Author: YMC
 |Created Time: 2015-1-20 12:14:28
 |File Name: Multiply_and_Add_zjut1101.cpp
 |Description: 
\***********************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
#define mset(l,n) memset(l,n,sizeof(l))
#define rep(i,n) for(int i=0;i<n;++i)
#define maxx(a) memset(a, 0x3f, sizeof(a))
#define zero(a) memset(a, 0, sizeof(a))
#define srep(i,n) for(i = 1;i <= n;i ++)
#define MP make_pair
const int inf=0x3f3f3f3f ;
const double eps=1e-8 ;
const double pi=acos (-1.0);
typedef long long ll;
using namespace std;
const int maxn = 100005;
const int mod = 1000000007;
struct Tree{
    ll sum;
    int l,r;
    ll add,mul;
}tree[maxn << 2];
char op[10];
int n,m;
int a,b;
ll c;
void pushup(int rt) {
    tree[rt].sum = tree[L(rt)].sum + tree[R(rt)].sum;
    tree[rt].sum %= mod;
}
void pushdown(int rt) {
    if(tree[rt].add != 0 || tree[rt].mul != 1){
        tree[L(rt)].sum = tree[L(rt)].sum * tree[rt].mul + tree[rt].add*(tree[L(rt)].r - tree[L(rt)].l + 1);
        tree[L(rt)].sum %= mod;
        tree[L(rt)].mul *= tree[rt].mul;
        tree[L(rt)].mul %= mod;
        tree[L(rt)].add = tree[L(rt)].add * tree[rt].mul + tree[rt].add;
        tree[L(rt)].add %= mod;
        tree[R(rt)].sum = tree[R(rt)].sum * tree[rt].mul + tree[rt].add*(tree[R(rt)].r - tree[R(rt)].l + 1);
        tree[R(rt)].sum %= mod;
        tree[R(rt)].mul *= tree[rt].mul;
        tree[R(rt)].mul %= mod;
        tree[R(rt)].add = tree[R(rt)].add * tree[rt].mul + tree[rt].add;
        tree[R(rt)].add %= mod;
        tree[rt].add = 0;
        tree[rt].mul = 1;
    }
}
void build(int l,int r,int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].add = 0;
    tree[rt].mul = 1;
    tree[rt].sum = l;
    if(l == r) {
        return ;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    build(l,mid,L(rt));
    build(mid + 1, r, R(rt));
    tree[rt].sum = tree[L(rt)].sum + tree[R(rt)].sum;
    tree[rt].sum %= mod;
}
void add(int l,int r,ll v,int rt) {
    if(l <= tree[rt].l && r >= tree[rt].r) {
        tree[rt].add += v;
        tree[rt].add %= mod;
        tree[rt].sum += v*(tree[rt].r - tree[rt].l + 1);
        tree[rt].sum %= mod;
        return ;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        add(l,r,v,L(rt));
    } else if(l >= mid + 1) {
        add(l,r,v,R(rt));
    } else {
        add(l,mid,v,L(rt));
        add(mid+1,r,v,R(rt));
    }
    pushup(rt);
}
void mul(int l,int r,ll v,int rt) {
    if(l <= tree[rt].l && r >= tree[rt].r) {
        tree[rt].mul *= v;
        tree[rt].mul %= mod;
        tree[rt].add *= v;
        tree[rt].add %= mod;
        tree[rt].sum *= v;
        tree[rt].sum %= mod;
        return ;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        mul(l,r,v,L(rt));
    } else if(l >= mid + 1) {
        mul(l,r,v,R(rt));
    } else {
        mul(l,mid,v,L(rt));
        mul(mid + 1, r, v, R(rt));
    }
    pushup(rt);
} 
ll query(int l,int r,int rt) {
    ll sum = 0;
    if(l <= tree[rt].l && r >= tree[rt].r) {
        return tree[rt].sum % mod;
    }
    pushdown(rt);
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(mid >= r) {
        return query(l,r,L(rt)) % mod;
    } else if(l >= mid + 1) {
        return query(l,r,R(rt)) % mod;
    } else {
        sum += query(l,mid,L(rt));
        sum += query(mid+1,r,R(rt));
        return sum % mod;
    }
}
int main() {
	//freopen("input.txt","r",stdin); 
    while(scanf("%d %d",&n,&m) != EOF) {
        build(0,n,1);
        while(m --) {
            scanf("%s",op);
            if(op[0] == 'a') {
                scanf("%d %d %lld",&a,&b,&c);
                add(a,b,c,1);
            } else if(op[0] == 'm') {
                scanf("%d %d %lld",&a,&b,&c);
                mul(a,b,c,1);
            } else {
                scanf("%d %d",&a,&b);
                printf("%lld\n",query(a,b,1));
            }
        }
        puts("");
    }
	return 0;
}
Mess

python 字符问题

把vps上的脚本迁移了一下，从centos转到了debian,发现有些脚本不能用了。。

可能是编码问题，然后转化为各种编码，发现还是符号错误。

最终才发现了问题所在。。

1
if u'哈哈' in content:

这个在python3上面是非法的。因为python3只有一种字符串类型：unicode字符串
u’哈哈’ 在python3对应‘哈哈’
ur’哈哈’ 在python3对应r‘哈哈’

具体可以参见http://www.360doc.com/content/14/0619/23/16740871_388198818.shtml

不知道为什么，我用的相同的源码包编译的python3.2，在centos下u’哈哈’是可以的，但是在debian下就不可以。。

因为一直以为可以，所以一直认为编码错误。。没想到到后来是语法错误。。

其中vim可以通过下面命令设置编码

1
2
:set fileencoding=UTF8  
:set fileencoding=gbk

还可以通过下面命令查看编码

1
:set enc

shell下可以通过 file filename来查看文件编码。

Notes

gdb-notes

#执行程序(gdb启动时没有选择程序名称)

1
(gdb)file test

#运行准备好的程序

1
2
(gdb)run 3
//run 后面是指定的参数

#参数设置

1
set args 3

#查看默认参数

1
show args

#列文件清单

1
2
3
list line1,line2
//简写
l 1, 2

#打印数据

1
2
3
print var
//简写
p var

#计算函数调用返回值

1
p sum(3)

#打印结构体

1
2
p *io
//io为结构体

#设置断点

1
2
3
4
b filename:46
//b filename:linenum
b 46 if i==2

#打印断点信息

1
info break

#删除断点

1
delete b 8

#禁止,允许,清除断点

1
2
3
disable b 9
enable b 9
clean b 9

#单步调试

1
2
3
4
5
6
b 32        //在32行处设置断点
run 3       //运行程序，输入参数为3
n           //单步执行
s           //进入函数体内部
finish      //执行完函数
c           //继续执行到下个断点

#调用路径

1
bt

#打印指令处的汇编代码

1
disassemble sum     //sum是一个函数

#帮助

1
2
help
help c

Notes

nots of python

#list

1
2
3
4
5
6
7
classmates=['jack','Bob']
len(classmates)
#list元素也可以是list
list.append('xx')
list.insert(1,'xx')
list.pop()  #删除最后一个元素
list.pop(1)

#tuple, list的[]变为(),元素不可变

1
2
3
classmates=('jack','Bob')
#定义一个元素的tuple
t = (1,)

#if

1
2
3
4
5
6
if xx:
    do some thing
elif xx:
    do some thing
else:
    do some thing

#关于raw_input

1
2
a = int(raw_input('xx'))
#如果输入数字要强转

#dict

1
2
3
4
5
d={'a':100,'b':75,'c':50}
d.get('a')      #找不到返回None
d.get('a',x)    #找不到返回x
d.pop('a')      #删除
#dict的key必须是不可变的

#set

1
2
3
4
s = set([1,2,3])
s.add(4)
s.remove(4)
s1 & s2     #set可以做交集并集

#函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def my_abs(x):
    if x >= 0:
        return x
    else:
        return -x
#空函数
def nop():
    pass
#类型检查
def my_abs(x):
    if not isinstance(x,(int,float)):
        raise TypeError('bad operand type')
    #do some thing
#返回多个值
def func()
    return 1,2
#默认参数必须指向不变的对象！不然函数体可能会变
#可变参数
def getsum(*numbers):
    sum = 0
    for n in numbers:
        sum = sum + n * n
    return sum
#关键字参数
def person(name, age, **kw):
    print 'name:',name,'age:',age,'other:',kw
#参数可以组合，顺序必须是：必选参数，默认参数，可变参数，关键字参数
def func(a, b, c = 0,*args, **kw):
    xxx
#*args是可变参数，接收的是tuple
#**kw是关键字参数，接收的是dict

#切片

1
2
3
L[0:3]  #取0,1,2这三个元素
L[:3]   #同上
L[:10:2]    #从0到10，每2个取一个

#迭代

1
2
3
4
5
6
7
8
9
d = {'a':1,'b':2,'c':3}
for key in d:
    print key
for value in d.itervalues():
    xxx
#判断是否可迭代
from collections import Iterable
isinstance('abc',Iterable)  #'abc'是否可迭代

#列表生成式

1
2
3
4
5
6
7
8
9
10
11
12
range(1,11)
[x * x for x in range(1,11)]
[x * x for x in range(1,11) if x % 2 == 0]
[m + n for m in 'ABC' for n in 'XYZ']
#列出当前所有文件和目录名
import os
[d for d in os.listdir('.')]
d={'a':1,'b':2}
[k + '=' + v for k, v in d.iteritems()]
[s.lower() for s in L]

#生成器,按照函数先生成一部分

1
2
3
4
5
6
7
8
9
10
11
12
13
g = (x * x for x in range(10))
#和列表生成式区别是它是小括号
g.next()        #获取一个
for n in g:     #取出所有
    print n
#把函数改造为generator,注意yield,每次执行到yield就中断
def fib(max):
    n,a,b = 0,0,1
    while n < max:
        yield b
        a,b = b,a+b
        n = n + 1

#map and reduce

1
2
3
4
5
6
7
8
9
def add(x,y):
    return x+y
reduce(add, [1,3,5,7,9])
#返回25
def str2int(s):
    def fn(x,y):
        return x * 10 + y
    return reduce(fn,map(int,s))

#排序

1
2
3
sorted([1,3,2,5,4])
#也可以类似c++ STL一样自定义大小
sorted([1,2,4],cmp)     #cmp是一个函数

#匿名函数

1
2
3
4
map(lambda x: x*x, [1,2,3])
#返回[1,4,9]
f = lambda x : x*x

#decorator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def log(func):
    def wrapper(*args, **kw):
        print 'call %s():' %func.__name__
        return func(*args, **kw)
    return wrapper
#log是一个decorator,接受一个函数作为参数，返回一个函数
@log
def now():
    print 'xx'
#相当于now = log(now)
def log(func):
    @functools.wraps(func)
    def wrapper(*args, **kw):
        print 'call %s():' %func.__name__
        return func(*args, **kw)
    retrun wrapper
#上面写的decorator可以保证__name__是func

#偏函数

1
2
import functools
int2 = functools.partial(int, base=2)

#模块

1
2
#导入模块加别名
import cStringIO as StringIO

#gevent 协程

1
2
3
4
5
6
7
8
9
10
11
from gevent import monkey; monkey.patch_socket()
import gevent
def func(n):
    xxx
g1 = gevent.spawn(func, 1)
g2 = gevent.spawn(func, 1)
g1.join()
g2.join()
#g1和g2会依次运行。func在进行io操作或者sleep的时候会让其他的实例执行

#pack and unpack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#struct模块中最重要的三个函数是pack(), unpack(), calcsize()
pack(fmt, v1, v2, ...)
#按照给定的格式(fmt)，把数据封装成字符串(实际上是类似于c结构体的字节流)
unpack(fmt, string)
#按照给定的格式(fmt)解析字节流string，返回解析出来的tuple
calcsize(fmt)
#计算给定的格式(fmt)占用多少字节的内存
#string
string.maketrans(from, to)
#建立字符映射表
string.translate(s, table[, deletechars])
str.translate(table[, deletechars])
#解析字符串

Mess

unsigned int和int

今天发现C++上面一个容易犯的错误。一道简单的题坑了半个多小时。。

1
2
3
if(ma[i].size() > maxx) {
    maxx = ma[i].size();
}

这段话看起来很正常，在前面输出的时候发现，虽然ma[i].size()是大于maxx的，但是就是进入不了if语句。。

后来才发现，ma[i].size()是unsigned int。不能直接与int相比。。

以后真的要小心了。

Mess

shadowsocks和polipo配置

上github速度太慢。直接把shadowsocks架在龙芯上面了。
记录一下config文件。
config.json

1
2
3
4
5
6
7
8
9
{
        "server":"your_server",
        "server_port":port,
        "local_address":"0.0.0.0",
        "local_port":7070,
        "password":"passwd",
        "timeout":600,
        "method":"aes-256-cfb"
}

polipo.config

1
2
3
socksParentProxy = "127.0.0.1:7070"
socksProxyType = socks5
proxyAddress = 0.0.0.0

运行：

1
2
nohup sslocal -c config.json &
nohup polipo -c polipo.config &

polipo 默认端口在8123

Mess

openvz改变服务器时间

openvz 的时间如果有问题，那么cron执行时间就会错误，所以很有必要调整好时间。

可以使用以下命令

1
2
rm -rf /etc/localtime
ln -s /usr/share/zoneinfo/Asia/Shanghai /etc/localtime

如果还是不行。可以安装tzselect
可能需要

1
dpkg-reconfigure tzdata

ssh经常要后台运行一些东西。可以用screen
常用的几个命令

1
2
screen -ls
screen -r *****

Mess

aria2配置

aria2是一个轻型的下载软件，也有web端可以控制。

debian下安装aria2,aria2建议1.18以上
在 /etc/aria2下创建session文件和配置文件

1
2
3
cd /etc/aria2
touch aria2.session
vim aria2.conf
1
2
3
4
5
6
7
8
9
10
11
12
13
#文件保存目录自行修改
dir=/data
disable-ipv6=true
#打开rpc的目的是为了给web管理端用
enable-rpc=true
rpc-allow-origin-all=true
rpc-listen-all=true
rpc-listen-port=6800 #建议端口也改了
rpc-secret=passwd   #这里就是密码了
continue=true
input-file=/etc/aria2/aria2.session
save-session=/etc/aria2/aria2.session
max-concurrent-downloads=3

执行一下命令开启aria2c,如果没问题，后面加-D后台运行。

1
aria2c --conf-path=/etc/aria2/aria2.conf

web端建议用binux的yaaw
配置好之后需要有一个JSON-RPC Path,格式如下

1
http://token:passwd@ip:6800/jsonrpc

这样就配置好了

append:
openvz上面的debian 7 apt-get 的版本太低了。需要自己手动编译安装
可以用下面的地址下载源码

1
http://nchc.dl.sourceforge.net/project/aria2/stable/aria2-1.15.2/aria2-1.15.2.tar.gz

第一版支持加密的版本。
是以用户名，密码加密的。

1
2
rpc-user=username
rpc-passwd=passwd

JSON-RPC Path为：

1
http://username:passwd@ip:6800/jsonrpc

Mess

nginx 文件服务器

局域网搭建本地文件服务器
chrome最近不知道怎么回事，打开ftp网页就崩溃，也找不到相关资料
为了局域网更好传输文件，直接安装了nginx搭了一个文件服务器。

在nginx.conf适当的位置加入下面一段代码。然后就可以通过192.168.1.148:1688访问本地文件了。
视频文件还可以随意拖动哦~(不支持重型视频，比如mkv)

1
2
3
4
5
6
7
8
9
10
11
12
13
server {
    listen       1688;
    server_name  192.168.1.148;
 
        location / {
            charset utf-8,gbk;
            root   /data1;
            index  index.php index.html index.htm;
            autoindex on;
            autoindex_exact_size off;
            autoindex_localtime on;
        }
    }

location中设定字符集才能够正确显示中文。

再记录一下lighttpd当文件服务器

1
2
3
4
dir-listing.activate       = "enable"
dir-listing.encoding       = "utf8"
servers.modules +=( "mod_alias")
alias.url += ( "/file" => "/data" )

Mess

Linux sunpinyin用+ - 切换下一页

一直在windows下，因为要求用vs
今天偶尔切换到linux更新了下
发现sunpinyin 居然不能用 + 和 - 切换下一页
只能用pgdown 和 pgup ,真是反人类。
桌面那边调不出设置。只能够用终端调出设置面板

1
/usr/lib/ibus-sunpinyin/ibus-setup-sunpinyin