网站开发主管待遇,App加网站什么做,常州网站建设公司案例,手游游戏源码资源网UOJ#191. 【集训队互测2016】Unknown
题目描述
Solution
二进制分组。 每一个组内维护一个斜率单调减的凸包。 因为有删点#xff0c;避免出现反复横跳产生的爆炸复杂度#xff0c;需要等到同一深度的下一个区间填满之后再合并当前区间。 时间复杂度O(nlg2n)O(nlg^2n)O(nl…UOJ#191. 【集训队互测2016】Unknown
题目描述
Solution
二进制分组。 每一个组内维护一个斜率单调减的凸包。 因为有删点避免出现反复横跳产生的爆炸复杂度需要等到同一深度的下一个区间填满之后再合并当前区间。 时间复杂度O(nlg2n)O(nlg^2n)O(nlg2n)。
#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 mods998244353;
const int MAXN600005;
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;
}
struct Vct
{int x,y;Vct(int x10,int y10) { xx1,yy1; }Vct operator (const Vct a) { return Vct(xa.x,ya.y); }Vct operator - (const Vct a) { return Vct(x-a.x,y-a.y); }ll operator * (const Vct a) { return 1ll*x*a.y-1ll*y*a.x; }friend bool operator (const Vct a,const Vct b) { return (a.xb.x)||(a.xb.xa.yb.y); }
};
struct Convex_Hull
{vectorVct V;void Clear() { V.clear(); }Convex_Hull(){ Clear(); }void Push(Vct x) { int nV.size(); while (n2(x-V[n-2])*(V[n-1]-V[n-2])0) V.pop_back(),n--; n,V.PB(x); }friend Convex_Hull Merge(const Convex_Hull x,const Convex_Hull y){Convex_Hull ans;int i,j;for (i0,j0;ix.V.size()jy.V.size();) ans.Push(x.V[i]y.V[j]?x.V[i]:y.V[j]);for (;ix.V.size();) ans.Push(x.V[i]);for (;jy.V.size();) ans.Push(y.V[j]);return ans;}ll Query(Vct x){int l0,rV.size()-1;while (l5r){int mid(lr1)1;if ((V[mid]-V[mid-1])*x0) lmid;else rmid-1;}ll ans-loo;for (int il;ir;i) upmax(ans,x*V[i]);return ans;}
};
struct Segment_Tree
{int flag[MAXN1],lst[20];Convex_Hull tree[MAXN1];void up(int x) { flag[x]1,tree[x]Merge(tree[x1],tree[x1|1]); }void build(int x,int l,int r,int dep){lst[dep]0;tree[x].Clear(),flag[x]0;if (lr) return;int mid(lr)1;build(x1,l,mid,dep1);build(x1|1,mid1,r,dep1);}void insert(int x,int l,int r,int y,Vct z,int dep){if (ry){if (lst[dep]) up(lst[dep]);lst[dep](lr)?0:x;}if (lr) { tree[x].Push(z); return; }int mid(lr)1;if (ymid) insert(x1,l,mid,y,z,dep1);else insert(x1|1,mid1,r,y,z,dep1);}void erase(int x,int l,int r,int y,int dep){tree[x].Clear(),flag[x]0;if (lst[dep]x) lst[dep]0;if (lr) return; int mid(lr)1;if (ymid) erase(x1,l,mid,y,dep1);else erase(x1|1,mid1,r,y,dep1);}ll query(int x,int l,int r,int L,int R,Vct y){int mid(lr)1;if (LlrR) {if (lr||flag[x]) return tree[x].Query(y);return max(query(x1,l,mid,l,mid,y),query(x1|1,mid1,r,mid1,r,y));}if (Rmid) return query(x1,l,mid,L,R,y);else if (Lmid) return query(x1|1,mid1,r,L,R,y);else return max(query(x1,l,mid,L,mid,y),query(x1|1,mid1,r,mid1,R,y));}
} segment;
int main()
{int zblread(),Case;while (Caseread()){int nmin(300000,Case),num0,ans0;segment.build(1,1,n,0);while (Case--){int optread();if (opt1) { int xread(),yread(); segment.insert(1,1,n,num,Vct(x,y),0); }else if (opt2) { segment.erase(1,1,n,num--,0); }else {int lread(),rread(),xread(),yread();ll tsegment.query(1,1,n,l,r,Vct(x,y));((t%mods)mods)%mods;ans^t;}}printf(%d\n,ans);}return 0;
}
卡空间很恶心。