以时间为下标建线段树，则持续[L, R]时间的一个事物就能被表示成logn段区间。
这样就避免删除只有插入。
例题：
bzoj4644 经典傻逼题
每个点的点权为与它相连的边的权值异或和。求最大权点集即可。
线段树分治 + 线性基 + bitset。
1 #include2 #include 3 #include 4 #include 5 6 const int N = 1010; 7 8 std::vector v[N * 4]; 9 typedef std::bitset B; 10 11 struct Edge { 12 int x, y; 13 B v; 14 }edge[N]; 15 16 int n, m; 17 char str[N]; 18 B base[N], val[N]; 19 20 void insert(int i, int l, int r, int o) { 21 if(i <= l && r <= m) { 22 v[o].push_back(i); 23 return; 24 } 25 int mid = (l + r) >> 1; 26 if(i <= mid) { 27 insert(i, l, mid, o << 1); 28 } 29 if(mid < m) { 30 insert(i, mid + 1, r, o << 1 | 1); 31 } 32 return; 33 } 34 35 inline void getAns() { 36 for(int i = 0; i < N; i++) { 37 base[i].reset(); 38 } 39 for(int i = 1; i <= n; i++) { 40 B x = val[i]; 41 for(int j = N - 1; j >= 0 && x.any(); j--) { 42 if(!x[j]) { 43 continue; 44 } 45 if(base[j].none()) { 46 base[j] = x; 47 break; 48 } 49 x ^= base[j]; 50 } 51 } 52 B ans; 53 ans.reset(); 54 for(int i = N - 1; i >= 0; i--) { 55 if(base[i].none()) { 56 continue; 57 } 58 if(!ans[i]) { 59 ans ^= base[i]; 60 } 61 } 62 bool f = false; 63 for(int i = N - 1; i >= 0; i--) { 64 if(ans[i]) f = true; 65 if(!f) continue; 66 printf("%d", (int)ans[i]); 67 } 68 if(!f) printf("0"); 69 puts(""); 70 return; 71 } 72 73 void ask(int l, int r, int o) { 74 for(int i = 0; i < (int)v[o].size(); i++) { 75 int j = v[o][i]; 76 val[edge[j].x] ^= edge[j].v; 77 val[edge[j].y] ^= edge[j].v; 78 } 79 if(l == r) { 80 getAns(); 81 for(int i = 0; i < (int)v[o].size(); i++) { 82 int j = v[o][i]; 83 val[edge[j].x] ^= edge[j].v; 84 val[edge[j].y] ^= edge[j].v; 85 } 86 return; 87 } 88 int mid = (l + r) >> 1; 89 ask(l, mid, o << 1); 90 ask(mid + 1, r ,o << 1 | 1); 91 for(int i = 0; i < (int)v[o].size(); i++) { 92 int j = v[o][i]; 93 val[edge[j].x] ^= edge[j].v; 94 val[edge[j].y] ^= edge[j].v; 95 } 96 return; 97 } 98 99 int main() {100 //printf("%d \n", (sizeof(base) * 3) / 1048576);101 int q;102 scanf("%d%d%d", &q, &n, &m);103 for(int i = 1; i <= m; i++) {104 scanf("%d%d%s", &edge[i].x, &edge[i].y, str);105 int a = strlen(str);106 for(int j = a - 1; j >= 0; j--) {107 edge[i].v[a - 1 - j] = str[j] - '0';108 }109 for(int j = a; j < N; j++) {110 edge[i].v[j] = 0;111 }112 insert(i, 1, m, 1);113 }114 115 ask(1, m, 1);116 117 return 0;118 }
bzoj4025 二分图
带撤销带权并查集 + 线段树分治。
线段树分治 + lct。