真的波折。一开始半小时出来一个思路，写了半天的树套树，但是发现题目理解错了。
这题的桥意思是对于当前的图来说，删去这条边是否可以造成两个点不连通（也就是说图可能是不连通的）。
其实这样的情况和我一开始分析的思路也差不多。
我们以竖边来隔开各个部分，可以发现，只有在环上的边删去才不是桥。
那么我们就可以维护环上的边的条数来计算。
这里我们还要分析一些东西：
1：这个横边必须要满足上下两条都有，如果上下某条没有那么，那么它肯定无法组成环。
也就是说我们维护的横边都是上下都有的那种。
2：我们不需要一条条维护，我们直接维护整条连续的横边，因为他们被包含在同一个环中肯定有同一性质。
所以我们需要去找到这个连续横边内部的最左的竖边，和最右的竖边。那么这两条竖边和中间的横边组成的就是这段横边能组成的最大环。
有了这两点，我们就需要去维护了，首先，很明显我们可以用线段树去维护竖边（我一开始写的树套树也是这样..）
对于横边，我们可以用set去维护一整段，然后加点和拆点的时候，暴力拆除。因为我们每次操作都是单点的，所以每次的复杂度只有logn。
这里加点和删点都有几种情况，分析一下即可。
这里set有很多的问题：
因为对于多键值的情况，set对于第一关键字相等的情况也看做相同。
所以，因为左界可能存在重复次数，所以要用multiset。而且因为这里是迭代器的指针，在我们对set操作之后再去指针指向原地址，里面的数据可能已经变换了。
所以我们每次应该先计算cal再去操作set，并且我们尽量去删L，r而不是重新构建Line{L->L,L->r}这种再去删除，因为它再次去检索可能会导致删除的不是我们想要的。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; #define rg register const int N = 1e6 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { rg int f = 1,x = 0;rg char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} struct Line{ int L,r; bool operator < (const Line &a)const{ return L < a.L; } }; multiset<Line> S; struct Node{int L,r,mi,mx,sum;}node[N << 2]; int sz[N],ans = 0,n; void Pushup(int idx) { node[idx].mx = max(node[idx << 1].mx,node[idx << 1 | 1].mx); node[idx].mi = min(node[idx << 1].mi,node[idx << 1 | 1].mi); node[idx].sum = node[idx << 1].sum + node[idx << 1 | 1].sum; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r; if(L == r) { node[idx].mi = node[idx].mx = L; node[idx].sum = 1; return ; } int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); Pushup(idx); } void update(int x,int idx,int id) { if(node[idx].L == node[idx].r) { if(id == 0) node[idx].mx = -INF,node[idx].mi = INF,node[idx].sum = 0; else node[idx].mx = node[idx].mi = node[idx].L,node[idx].sum = 1; return ; } int mid = (node[idx].L + node[idx].r) >> 1; if(mid >= x) update(x,idx << 1,id); else update(x,idx << 1 | 1,id); Pushup(idx); } int query_mi(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].mi; int mid = (node[idx].L + node[idx].r) >> 1,mi = INF; if(mid >= L) mi = min(mi,query_mi(L,r,idx << 1)); if(mid < r) mi = min(mi,query_mi(L,r,idx << 1 | 1)); return mi; } int query_mx(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].mx; int mid = (node[idx].L + node[idx].r) >> 1,mx = -INF; if(mid >= L) mx = max(mx,query_mx(L,r,idx << 1)); if(mid < r) mx = max(mx,query_mx(L,r,idx << 1 | 1)); return mx; } int query_sum(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].sum; int mid = (node[idx].L + node[idx].r) >> 1,sum = 0; if(mid >= L) sum += query_sum(L,r,idx << 1); if(mid < r) sum += query_sum(L,r,idx << 1 | 1); return sum; } int cal(int L,int r) { int le = 0,ri = 0; while(L < 1 || r > n) {} int sum = query_sum(L,r,1); if(sum <= 1) return 0; else { le = query_mi(L,r,1); ri = query_mx(L,r,1); return (ri - le) * 2 + sum; } } void upd_row(int x,int id) { if(id == 0) { auto L = S.upper_bound(Line{x,x + 1}); --L; auto r = S.lower_bound(Line{x,x + 1}); sz[x]++; if(sz[x] == 1) return; else { if(L->r == x && r->L != x + 1) { ans -= cal(L->L,L->r); ans += cal(L->L,x + 1); S.insert(Line{L->L,x + 1}); S.erase(L); } else if(L->r != x && r->L == x + 1) { ans -= cal(r->L,r->r); ans += cal(x,r->r); S.insert(Line{x,r->r}); S.erase(r); } else if(L->r == x && r->L == x + 1) { ans -= cal(L->L,L->r); ans -= cal(r->L,r->r); ans += cal(L->L,r->r); S.insert(Line{L->L,r->r}); S.erase(L); S.erase(r); } else if(L->r != x && r->L != x + 1){ ans += cal(x,x + 1); S.insert(Line{x,x + 1}); } } } else { auto p = S.upper_bound(Line{x, x + 1}); p--; sz[x]--;; if (sz[x] == 0) return; if (p->L == x && p->r == x + 1) { ans -= cal(x, x + 1); S.erase(p); } else if (p->L == x && p->r != x + 1) { ans += cal(x+1,p->r); ans -= cal(p->L,p->r); S.insert(Line{x+1,p->r}); S.erase(p); } else if (p->L != x && p->r == x + 1) { ans += cal(p->L,x); ans -= cal(p->L,p->r); S.insert(Line{p->L,x}); S.erase(p); } else if (p->L != x && p->r != x + 1) { ans -= cal(p->L, p->r); ans += cal(p->L, x); ans += cal(x+1, p->r); S.insert(Line{p->L, x}); S.insert(Line{x+1, p->r}); S.erase(p); } } } void upd_line(int x,int id) { auto L = S.upper_bound(Line{x,x});L--; if(id == 0) { if(L->r >= x) { ans -= cal(L->L,L->r); update(x,1,1); ans += cal(L->L,L->r); } else update(x,1,1); } else { if(L->r >= x) { ans -= cal(L->L,L->r); update(x,1,0); ans += cal(L->L,L->r); } else update(x,1,0); } } void solve() { int m;n = read(),m = read(); S.clear(); S.insert(Line{1,n}); S.insert(Line{-1,-1}); S.insert(Line{n + 2,n + 2}); for(int i = 1;i <= n;++i) sz[i] = 2; build(1,n,1); int allsz = 3 * n - 2; ans = 3 * n - 2; while(m--) { int id,x0,y0,x1,y1;id = read(),x0 = read(),y0 = read(),x1 = read(),y1 = read(); if(id == 1) { allsz++; if(x0 == x1) upd_row(min(y0,y1),0); else upd_line(min(y0,y1),0); } else { allsz--; if(x0 == x1) upd_row(min(y0,y1),1); else upd_line(min(y0,y1),1); } printf("%d ",allsz - ans); } } int main() { int ca;ca = read(); while(ca--) { solve(); } // system("pause"); return 0; }