【学习笔记】线段树分治

定义

线段树分治是一种解决一类有插入、删除和整体查询操作的问题的方法。它是一种离线做法，通过在线段树上记录操作的时间区间来处理修改对询问的影响。每个操作被看作一个时间区间的修改，并在线段树上进行标记。然后通过深度优先搜索（DFS）依次执行这些操作，直到根节点来回答查询，并在离开时将其撤销。

 题目

#121. 「离线可过」动态图连通性

  1 #include <bits/stdc++.h>
  2 #define fo(a,b,c) for(int a=b;a<=c;a++)
  3 #define re(a,b,c) for(int a=b;a>=c;a--)
  4 #define mod 1000000007
  5 #define inp 10000019
  6 using namespace std;
  7 const int N = 500005;
  8 
  9 inline int read() {
 10     int x = 0, f = 1;
 11     char ch = getchar();
 12 
 13     while (ch < '0' || ch > '9') {
 14         if (ch == '-')
 15             f = -1;
 16 
 17         ch = getchar();
 18     }
 19 
 20     while (ch >= '0' && ch <= '9') {
 21         x = (x << 1) + (x << 3) + (ch ^ 48);
 22         ch = getchar();
 23     }
 24 
 25     return x * f;
 26 }
 27 
 28 int nyn = 1;
 29 int n, e[5005][5005], cnt, st[N], en[N], fr[N], to[N], f[N];
 30 int op2l[N], op2r[N], sz[N], tot;
 31 
 32 struct sss {
 33     int x, y, szx, szy;
 34 } sta[N];
 35 
 36 int find(int x) {
 37     if (f[x] == x)
 38         return x;
 39 
 40     return find(f[x]);
 41 }
 42 
 43 void merge(int x, int y) {
 44     x = find(x);
 45     y = find(y);
 46 
 47     if (x == y)
 48         return;
 49 
 50     tot++;
 51 
 52     if (sz[x] > sz[y])
 53         swap(x, y);
 54 
 55     sta[tot].x = x;
 56     sta[tot].y = y;
 57     sta[tot].szx = sz[x];
 58     sta[tot].szy = sz[y];
 59     f[x] = y;
 60     sz[y] += sz[x];
 61 }
 62 
 63 void split(int k) {
 64     while (tot > k) {
 65         int x = sta[tot].x, y = sta[tot].y;
 66         int szx = sta[tot].szx;
 67         int szy = sta[tot].szy;
 68         f[x] = x;
 69         sz[x] = szx;
 70         sz[y] = szy;
 71         tot--;
 72     }
 73 }
 74 
 75 struct IO {
 76     vector<int> t;
 77 } node[N * 4];
 78 
 79 void ud(int rt, int l, int r, int L, int R, int val) {
 80     if (l > r)
 81         return;
 82 
 83     if (L <= l && r <= R) {
 84         node[rt].t.push_back(val);
 85         return;
 86     }
 87 
 88     int mid = (l + r) / 2;
 89 
 90     if (L <= mid)
 91         ud(rt * 2, l, mid, L, R, val);
 92 
 93     if (R >= mid + 1)
 94         ud(rt * 2 + 1, mid + 1, r, L, R, val);
 95 }
 96 
 97 void qr(int rt, int l, int r) {
 98     int num = tot;
 99 
100     for (int i = 0; i < node[rt].t.size(); i++) {
101         int x = node[rt].t[i];
102         merge(fr[x], to[x]);
103     }
104 
105     if (l == r) {
106         if (l == 1)
107             return;
108 
109         int x = op2l[l], y = op2r[l];
110         int fx = find(x), fy = find(y);
111 
112         if (fx == fy)cout << "Y\n";
113         else cout << "N\n";
114 
115         split(num);
116         return;
117     }
118 
119     int mid = (l + r) / 2;
120     qr(rt * 2, l, mid);
121     qr(rt * 2 + 1, mid + 1, r);
122     split(num);
123 }
124 
125 int dp[N];
126 void sol() {
127     n = read();
128 
129     for (int i = 1; i <= n; i++)
130         f[i] = i, sz[i] = 1;
131 
132     int m = read();
133     int tm = 1;
134 
135     for (int i = 1; i <= m; i++) {
136         int op = read();
137 
138         if (op == 0) {
139             cnt++;
140             int x = read();
141             int y = read();
142             fr[cnt] = x;
143             to[cnt] = y;
144             e[x][y] = e[y][x] = cnt;
145             st[cnt] = tm + 1;
146         } else if (op == 1) {
147             int x = read();
148             int y = read();
149             en[e[x][y]] = tm;
150             e[x][y] = 0;
151         } else {
152             tm++;
153             op2l[tm] = read();
154             op2r[tm] = read();
155         }
156     }
157 
158     for (int i = 1; i <= cnt; i++)
159         if (en[i])
160             ud(1, 1, tm, st[i], en[i], i);
161         else
162             ud(1, 1, tm, st[i], tm, i);
163 
164     qr(1, 1, tm);
165 }
166 
167 int main() {
168     while (nyn--) {
169         sol();
170         printf("\n");
171     }
172 }

P5787 二分图 /【模板】线段树分治

线段树分治

嘻嘻，结束！