Mess

让nginx和lighttpd支持播放mkv

看到了一个帖子，说lighttpd可以直接播放mkv，而nginx不行。有点奇怪，所以尝试了一下lighttpd，发现点击mkv文件还是显示下载，不能和mp4一样直接播放，但是chrome是支持mkv播放的，本地同样的文件拖入chrome是可以完美播放的。

后来去找了一下相关的原因，在stackoverflow上面发现mkv是下载还是直接播放取决于mime类型，mime类型如果是video/webm的是可以直接播放的

所以之后又尝试了一下在lighttpd和nginx指定mime类型映射列表

1
2
3
4
5
6
7
8
9
10
11
12
13
#lighttpd.conf
mimetype.assign = (
".mkv" => "video/wem")
#顺便记录一下alias,把/data1映射到xxx.com/file
servers.modules +=( "mod_alias")
alias.url += ( "/file" => "/data1" )
#nginx.conf
#在server > location块内加入
types{
    video/webm  mkv;
}

这样的话点击mkv文件会直接播放而不是下载。
但是chrome的文件类型支持有限，所以有些本地不能播放的网络上肯定是更加不可能的了。

Stackoverflow上的相关问题

Mess

rails 安装

gem install rails
安装需要花点时间，最好显示一下进度
gem install rails -V

安装中报错：

1
ERROR: Failed to build gem native extension.

要安装一个ruby-dev

1
sudo apt-get install ruby1.9.1-dev

ubuntu 上面安装可能会出现cannot find lib文件夹
需要在gems的ruby目录下建立一个ruby文件夹

Notes

ssh框架action中成员变量的命名

今天遇到了一个特别坑的地方。
我在action里面写一个变量叫gId,然后jsp上写上xxx.action?gId=1
然后到action函数里面竟然打不出gId的值。。set和get方法都写了。。
网上找不到一个答案。。
后来看了一下那个myeclipse自动生成的set和get方法叫setgId,getgId
看起来不太顺眼。。
然后把那个gId该名成了gid,自己写了setGid和getGid，这样才能获取到值。。
myeclipse真是好不靠谱啊。。
还有生成hiberate的xml文件都会少一个空格的，实在是醉了。。

java变量的命名规则如下：

1
变量的名字可大小写混用，但首字符应小写。词由大写字母分隔，限制用下划线

按照道理说gId这样命名应该没问题的吧？
看样子之后写成员变量要全小写了。

Mess

redsocks & iptables

redsocks 不说明

iptables配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//创建一条链
iptables -t nat -N REDSOCKS
//local
iptables -t nat -A REDSOCKS -d 0.0.0.0/8 -j RETURN 
iptables -t nat -A REDSOCKS -d 10.0.0.0/8 -j RETURN 
iptables -t nat -A REDSOCKS -d 127.0.0.0/8 -j RETURN 
iptables -t nat -A REDSOCKS -d 169.254.0.0/16 -j RETURN 
iptables -t nat -A REDSOCKS -d 172.16.0.0/12 -j RETURN 
iptables -t nat -A REDSOCKS -d 192.168.0.0/16 -j RETURN 
iptables -t nat -A REDSOCKS -d 224.0.0.0/4 -j RETURN 
iptables -t nat -A REDSOCKS -d 240.0.0.0/4 -j RETURN
//other
iptables -t nat -A REDSOCKS -p tcp -j REDIRECT --to 12345 
iptables -t nat -A OUTPUT -p tcp -j REDSOCKS
iptables -t nat -I REDSOCKS -d my-server-ip -j RETURN
//局域网
iptables -t nat -A PREROUTING -p tcp -j REDSOCKS

Mess

Mess

mysql数据库导出

1
mysqldump -u root -p maimaimai > maimaimai.sql

myeclipse出现未知问题

1
2
3
删除 
/.metadata/.plugins/org.eclipse.core.runtime/.settings/com.
genuitec.eclipse.ast.deploy.core.pre

手动开栈：

1
#pragma comment(linker, "/STACK:1024000000,1024000000")

java web 错误：No result defined for action xxx and result input
可能是因为select 有误，struct 拦截器会跳转到 “input”

myeclipse 更改主题

hexo markdown语法

markdown plus

ss-redir 配置

Mess

在满足时间复杂度下，代码果然还是越简单越好

今天写了个判断一个数的k次方是否超过另个数
然后当时想都没想就用了快速幂
(其中那个数的k次方可能超过long long)

第一个版本：判断x ^ n 是否大于m

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

下面这样是错的。。因为数据一大x超过long long 变成0，res也从1变成了0.
例子是：1000 536870912 1000

试了试加了个条件。x > m跳出。

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m || x>=m) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

发现还是错了，看这组数据：3 2 1

还需要再加个条件。。n>0.因为可能n已经为0了但是x大于了m.

1
2
3
4
5
6
7
8
9
10
11
bool pow(ll x,ll n,ll m){  
    ll res = 1;  
    while(n > 0){  
        if(n & 1) res = res * x;  
        x = x*x;  
        n>>=1;  
        if(res >= m || (n > 0 && x >= m)) return true;  
    }  
    if(res >= m) return true;  
    else return false;  
}

其实这个东西不写快速幂就很快了，指数函数式爆炸上升的。。手残写了快速幂还错。。下次要牢记啊。

Algorithm

并查集

并查集是一个树形的数据结构，能够实现快速查询两个数是否属于同一个集合。

并查集虽说是树形的结构，但是一个节点只记录了父亲，不记录子节点，因为记录子节点完全没有必要。

怎么标记两个节点属于一个集合？比如两个节点是a和b，则只需要fa(a) = fa(b),fa(a)是a最原始的祖先。这样的话两棵树就连在了一起。要查询两个节点是否在同一个集合，只需要分别计算fa(a)和fa(b)，只要两者一样就代表他们在同一颗树，也就是属于同一个集合。

当然，并查集只能只有上述两个操作，不能够修改节点集合之间的关系，也不能嵌套之类的。如果真的要实现这些复杂的操作，那么只能够求靠动态树了。

并查集一个操作的复杂度在于找父亲，可以每次merge的时候让这棵树平衡一点加快并查集的查询速度。

并查集的一个应用就是求最小生成树的kruskal算法。每次选择最短的边，把两个相连的点标记为在同一个集合，知道所有点都加入集合，就得到最小生成树了。

下面是并查集一个实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/***********************************************\
 |Author: YMC
 |Created Time: 2015/3/26 22:17:52
 |File Name: a.cpp
 |Description: 
\***********************************************/
int n,m;
int father[5000];
void init(int n) {
    srep(i,n) father[i] = i;
}
int find(int v) {
    return father[v] = father[v] == v ? v : find(father[v]);    //可降低并查集高度
}
bool merge(int a,int b) {
    int x = find(a);
    int y = find(b);
    if(x == y) return false;
    father[x] = y;
    return true;
}

Algorithm

splay

splay 是一种很灵活的数据结构。它是动态树的基础，动态树是维护树上数据的神器啊~

splay是一种特殊的二叉查找树，与平衡树不同，不是按照判断高度来降低深度的。
每次插入一个点，或者每次处理一个点，都需要进行一次splay操作把该点移动到根，根据数据的局部性原理，可以使处理变得快一点。

###它有以下规则：（p是x的parent节点）
zig

  • 当p为根节点时，进行zip step操作。
  • 当x是p的左孩子时，对x右旋；
  • 当x是p的右孩子时，对x左旋。

zig-zig

  • 当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。
  • 当p为左孩子，x为右孩子时，将x左旋后再右旋。
  • 当p为右孩子，x为左孩子时，将x右旋后再左旋。

zig-zag

  • 当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。
  • 当p为左孩子，x为右孩子时，将x左旋后再右旋。
  • 当p为右孩子，x为左孩子时，将x右旋后再左旋。

splay可以替代线段树进行更加复杂的区间操作，但是一般如果不是线段树解决不了的问题，尽量不能用splay做，因为splay常数比线段树大很多。

splay的维护懒惰标记也很巧妙，每次旋转的时候先把标记下降，然后旋转，旋转之后只有该节点原来的父亲的数据会发生变化，需要pushup一下，当前节点的数据可以等位置固定了之后再维护。

如果要计算一段区间内的值，可以先把该段位置的前一个节点splay到根，然后把该段位置的后一个节点splay到root,这样的话，后一个的节点的左子树就是该段区间所维护的值了。

下面是一个实现：

题目链接

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
/***********************************************\
 |Author: YMC
 |Created Time: 2015/3/25 21:34:19
 |File Name: hdu1166.cpp
 |Description: 
\***********************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#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(int 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;
#define maxn 110000
struct Node {
    int val;
    int sum;
    int add;
    Node* ch[2], *f;
    int size;
    void init() {
        f = ch[0] = ch[1] = NULL; size = 1;
        add = 0;    //延迟标记
    }
    void rot(int c) {
        Node *y = f, *z = y->f;
        //y->push_down(); push_down();
        y->ch[!c] = ch[c];  if(ch[c]) ch[c]->f = y;
        f = z;
        if(z) {
            if(y == z->ch[0])   z->ch[0] = this;
            else z->ch[1] = this;
        }
        ch[c] = y;  y->f = this;
        y->update();    //自己暂时不更新,y是原来的fa,在自己下面
    }
    void splay(Node *fa) {
        for(pushdown(); f != fa; ) {    //每次自己要旋转,则需要把标记传递下去,子标记不受影响。
            if(f->f == fa) {
                if(f->ch[0] == this) rot(1);
                else rot(0);
            } else {
                Node *y = f, *z = y->f;
                if(y->ch[0] == this) {
                    if(z->ch[0] == y) {
                        y->rot(1); rot(1);
                    } else {
                        rot(1); rot(0);
                    }
                } else {
                    if(z->ch[0] != y) {
                        y->rot(0); rot(0);
                    } else {
                        rot(0); rot(1);
                    }
                }
            }
        }
        update();   //本节点最后更新
    }
    void pushdown() {
        if(add) {
            if(ch[0]) {
                ch[0]->add += add;
                ch[0]->val += add;
                ch[0]->sum += ch[0]->size * add;
            }
            if(ch[1]) {
                ch[1]->add += add;
                ch[1]->val += add;
                ch[1]->sum += ch[1]->size * add;
            }
            add = 0;
        }
    }
    void update() {
        size = 1;
        if(ch[0]) size += ch[0]->size;
        if(ch[1]) size += ch[1]->size;
        sum = val;
        if(ch[0]) sum += ch[0]->sum;
        if(ch[1]) sum += ch[1]->sum;
    }
    Node* find(int r) {
        pushdown();     //找的时候要维护一些信息。不然找到的节点的信息错误
        int L = 0; if(ch[0]) L += ch[0]->size;
        if(r <= L) return ch[0]->find(r);
        if(r == L+1) return this;
        return ch[1]->find(r-L-1);
    }
}node[maxn];
int e;
inline Node* _alloc() {
    node[e].init(); return &node[e++];
}
int da[maxn];
Node* _make(int l, int r) {
    if(l > r) return NULL;
    int mid = l + r >> 1;   //从中间开始建，树的深度最小
    Node *p = _alloc(); p->val = da[mid];
    p->ch[0] = _make(l, mid-1); if(p->ch[0]) p->ch[0]->f = p;
    p->ch[1] = _make(mid+1, r); if(p->ch[1]) p->ch[1]->f = p;
    p->update();    //子节点更新好之后再更新自己。
    return p;
}
char op[10];
int a, b, c, n;
int main() {
	//freopen("input.txt","r",stdin); 
    int T;
    scanf("%d",&T);
    int cas = 0;
    while(T--) {
        printf("Case %d:\n", ++cas);
        scanf("%d",&n);
        srep(i,n) scanf("%d",&da[i]);
        da[0] = da[n+1] = 0;
        e = 0;
        Node *root = _make(0, n+1), *tp;
        while(scanf("%s",op) != EOF) {
            if(op[0] == 'Q') {
                scanf("%d %d",&a,&b); a++; b++;
                tp = root->find(a - 1);
                tp->splay(NULL); root = tp;
                tp = root->find(b + 1);
                tp->splay(root);
                tp = tp->ch[0];
                printf("%d\n",tp->sum);
            } else if(op[0] == 'A') {
                scanf("%d %d",&a,&b); a++;
                tp = root->find(a-1);
                tp->splay(NULL);    root = tp;
                tp = root->find(a+1);
                tp->splay(root);
                tp = tp->ch[0];
                tp->sum += b;
            } else if(op[0] == 'S') {
                scanf("%d %d",&a,&b); a++;
                tp = root->find(a-1);
                tp->splay(NULL);    root = tp;
                tp = root->find(a+1);
                tp->splay(root);
                tp = tp->ch[0];
                tp->sum -= b;
            } else break;
        }
    }
	return 0;
}
Algorithm

树链剖分

线段树是一种非常常用的数据结构，能够在log的时间内对数组进行区间修改，区间合并等操作。它的局限性也很明显，如果操作不是在数组上，而是在一颗树上，那么线段树将无能为力。

树链剖分为线段树的这个缺点提供的有效的解决方法，即把树转化为链。尽可能把树上的操作转化为链的操作。

如下图所示，粗的线条就是重链，细的是轻链，标号是其在线段树中的位置
树链剖分

树链剖分把一棵树标号，把树上的链分为重链和轻链两种。重链就是父亲到最重的儿子上的一条边。且转化出来的相连的重链标号连续。所有链的编号不同。我们知道，树上的每两个点之间的路径都是唯一的。标号之后，树上每两点的路径是由重链和轻链交替连接的，重链会尽量的长（这就是剖分轻重链的优点）。

因为重链比较长，所以树上两个点的路径轻重链的条数会很少，而因为重链标号是连续的，所以可以把链上的数据维护在线段树中，lg(n)复杂度时间内就能够完成一条重链的操作。效果非常不错。

下面是一个例子的实现：

题目链接

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
186
187
188
189
190
191
192
/***********************************************\
 |Author: YMC
 |Created Time: 2014/9/22 21:23:55
 |File Name: hdu 5029 self.cpp
 |Description: 
\***********************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#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(int 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;
#define maxn 100010
vector <int> ma[maxn];
int pathid[maxn],pathtop[maxn],dep[maxn];
int que[maxn],s,t,fa[maxn],size[maxn],son[maxn],tot;
int fq[maxn];
ll an[maxn],bn[maxn];
int n,m,u,v,cnt;
int tp;
inline void add_edge(int a,int b){
    ma[a].push_back(b);ma[b].push_back(a);
}
//树链剖分
void buildpath() {
    int u,v;
    s = 0;t = 0;
    que[t ++] = 1;          //注意修改起点
    fa[1] = -1;dep[1] = 1;
    while(s < t) {
        u = que[s ++];
        rep(i,ma[u].size()) {
            v = ma[u][i];
            if(v != fa[u]) {
                fa[v] = u; dep[v] = dep[u] + 1; que[t ++] = v;
            }
        }
    }
    for(int j = n-1;j >= 0;--j) {
        u = que[j];
        son[u] = -1; size[u] = 1;
        rep(i,ma[u].size()) {
            v = ma[u][i];
            if(v != fa[u]) {
                size[u] += size[v];
                if(son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
            }
        }
        if(son[u] == -1) son[u] = u;
    }
    memset(pathtop,-1,sizeof(pathtop));
    cnt = 1;
    for(int i = 0;i<n;++i) {
        u = que[i];
        if(pathtop[u] != -1) continue;
        int top = u;
        for(;;) {
            pathtop[u] = top;
            pathid[u] = cnt ++;
            fq[pathid[u]] = u;
            if(son[u] == u) break;
            u = son[u];
        }
    }
}
void init(int n){ 
    rep(i,n+2){
        ma[i].clear();
    }
    memset(an,0,sizeof(an));
    memset(bn,0,sizeof(bn));
}
void change1(int u,int v,int z) {
    int f1 = pathtop[u],f2 = pathtop[v];
    while(f1 != f2) {
        if(dep[f1] < dep[f2]) { //始终让f1在下面
            swap(f1,f2);
            swap(u,v);
        }
        an[pathid[f1]] += z;
        an[pathid[u] + 1] -= z;
        u = fa[f1];
        f1 = pathtop[u];
    }
    if(dep[u] > dep[v]) swap(u,v);
    an[pathid[u]] += z;
    an[pathid[v] + 1] -= z;
}
void change2(int u,int v,ll z) {
    //if(u == v) return;
    int f1 = pathtop[u],f2 = pathtop[v];
    while(f1 != f2) {
        if(dep[f1] < dep[f2]) { //始终让f1在下面
            swap(f1,f2);
            swap(u,v);
        }
        bn[pathid[f1]] += z;
        bn[pathid[u] + 1] -= z;
        u = fa[f1];
        f1 = pathtop[u];
    }
    if(u == v) return ;
    if(dep[u] > dep[v]) swap(u,v);
    bn[pathid[son[u]]] += z;
    bn[pathid[v]+1] -= z;
}
char ch[20];
ll ans[maxn];
ll ans1[maxn];
pair<int,int> pa[maxn];
int main() {
    //freopen("input.txt","r",stdin); 
    int T;
    scanf("%d",&T);
    int cas = 1;
    while(T--) {
        scanf("%d %d",&n,&m);
        init(n);
        rep(i,n-1) {
            scanf("%d %d",&u,&v);
            add_edge(u,v);
            pa[i] = make_pair(u,v);
        }
        buildpath();        //剖分
        rep(i,n-1){
            if(dep[pa[i].first] < dep[pa[i].second]) {
                swap(pa[i].first,pa[i].second);
            }
        }
        rep(i,m){
            scanf("%s %d %d %d",ch,&u,&v,&tp);
            if(ch[3] == '1'){
                change1(u,v,tp);
            }
            else {
                change2(u,v,tp);
            }
        }
        printf("Case #%d:\n",cas ++);
        ll sum = 0;
        for(int i=1;i<=n;++i){
            sum += an[i];
            ans1[fq[i]] = sum;
        }
        for(int i=1;i<n;++i){
            printf("%I64d ",ans1[i]);
        }
        printf("%I64d\n",ans1[n]);
        if(n == 1){
            puts("");
            continue;
        }
        sum = 0;
        for(int i=2;i<=n;++i){
            sum += bn[i];
            ans[fq[i]] = sum;
        }
        rep(i,n-2){
            printf("%I64d ",ans[pa[i].first]);
        }
        printf("%I64d\n",ans[pa[n-2].first]);
    }
    return 0;
}