HDU6218 2017ACM/ICPC亚洲区沈阳站 Bridge

Solution

我们考虑维护在环上的边的个数，答案就是总边数减去环上边数。

环的形态是这样的： ( 0 , l ) , ( 0 , l + 1 ) . . . ( 0 , r ) , ( 1 , r ) , ( 1 , r − 1 ) . . . ( 1 , l ) (0,l),(0,l+1)...(0,r),(1,r),(1,r-1)...(1,l) (0,l),(0,l+1)...(0,r),(1,r),(1,r−1)...(1,l)。
考虑怎样才会连成环，显然是上下两段连续的横边加上它们之间的纵边。因此横坐标在 [ l , r ] [l,r] [l,r]之间的点在同一个环上的必要条件是 [ l , r ] [l,r] [l,r]之间的横边都存在。

因此我们可以用 s e t set set维护上下两段连续的横边都存在的极长连续段 [ l , r ] [l,r] [l,r]。然后对于 [ l , r ] [l,r] [l,r]之间的纵边，我们找到该区间内最左边的纵边 m n mn mn和最右边的纵边 m x mx mx以及总纵边个数 n u m num num。那么这个极长连续段的环边个数为 2 ( m x − m n ) + n u m 2(mx-mn)+num 2(mx−mn)+num，且因为我们维护的是极长连续段，因此总环边个数就是所有极长连续段的环边个数之和，不会算重。

对于 m n , m x , n u m mn,mx,num mn,mx,num，直接用线段树维护即可。
时间复杂度 O ( m l g n ) O(mlgn) O(mlgn)。

注意 n = 1 n=1 n=1的情况可能会算出 − 1 -1 −1来！（虽然评测数据没有这种情况）
注意题中给定的坐标 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x1,y1),(x2,y2) (x1,y1),(x2,y2)，可能存在 y 1 > y 2 y1>y2 y1>y2的情况！！！

Code

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=924844033;
const int MAXN=200005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
set<PR> Set;
int flag[MAXN],n,m,ans;
struct Node
{ 
	Node(){}
	Node(int mn,int mx,int sum):mn(mn),mx(mx),sum(sum){};
	friend Node operator + (Node a,Node b) { return Node(min(a.mn,b.mn),max(a.mx,b.mx),a.sum+b.sum); }
	int mn,mx,sum; 
} s[MAXN<<2];
void Build(int x,int l,int r)
{
	if (l==r) { s[x]=Node(l,l,1); return; }
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	s[x]=s[x<<1]+s[x<<1|1];
}
void Update(int x,int l,int r,int y,int z)
{
	if (l==r) { s[x]=(z==-1?Node(INF,0,0):Node(l,l,1)); return; }
	int mid=(l+r)>>1;
	if (y<=mid) Update(x<<1,l,mid,y,z);
	else Update(x<<1|1,mid+1,r,y,z);
	s[x]=s[x<<1]+s[x<<1|1];
}
Node Query(int x,int l,int r,int L,int R)
{
	if (l>=L&&r<=R) return s[x];
	int mid=(l+r)>>1;
	if (R<=mid) return Query(x<<1,l,mid,L,R);
	else if (L>mid) return Query(x<<1|1,mid+1,r,L,R);
	else return Query(x<<1,l,mid,L,mid)+Query(x<<1|1,mid+1,r,mid+1,R);
}

int update(int x,int opt)
{
	if (x<1||x>n) return 0;
	set<PR>::iterator it=Set.lower_bound(MP(x+1,0));
	if (it==Set.begin()||(--it)->se<x) return 0;
	Node t=Query(1,1,n,it->fi,it->se+1);
	if (t.sum<=1) return 1;
	ans-=((t.mx-t.mn)*2+t.sum)*opt;
	return 1;
}
void add(int x)
{
	set<PR>::iterator it=Set.lower_bound(MP(x+1,0));
	PR t=MP(x,x),L=MP(0,0),R=MP(0,0);
	if (it!=Set.end()&&it->fi==x+1) R=*it;
	if (it!=Set.begin()&&(--it)->se==x-1) L=*it;
	if (R.fi) Set.erase(Set.find(R)),t.se=R.se;
	if (L.fi) Set.erase(Set.find(L)),t.fi=L.fi;
	Set.insert(t);
}
void erase(int x)
{
	set<PR>::iterator it=Set.lower_bound(MP(x+1,0));
	PR t=*(--it);
	Set.erase(it);
	if (t.fi<x) Set.insert(MP(t.fi,x-1));
	if (t.se>x) Set.insert(MP(x+1,t.se));
}

signed main()
{
	int Case=read();
	while (Case--)
	{
		n=read(),m=read(),ans=(n==1);
		Build(1,1,n);
		Set.clear(),Set.insert(MP(1,n));
		for (int i=1;i<n;i++) flag[i]=2;
		while (m--)
		{
			int opt=read(),x1=read(),y1=read(),x2=read(),y2=read();
			if (y1>y2) swap(y1,y2);
			ans+=(opt==1)?1:-1;
			if (opt==1&&x1==x2&&(++flag[y1])==2) update(y1-1,-1),update(y1+1,-1),add(y1),update(y1,1);
			if (opt==2&&x1==x2&&(--flag[y1])==1) update(y1,-1),erase(y1),update(y1-1,1),update(y1+1,1);
			if (y1==y2)
			{
				if (!update(y1,-1)) update(y1-1,-1);
				Update(1,1,n,y1,(opt==1)?1:-1);
				if (!update(y1,1)) update(y1-1,1);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}