LINK Blog

——互联网里的一粒沙

发表于 更新于 本文字数： 13 阅读时长 ≈ 1 分钟

建站前期，内容正有序添加中

发表于 分类于 ， 本文字数： 399 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
auto dijkstra = [&](int s) {
  vector<i64> dis(n, 1e18);
  dis[s] = 0;
  priority_queue<pll, vector<pll>, greater<pll>> q;
  q.push({0, s});

  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();

    if (d != dis[u])
      continue;

    for (auto [v, w] : v[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
  return dis;
};

发表于 分类于 ， 本文字数： 153 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
// a * x + b * y = gcd(a, b) 的一组特解
pll exgcd(i64 a, i64 b) {
  if (!b)
    return {1, 0};
  pll res = exgcd(b, a % b);
  return {res.se, res.fi - a / b * res.se};
}

发表于 分类于 ， 本文字数： 458 阅读时长 ≈ 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
inline __int128 read(){
    __int128 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;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

发表于 分类于 ， 本文字数： 1.1k 阅读时长 ≈ 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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, k, T;
vector<int> g[N];
int fa[N][17], depth[N], lg[N];
void init() {
  for (int i = 1; i <= n; ++i)
    lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
void dfs(int cur, int father) {
  fa[cur][0] = father;
  depth[cur] = depth[father] + 1;
  for (int i = 1; i <= lg[depth[cur]]; ++i) {
    fa[cur][i] = fa[fa[cur][i - 1]][i - 1];
  }
  for (auto i : g[cur]) {
    if (i != father)
      dfs(i, cur);
  }
}
int LCA(int x, int y) {
  if (depth[x] < depth[y])
    swap(x, y);               // 不妨假设x深度更大
  while (depth[x] > depth[y]) // 跳到同一深度
  {
    x = fa[x][lg[depth[x] - depth[y]] - 1];
  }
  if (x == y)
    return x;
  for (int k = lg[depth[x]] - 1; k >= 0; --k) // 跳到LCA下边一层
  {
    if (fa[x][k] != fa[y][k]) {
      x = fa[x][k], y = fa[y][k];
    }
  }
  return fa[x][0];
}
int root;
int main() {
  cin >> n >> m >> root;
  init();
  n--;
  while (n--) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(root, 0);
  while (m--) {
    int x, y;
    cin >> x >> y;
    int tmp = LCA(x, y);
    cout << tmp << '\n';
  }
  return 0;
}

发表于 分类于 ， 本文字数： 332 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct LazySum {
	vector<int> ps;
	LazySum(int n) : ps(n, 0) {}

	//[l, r]
	void add(int l, int r, int val) {
		if (l > r) return;
		ps[l] += val;
		ps[r + 1] -= val;
	}
	void pushToAndClear(vector<int> &d) {
		int sum = 0;
		fore (i, 0, sz(ps)) {
			sum += ps[i];
			ps[i] = 0;
			if (i < sz(d))
				d[i] += sum;
		}
	}
};

发表于 分类于 ， 本文字数： 340 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto insert = [&](i64 x1, i64 y1, i64 x2, i64 y2, i64 c,
                  vector<vector<i64>> &b) {
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;
};

auto TD_prefix_and = [&](vector<vector<i64>> &b) {
  for (int i = 1; i < n; i++)
    for (int j = 1; j < n; j++)
      b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
};

发表于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 4 分钟 
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
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
#define int long long
#define pii pair<int, int>

const int N = 1e4 + 9;

int tot, ans, last;  // last上条底的长度
int X[N << 1];       // 所有横坐标  需离散化

struct node1  // 扫描线
{
    int x1, x2, y;
    int flag;
} line[N << 1];

struct node2  // 线段树
{
    int l, r;
    int lz, len;  // len当先扫描到的矩形的长
    int sum;      // 竖边个数
    bool lco, rco;
} t[N << 3];

bool cmp(node1 q, node1 w) {
    if (q.y == w.y)
        return q.flag > w.flag;
    return q.y < w.y;
}

void build(int u, int l, int r) {
    t[u] = {l, r};
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
}

void pushup(int u) {
    int l = t[u].l, r = t[u].r;
    if (t[u].lz) {
        t[u].len = X[r + 1] - X[l];
        t[u].lco = t[u].rco = 1;
        t[u].sum = 2;
    } else {
        t[u].len = t[u << 1].len + t[u << 1 | 1].len;
        t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
        t[u].lco = t[u << 1].lco, t[u].rco = t[u << 1 | 1].rco;
        if (t[u << 1].rco && t[u << 1 | 1].lco)
            t[u].sum -= 2;
    }
}

void modify(int u, int l, int r, int flag) {
    if (l <= t[u].l && t[u].r <= r) {
        t[u].lz += flag;
        pushup(u);
        return;
    }
    int mid = (t[u].l + t[u].r) >> 1;
    if (l <= mid)
        modify(u << 1, l, r, flag);
    if (r > mid)
        modify(u << 1 | 1, l, r, flag);
    pushup(u);
}

void solve() {
    memset(t, 0, sizeof(t));
    memset(X, 0, sizeof(X));
    memset(line, 0, sizeof(line));
    map<int, int> p, p1;  // 用来离散横坐标 建树空间不会炸
    last = tot = ans = 0;

    int n, x = 0, y = 0, xx, yy;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> xx >> yy;
        line[i] = {x, xx, y, 1};
        line[i + n] = {x, xx, yy, -1};
        X[i] = x, X[i + n] = xx;
        p1[x]++;
        p1[xx]++;
    }
    sort(line + 1, line + n * 2 + 1, cmp);  // 排序完就是从下往上扫
    // 去重 离散
    sort(X + 1, X + 2 * n + 1);
    unique(X + 1, X + 2 * n + 1);
    for (auto [i, j] : p1) {
        if (!p[i])
            p[i] = ++tot;
    }

    build(1, 1, tot - 1);

    for (int i = 1; i < 2 * n; i++) {
        int l = p[line[i].x1],
            r = p[line[i].x2];  // 用离散值查到当前扫描到的边的左右横坐标
        modify(1, l, r - 1, line[i].flag);
        ans = ans + abs(last - t[1].len);  // 横边
        last = t[1].len;
        ans =
            ans + t[1].sum * (line[i + 1].y - line[i].y);  // 竖边条数*竖边长度
    }
    ans = ans + line[n * 2].x2 - line[n * 2].x1;
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // init();
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

0%