新手如何做服装网站,广州开发小程序,建网站买什么主机,长沙好的做网站品牌HDU6218 2017ACM/ICPC亚洲区沈阳站 Bridge
Solution
我们考虑维护在环上的边的个数#xff0c;答案就是总边数减去环上边数。
环的形态是这样的#xff1a;(0,l),(0,l1)...(0,r),(1,r),(1,r−1)...(1,l)(0,l),(0,l1)...(0,r),(1,r),(1,r-1)...(1,l)(0,l),(0,l1)...(0,r),(…HDU6218 2017ACM/ICPC亚洲区沈阳站 Bridge
Solution
我们考虑维护在环上的边的个数答案就是总边数减去环上边数。
环的形态是这样的(0,l),(0,l1)...(0,r),(1,r),(1,r−1)...(1,l)(0,l),(0,l1)...(0,r),(1,r),(1,r-1)...(1,l)(0,l),(0,l1)...(0,r),(1,r),(1,r−1)...(1,l)。 考虑怎样才会连成环显然是上下两段连续的横边加上它们之间的纵边。因此横坐标在[l,r][l,r][l,r]之间的点在同一个环上的必要条件是[l,r][l,r][l,r]之间的横边都存在。
因此我们可以用setsetset维护上下两段连续的横边都存在的极长连续段[l,r][l,r][l,r]。然后对于[l,r][l,r][l,r]之间的纵边我们找到该区间内最左边的纵边mnmnmn和最右边的纵边mxmxmx以及总纵边个数numnumnum。那么这个极长连续段的环边个数为2(mx−mn)num2(mx-mn)num2(mx−mn)num且因为我们维护的是极长连续段因此总环边个数就是所有极长连续段的环边个数之和不会算重。
对于mn,mx,nummn,mx,nummn,mx,num直接用线段树维护即可。 时间复杂度O(mlgn)O(mlgn)O(mlgn)。
注意n1n1n1的情况可能会算出−1-1−1来虽然评测数据没有这种情况 注意题中给定的坐标(x1,y1),(x2,y2)(x1,y1),(x2,y2)(x1,y1),(x2,y2)可能存在y1y2y1y2y1y2的情况
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 secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods924844033;
const int MAXN200005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
setPR 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.sumb.sum); }int mn,mx,sum;
} s[MAXN2];
void Build(int x,int l,int r)
{if (lr) { s[x]Node(l,l,1); return; }int mid(lr)1;Build(x1,l,mid);Build(x1|1,mid1,r);s[x]s[x1]s[x1|1];
}
void Update(int x,int l,int r,int y,int z)
{if (lr) { s[x](z-1?Node(INF,0,0):Node(l,l,1)); return; }int mid(lr)1;if (ymid) Update(x1,l,mid,y,z);else Update(x1|1,mid1,r,y,z);s[x]s[x1]s[x1|1];
}
Node Query(int x,int l,int r,int L,int R)
{if (lLrR) return s[x];int mid(lr)1;if (Rmid) return Query(x1,l,mid,L,R);else if (Lmid) return Query(x1|1,mid1,r,L,R);else return Query(x1,l,mid,L,mid)Query(x1|1,mid1,r,mid1,R);
}int update(int x,int opt)
{if (x1||xn) return 0;setPR::iterator itSet.lower_bound(MP(x1,0));if (itSet.begin()||(--it)-sex) return 0;Node tQuery(1,1,n,it-fi,it-se1);if (t.sum1) return 1;ans-((t.mx-t.mn)*2t.sum)*opt;return 1;
}
void add(int x)
{setPR::iterator itSet.lower_bound(MP(x1,0));PR tMP(x,x),LMP(0,0),RMP(0,0);if (it!Set.end()it-fix1) R*it;if (it!Set.begin()(--it)-sex-1) L*it;if (R.fi) Set.erase(Set.find(R)),t.seR.se;if (L.fi) Set.erase(Set.find(L)),t.fiL.fi;Set.insert(t);
}
void erase(int x)
{setPR::iterator itSet.lower_bound(MP(x1,0));PR t*(--it);Set.erase(it);if (t.fix) Set.insert(MP(t.fi,x-1));if (t.sex) Set.insert(MP(x1,t.se));
}signed main()
{int Caseread();while (Case--){nread(),mread(),ans(n1);Build(1,1,n);Set.clear(),Set.insert(MP(1,n));for (int i1;in;i) flag[i]2;while (m--){int optread(),x1read(),y1read(),x2read(),y2read();if (y1y2) swap(y1,y2);ans(opt1)?1:-1;if (opt1x1x2(flag[y1])2) update(y1-1,-1),update(y11,-1),add(y1),update(y1,1);if (opt2x1x2(--flag[y1])1) update(y1,-1),erase(y1),update(y1-1,1),update(y11,1);if (y1y2){if (!update(y1,-1)) update(y1-1,-1);Update(1,1,n,y1,(opt1)?1:-1);if (!update(y1,1)) update(y1-1,1);}printf(%d\n,ans);}}return 0;
}
