# 作死变码风

#### if

if (condition) {
....
} else if (condition) {
...
} else {
...
}

if (condition) return 0;


1.if 和左圆括号间都有个空格. 右圆括号和左大括号之间也要有个空格
2.如果能增强可读性, 简短的条件语句允许写在同一行. 只有当语句简单并且没有使用 else 子句时使用
3.如果语句中某个 if-else 分支使用了大括号的话, 其它分支也必须使用apple的bug

#### for/while

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
...
}
}

for (; pos <= n && test > p; pos += test, ++test) {}

while (condition) continue;


#### fhqtreap

#include <cstdio>
#include <cstdlib>
using namespace std;
{
int x=0, f=1;char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f=-1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0';ch = getchar(); }
return x * f;
}
const int N = 500010;
int ch[N][2], val[N], pri[N], siz[N], sz;
void update(int x) { siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]]; }
int new_node(int v) {
siz[++sz] = 1;
val[sz] = v;
pri[sz] = rand();
return sz;
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (pri[x] < pri[y]) {
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void split(int now, int k, int &x, int &y) {
if (!now) x = y = 0;
else {
if (val[now] <= k)
x = now, split(ch[now][1], k, ch[now][1], y);
else
y = now, split(ch[now][0], k, x, ch[now][0]);
update(now);
}
}
int kth(int now, int k) {
while (1) {
if (k <= siz[ch[now][0]])
now = ch[now][0];
else if (k == siz[ch[now][0]] + 1)
return now;
else
k -= siz[ch[now][0]] + 1, now=ch[now][1];
}
}
main() {
srand(2001331);
int T, com, x, y, z, a, b, root=0;
while (T--) {
if (com == 1) {
split(root, a, x, y);
root = merge(merge(x, new_node(a)), y);
} else if (com == 2) {
split(root, a, x, z);
split(x, a-1, x, y);
y = merge(ch[y][0], ch[y][1]);
root = merge(merge(x, y), z);
} else if (com == 3) {
split(root, a-1, x, y);
printf("%d\n", siz[x] + 1);
root = merge(x, y);
} else if (com == 4) {
printf("%d\n", val[kth(root, a)]);
} else if (com == 5) {
split(root, a-1, x, y);
printf("%d\n", val[kth(x, siz[x])]);
root = merge(x, y);
} else if (com == 6) {
split(root, a, x, y);
printf("%d\n", val[kth(y, 1)]);
root = merge(x, y);
}
}
}


#### 链剖lca

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
struct edge {
int to,next;
}e[N<<1];
int st[N], siz[N], top[N], son[N], fa[N], deep[N];
int tot, n, m, x, y, root;
void add(int x, int y) {
e[++tot].next = st[x];
e[tot].to = y, st[x] = tot;
}
void dfs1(int now) {
siz[now] = 1;
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now]) {
fa[e[i].to] = now;
deep[e[i].to] = deep[now] + 1;
dfs1(e[i].to);
siz[now] += siz[e[i].to];
if (siz[son[now]] < siz[e[i].to])
son[now] = e[i].to;
}
}
void dfs2(int now, int tp) {
top[now] = tp;
if (son[now])
dfs2(son[now], tp);
for (int i = st[now]; i; i = e[i].next)
if (e[i].to != fa[now] && e[i].to != son[now])
dfs2(e[i].to, e[i].to);
}
int lca(int x, int y) {
while (top[x] != top[y]) deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
return deep[x] > deep[y] ? y : x;
}
main() {
scanf("%d%d%d", &n, &m, &root);
for (int i = 1; i < n; ++i)
scanf("%d%d", &x, &y),
dfs1(root);
dfs2(root,root);
for (int i = 1; i <= m; ++i)
scanf("%d%d", &x, &y),
printf("%d\n", lca(x,y));
}


#### lct（luogu模版）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 300010;
int n, m, x, y, f[N], ch[N][2], res[N], val[N], siz[N];
map<int,int>ma;
void update(int x) {
if (ch[x][0] && ch[x][1])
siz[x] = siz[ch[x][0]] ^ siz[ch[x][1]], siz[x] ^= val[x];
else if (ch[x][0])
siz[x] = siz[ch[x][0]] ^ val[x];
else if (ch[x][1])
siz[x] = siz[ch[x][1]] ^ val[x];
else
siz[x] = val[x];
}
void pushdown(int x) {
if (res[x] && x) {
if (ch[x][0]) res[ch[x][0]] ^= 1;
if (ch[x][1]) res[ch[x][1]] ^= 1;
swap(ch[x][0], ch[x][1]);
res[x]=0;
}
}
int is_root(int x) { return ch[f[x]][1] != x && ch[f[x]][0] != x; }
int get_son(int x) { return ch[f[x]][1] == x; }
void rot(int x) {
int fa = f[x], fafa = f[fa], k = get_son(x);
if (!is_root(fa))
ch[fafa][ch[fafa][1] == fa] = x;
ch[fa][k] = ch[x][k ^ 1], f[ch[fa][k]] = fa;
ch[x][k ^ 1] = fa, f[fa] = x, f[x] = fafa;
update(fa), update(x);
}
void pushs(int x) {
if (!is_root(x)) pushs(f[x]);
pushdown(x);
}
void splay(int x) {
pushs(x);
for (int fa; !is_root(x); rot(x))
if (!is_root(fa = f[x]))
rot(get_son(x) == get_son(fa) ? fa : x);
}
void access(int x) {
for (int y = 0; x; y = x, x = f[x])
splay(x), ch[x][1] = y, update(x);
}
int find_rt(int x) {
access(x), splay(x);
while (ch[x][0]) x = ch[x][0];
return x;
}
void make_root(int x) {
access(x), splay(x);
res[x] ^= 1;
}
void link(int x, int y) {
make_root(x);
f[x] = y;
splay(x);
}
void cut(int x, int y) {
make_root(x), access(y), splay(y);
ch[y][0] = f[x] = 0;
}
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &val[i]), siz[i] = val[i];
for (int i = 1; i <= m; ++i) {
int com, x, y;
scanf("%d%d%d", &com, &x, &y);
if (com == 0) {
make_root(x);
access(y);
splay(y);
printf("%d\n", siz[y]);
} else if (com == 1) {
if (find_rt(x) != find_rt(y)) {
if (ma[x] == 0)
ma[x] = y;
else
ma[y] = x;
}
} else if (com == 2) {
if (ma[x] == y) {
ma[x] = 0;
cut(x, y);
} else if (ma[y] == x) {
ma[y] = 0;
cut(x, y);
}
} else if (com==3) {
splay(x);
siz[x] ^= val[x];
val[x] = y;
siz[x] ^= y;
}
}
}


#### fft

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
const int N = 2000010;
int n, m, r[N];
struct complex {
double x, y;
complex (double xx = 0, double yy = 0) {
x = xx, y = yy;
}
}a[N], b[N], o[N], a_o[N];
complex operator + (complex a,complex b) { return complex(a.x + b.x, a.y + b.y); }
complex operator - (complex a,complex b) { return complex(a.x - b.x, a.y - b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }
void init(int n) {
double t = 2 * pi / n;
for (int i = 0; i <= n; ++i) {
o[i] = complex(cos(2.0 * pi * i / n), sin(2.0 * pi * i / n));
a_o[i] = complex(cos(2.0 * pi * i / n),-1 * sin(2.0 * pi * i / n));
}
}
void fft(int n, complex *a, complex *w)
{
for (int i = 0; i < n; ++i)
if (i < r[i])
swap(a[i], a[r[i]]);
for (int i = 2; i <= n; i <<= 1) {
int m = i >> 1;
for (int j = 0; j < n;j += i)
for (int k = 0; k < m; ++k) {
complex t = a[j + m + k] * w[n / i * k];
a[j + m + k] = a[j + k] - t;
a[j + k] = a[j + k] + t;
}
}
}
main() {
static int n,m,fn,l=0;
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; ++i) scanf("%lf", &a[i].x);
for (int i = 0; i <= m; ++i) scanf("%lf", &b[i].x);
fn = 1;
while (fn <= n + m) fn <<= 1, ++l;
for (int i = 0; i < fn; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
init(fn);
fft(fn, a, o);
fft(fn, b, o);
for (int i = 0; i <= fn; ++i)
a[i] = a[i] * b[i];
fft(fn, a, a_o);
for (int i = 0;i <= n + m; ++i)
printf("%d ", (int)(a[i].x / fn + 0.5));
}