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
const double eps = 1e-5;
const double pi = acos(-1.0);

inline int dcmp(double x) {
// double大小比较,考虑精度eps
if (fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
inline int zero(double x) {
return fabs(x) < eps;
}

struct Point {
double x, y;
Point(double x = 0, double y = 0): x(x), y(y){}
};
typedef Point Vector;

Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); }
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }

bool operator == (const Point& a, const Point& b) {
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double length(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }
double distance(Point a, Point b) { return length(b - a); }
double angle(Vector a, Vector b) { return acos(dot(a, b) / length(a) / length(b)); }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double xmult(Point a, Point b, Point c) {
// 0 -> 三点共线
// + -> AC 在 AB 的逆时针方向
// - -> AC 在 AB 的顺时针方向
return cross(b - a, c - a);
}
double area2(Vector a, Vector b, Vector c) { return cross(b - a, c - a); }

Vector rotate(Vector a, double rad) {
return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}
Vector normal(Vector a) { // 计算单位法线,确保a不是零向量
double l = length(a); return Vector(-a.y / l, a.x / l);
}
Vector getNormal(Vector a) { return Vector(-a.y, a.x); }

// 直线表示: 已知直线上两个不同点A和B,则方向向量为(B-A),参数方程为 A + (B - A) t
// 直线 t 无限制,射线 t > 0,线段 t 在 0 到 1 之间
struct Line {
Point p; Vector v;
Line(Point a, Point b) : p(a), v(b - a) {}
};

Point getLineIntersection(Point p, Vector v, Point q, Vector w) {
// P + tv 和 Q + wv 有唯一交点,当且仅当 cross(v,w) != 0
Vector u = p - q;
double t = cross(w, u) / cross(v, w);
return p + v * t;
}
double getDistanceToLine(Point p, Point a, Point b) {
// P 到 AB 的距离
Vector v1 = b - a, v2 = p - a;
return fabs(cross(v1, v2)) / length(v1);
}
double getDistanceToSegment(Point p, Point a, Point b) {
// P 到线段 AB 的距离
if (a == b) return length(p - a);
Vector v1 = b - a, v2 = p - a, v3 = p - b;
if (dcmp(dot(v1, v2)) < 0) return length(v2);
else if (dcmp(dot(v1, v3)) > 0) return length(v3);
else return fabs(cross(v1, v2)) / length(v1);
}
Point getLineProjection(Point p, Point a, Point b) {
Vector v = b - a;
return a + v * (dot(v, p - a) / dot(v, v));
}
bool segmentProperIntersection(Point a1, Point b1, Point a2, Point b2) {
// 线段重合?
// 线段相交在端点?
// 不考虑上述两个case,线段A1B1,A2B2相交 -> 1
double c1 = cross(b1 - a1, a2 - a1), c2 = cross(b1 - a1, b2 - a1);
double c3 = cross(b2 - a2, a1 - a2), c4 = cross(b2 - a2, b1 - a2);
return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
bool onSegment(Point p, Point a1, Point a2) {
// 点是否在一条线段上(不包含端点)
return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
// p 是否在直线 a + v * t = 0 上
bool onLine(Point p, Vector v, Point a) {return dcmp(cross(v, p - a)) == 0;}
// 直线方向向量 v, P点到定点 A 的向量 t, 返回 P 点的参数 t
double getPosOnLine(Vector v, Vector t) {
if (dcmp(v.x) == 0) return t.y / v.y;
return t.x / v.x;
}

// 获取直线与圆的交点,直线 p + v * t = 0, 圆 (x - o.x) ^ 2 + (x - o.y) ^ 2 = r ^ 2
// 返回交点个数和点在直线上的参数 t1 和 t2
int getLineCircleIntersection(Point p, Vector v, Point o, double r, double &t1, double &t2) {
double a = v.x, b = p.x - o.x, c = v.y, d = p.y - o.y;
double e = a * a + c * c, f = 2 * (a * b + c * d), g = b * b + d * d - r * r;
double delta = f * f - 4 * e * g;
if (dcmp(delta) < 0)
return 0;
if (dcmp(delta) == 0){
t1 = t2 = -f / (2 * e);
return 1;
}
t1 = (-f - sqrt(delta)) / (2 * e);
t2 = (-f + sqrt(delta)) / (2 * e);
return 2;
}

double polygonArea(Point* p, int n) {
// 计算多边形的面积,顶点要按顺序
double area = 0;
for (int i = 1; i < n - 1; i++)
area += cross(p[i] - p[0], p[i + 1] - p[0]);
return area / 2;
}
阅读全文 »

树链剖分:树链更新和查询 + 子树更新和查询

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
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

int to[maxn << 1], nxt[maxn << 1], head[maxn], tot = 0;
void add(int x, int y){
to[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}

int n, m, a[maxn];

namespace hld{
ll wt[maxn], tree[maxn << 2], laz[maxn << 2];
void pushup(int rt){tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];}
void pushdown(int rt, int ln, int rn){
if (!laz[rt]) return;
tree[rt << 1] += 1ll * laz[rt] * ln; tree[rt << 1 | 1] += 1ll * laz[rt] * rn;
laz[rt << 1] += 1ll * laz[rt]; laz[rt << 1 | 1] += 1ll * laz[rt];
laz[rt] = 0;
}
void build(int l, int r, int rt){
if (l == r){
laz[rt] = 0; tree[rt] = wt[l];
return;
}
int m = (l + r) >> 1;
build(lson); build(rson);
pushup(rt);
}
void update(int i, int x, int l, int r, int rt){
if (l == r){
tree[rt] += 1ll * x;
return;
}
int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
if (i <= m) update(i, x, lson);
else update(i, x, rson);
pushup(rt);
}
void update(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
tree[rt] += 1ll * x * (r - l + 1); laz[rt] += 1ll * x;
return;
}
int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
if (L <= m) update(L, R, x, lson);
if (R > m) update(L, R, x, rson);
pushup(rt);
}
ll query(int L, int R, int l, int r, int rt){
if (L <= l && r <= R) return tree[rt];
int m = (l + r) >> 1; pushdown(rt, m - l + 1, r - m);
ll s = 0;
if (L <= m) s += query(L, R, lson);
if (R > m) s += query(L, R, rson);
return s;
}

int siz[maxn], dep[maxn], fa[maxn], son[maxn], top[maxn], id[maxn], cnt = 0;
void dfs(int p, int d, int old){
dep[p] = d; fa[p] = old; siz[p] = 1;
int m = -1;
for (int i = head[p]; i; i = nxt[i]){
int v = to[i];
if (v == fa[p]) continue;
dfs(v, d + 1, p);
siz[p] += siz[v];
if (siz[v] > m) son[p] = v, m = siz[v];
}
}
void dfs(int p, int tp){
id[p] = ++cnt; top[p] = tp; wt[cnt] = a[p];
if (!son[p]) return;
dfs(son[p], tp);
for (int i = head[p]; i; i = nxt[i]){
int v = to[i];
if (v == fa[p] || v == son[p]) continue;
dfs(v, v);
}
}
void init(){
cnt = 0; dfs(1, 1, 0); dfs(1, 1); build(1, n, 1);
}

int qpath(int x, int y){
int ans = 0;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ans = (ans + query(id[top[x]], id[x], 1, n, 1)) % p;
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ans = (ans + query(id[x], id[y], 1, n, 1)) % p;
return ans;
}
int qson(int x){
return query(id[x], id[x] + siz[x] - 1, 1, n, 1);
}
void upath(int x, int y, int k){
k %= p;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]]) swap(x, y);
update(id[top[x]], id[x], k, 1, n, 1);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
update(id[x], id[y], k, 1, n, 1);
}
void uson(int x, int k){
update(id[x], id[x] + siz[x] - 1, k % p, 1, n, 1);
}
}

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
#include <cstdio>
#include <algorithm>
const int maxn = 100000 + 5;
const int inf = 1 << 30;

int a[maxn];
struct Splay{
int f[maxn], ch[maxn][2], size[maxn], rev[maxn] = {0}, key[maxn], root, sz;
Splay(){
root = sz = size[0] = rev[0] = f[0] = 0; key[0] = inf;
}
int get(int x){return ch[f[x]][1] == x;}
void pushup(int x){
size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
}
void pushdown(int x){
if (!rev[x]) return;
std::swap(ch[x][0], ch[x][1]);
rev[ch[x][0]] ^= 1; rev[ch[x][1]] ^= 1; rev[x] = 0;
}
int build(int l, int r, int rt){
if (l > r) return 0;
int m = (l + r) >> 1, tot = ++sz;
key[tot] = a[m]; f[tot] = rt; rev[tot] = 0;
ch[tot][0] = build(l, m - 1, tot);
ch[tot][1] = build(m + 1, r, tot);
pushup(tot);
return tot;
}
void rot(int x){
int old = f[x], oldf = f[old], tp = get(x);
pushdown(old); pushdown(x);
ch[old][tp] = ch[x][tp ^ 1]; f[ch[old][tp]] = old;
ch[x][tp ^ 1] = old; f[old] = x;
f[x] = oldf;
if (oldf) ch[oldf][ch[oldf][1] == old] = x;
pushup(old); pushup(x);
}
void splay(int x, int tar){
for (int fa; (fa = f[x]) != tar; rot(x))
if (f[fa] != tar)
rot(get(fa) == get(x) ? fa : x);
if (!tar) root = x;
}
int find(int k){
int tot = root;
while (1){
pushdown(tot);
if (k <= size[ch[tot][0]]) tot = ch[tot][0];
else {
k -= size[ch[tot][0]] + 1;
if (!k) return tot;
tot = ch[tot][1];
}
}
}
void reverse(int l, int r){
int a = find(l), b = find(r + 2);
splay(a, 0); splay(b, a);
rev[ch[b][0]] ^= 1;
}
void print(int p){
pushdown(p);
if (ch[p][0]) print(ch[p][0]);
if (key[p] != inf) printf("%d ", key[p]);
if (ch[p][1]) print(ch[p][1]);
}
}f;

int n, m;

int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) a[i + 1] = i;
a[1] = inf; a[n + 2] = inf;
f.root = f.build(1, n + 2, 0);
while (m--){
int l, r; scanf("%d%d", &l, &r);
f.reverse(l, r);
}
f.print(f.root);
return 0;
}

cnt[x] 表示 x 的出现次数,size[x] 表示以 x 为根节点的子树大小。

  • clean(int x)

  • 清除当前节点

  • get(int x)

  • 获取当前节点是父节点的左右孩子

  • update(int x)

  • 更新当前节点的 size

  • rot(int x)

  • 将当前节点向上旋转

  • splay(int x)

  • 将当前节点伸展为根节点

  • insert(int v)

  • 创建一个新的节点,并将其旋转至根

  • find(int v)

  • 返回键为 v 的节点的名次,并将其旋转至根节点

  • findx(int x)

  • 返回排名为 x 的键

  • prev()

  • 返回根节点的前驱

  • succ()

  • 返回根节点的后继

  • del(int v)

  • 删除一个键为 v 的节点

模板:

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
struct Splay{
int f[maxn], ch[maxn][2], key[maxn], cnt[maxn], size[maxn], sz = 0, root = 0;
Splay(){sz = root = 0;}
void clear(int x){
ch[x][0] = ch[x][1] = f[x] = key[x] = cnt[x] = size[x] = 0;
}
int get(int x){
return ch[f[x]][1] == x;
}
void update(int x){
if (!x) return;
size[x] = cnt[x];
if (ch[x][0]) size[x] += size[ch[x][0]];
if (ch[x][1]) size[x] += size[ch[x][1]];
}
void rot(int x){
int old = f[x], oldf = f[old], tp = get(x);
ch[old][tp] = ch[x][tp ^ 1]; f[ch[old][tp]] = old;
f[old] = x; ch[x][tp ^ 1] = old;
f[x] = oldf;
if (oldf) ch[oldf][ch[oldf][1] == old] = x;
update(old); update(x);
}
void splay(int x){
for (int fa; fa = f[x]; rot(x))
if (f[fa]) rot(get(x) == get(fa) ? fa : x);
root = x;
}
int insert(int v){
if (root == 0){
sz++; ch[sz][0] = ch[sz][1] = f[sz] = 0;
key[sz] = v; cnt[sz] = 1; size[sz] = 1;
root = sz;
return 1;
}
int tot = root, fa = 0;
while (1){
if (key[tot] == v){
cnt[tot]++; update(tot); update(fa);
splay(tot);
return cnt[tot];
}
fa = tot;
tot = ch[tot][v > key[tot]];
if (tot == 0){
sz++; ch[sz][0] = ch[sz][1] = 0;
key[sz] = v; cnt[sz] = size[sz] = 1;
f[sz] = fa; ch[fa][v > key[fa]] = sz;
update(fa); splay(sz);
break;
}
}
return 1;
}
int find(int v){
int ans = 0, tot = root;
while (1){
if (v < key[tot]) tot = ch[tot][0];
else {
ans += (ch[tot][0] ? size[ch[tot][0]] : 0);
if (v == key[tot]){
splay(tot); return ans + 1;
}
ans += cnt[tot];
tot = ch[tot][1];
}
}
return 0;
}
int findx(int x){
int tot = root;
while (1){
if (ch[tot][0] && x <= size[ch[tot][0]]) tot = ch[tot][0];
else {
int t = (ch[tot][0] ? size[ch[tot][0]] : 0) + cnt[tot];
if (x <= t) return key[tot];
x -= t; tot = ch[tot][1];
}
}
return -1;
}
int prev(){
int tot = ch[root][0];
while (ch[tot][1]) tot = ch[tot][1];
return tot;
}
int succ(){
int tot = ch[root][1];
while (ch[tot][0]) tot = ch[tot][0];
return tot;
}
void del(int v){
find(v);
if (cnt[root] > 1){
cnt[root]--; return;
}
if (!ch[root][0] && !ch[root][1]){
clean(root); root = 0; return;
}
if (!ch[root][0]){
int old = root; root = ch[root][1]; f[root] = 0;
clean(old); return;
}
else if (!ch[root][1]){
int old = root; root = ch[root][0]; f[root] = 0;
clean(old); return;
}
int lf = prev(), old = root;
splay(lf); f[ch[old][1]] = root; ch[root][1] = ch[old][1];
clean(old); update(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
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 100000 + 5;

// sum 节点, add 懒惰, a 原数组
int sum[maxn << 2], add[maxn << 2], a[maxn], n;
void pushup(int rt){sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
void pushdown(int rt, int ln, int rn){
if (add[rt]){
add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt];
sum[rt << 1] = add[rt] * ln; sum[rt << 1 | 1] = add[rt] * rn;
add[rt] = 0;
}
}
void build(int l, int r, int rt){
if (l == r){
sum[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(lson); build(rson);
pushup(rt);
}
void update(int i, int x, int l, int r, int rt){
if (l == r){
sum[rt] += x;
return;
}
int m = (l + r) >> 1;
if (i <= m) update(i, x, lson);
else update(i, x, rson);
pushup(rt);
}
void update(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
sum[rt] += x * (r - l + 1);
add[rt] += x;
return;
}
int m = (l + r) >> 1;
pushdown(rt, m - l + 1, r - m);
if (L <= m) update(L, R, x, lson);
if (R > m) update(L, R, x, rson);
pushup(rt);
}
int query(int i, int l, int r, int rt){
if (l == r){
return sum[rt];
}
int m = (l + r) >> 1;
if (i <= l) return query(i, lson);
return query(i, rson);
}
int query(int L, int R, int l, int r, int rt){
if (L <= l && r <= R){
return sum[rt];
}
int m = (l + r) >> 1;
pushdown(rt, m - l + 1, r - m);
int ans = 0;
if (L <= m) ans += query(L, R, lson);
if (R > m) ans += query(L, R, rson);
return ans;
}

区间加乘双标记

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
int n, m, p;
ll a[maxn], sum[maxn << 2], add[maxn << 2], mul[maxn << 2];

void pushup(int rt){ sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % p; }
void pushdown(int rt, int ln, int rn){
int ls = rt << 1, rs = rt << 1 | 1;
if (mul[rt] != 1){
mul[ls] *= mul[rt]; mul[rs] *= mul[rt];
add[ls] *= mul[rt]; add[rs] *= mul[rt];
sum[ls] *= mul[rt]; sum[rs] *= mul[rt];
mul[rt] = 1;
}
if (add[rt] != 0){
add[ls] += add[rt]; add[rs] += add[rt];
sum[ls] += add[rt] * ln; sum[rs] += add[rt] * rn;
add[rt] = 0;
}
}
void build(int l, int r, int rt){
mul[rt] = 1;
if (l == r){
sum[rt] = a[l] % p; return;
}
int m = l + r >> 1;
build(lson); build(rson);
pushup(rt);
}
void update1(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
sum[rt] *= x;
mul[rt] *= x;
add[rt] *= x;
return;
}
int m = l + r >> 1; pushdown(rt, m - l + 1, r - m);
if (L <= m) update1(L, R, x, lson);
if (R > m) update1(L, R, x, rson);
pushup(rt);
}
void update2(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
sum[rt] += x * (r - l + 1);
add[rt] += x;
return;
}
int m = l + r >> 1; pushdown(rt, m - l + 1, r - m);
if (L <= m) update2(L, R, x, lson);
if (R > m) update2(L, R, x, rson);
pushup(rt);
}

区间取模

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
int n, m, a[maxn], mx[maxn << 2];;
ll sum[maxn << 2];

void pushup(int rt){
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}
void build(int l, int r, int rt){
if (l == r) {
sum[rt] = mx[rt] = a[l]; return;
}
int m = l + r >> 1;
build(lson); build(rson);
pushup(rt);
}
void update(int i, int x, int l, int r, int rt){
if (l == r){
sum[rt] = mx[rt] = x; return;
}
int m = l + r >> 1;
if (i <= m) update(i, x, lson);
else update(i, x, rson);
pushup(rt);
}
void update(int L, int R, int mod, int l, int r, int rt){
if (L > r || l > R || mx[rt] < mod) return;
if (L <= l && r <= R && l == r){
sum[rt] = mx[rt] = mx[rt] % mod;
return;
}
int m = l + r >> 1;
update(L, R, mod, lson); update(L, R, mod, rson);
pushup(rt);
}