【UOJ191】【集训队互测2016】Unknown（二进制分组）（凸壳二分）

传送门

不想写题解，罗哲正论文里面写得很清楚，感觉我没有什么好写的，也没什么必要再证明一遍复杂度了

题目原名是“我们仍未知道那天所看见的数据结构的名字”，但是实际上却是利用分治解决了一个看上去很像数据结构的题。

罗哲正在论文里面说考场上AC估计要花2~4小时。

我TM，我觉得要是我想到操作树上树分治我估计两个小时都调补粗来

罗哲正论文里面说二进制分组空间复杂度 $O(n\log n)$估计只有90分。

但是它空间常数小的一批啊

现在UOJ上第一页好像全部都是论文里面这种看着像线段树的二进制分组做法。

我看到的空间最小的二进制分组才32MB不到，虽然我的有34MB

想清楚了还是很好写，虽然写的时候还是很紧张，总是在想集训队胡策正解代码怎么这么短

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

namespace IO{
	inline char gc(){
		static cs int Rlen=1<<22|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	template<typename T>
	inline T get(){
		char c;T num;bool f=0;
		while(!isdigit(c=gc()))f=c=='-';num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return f?-num:num; 
	}
	inline int gi(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout; 

cs int N=3e5+7,mx=1<<19,mod=998244353;

struct Point{int x,y;};
ll operator*(cs Point &a,cs Point &b){return (ll)a.x*b.y-(ll)a.y*b.x;}
Point operator-(cs Point &a,cs Point &b){return (Point){a.x-b.x,a.y-b.y};}
Point nd[20][N],*hull[mx+N],*a;
int siz[mx+N],ans,now,tp,m;

inline void ins(cs Point &p){
	if(tp&&a[tp-1].x==p.x){
		if(a[tp-1].y>=p.y)return ;
		--tp;
	}
	while(tp>1&&(a[tp-2]-a[tp-1])*(p-a[tp-1])<=0)--tp;
	a[tp++]=p;
}
inline void build(int p){
	if(siz[p])return ;
	a=hull[p],tp=0;
	Point *Lx=hull[p<<1],*cs Ly=Lx+siz[p<<1];
	Point *Rx=hull[p<<1|1],*cs Ry=Rx+siz[p<<1|1];
	while(Lx<Ly&&Rx<Ry)ins(Lx->x<Rx->x?*Lx++:*Rx++);
	while(Lx<Ly)ins(*Lx++);while(Rx<Ry)ins(*Rx++);
	siz[p]=tp;
}
inline void push(){
	int x=gi(),y=gi(),q=mx+(++now);
	siz[q]=1;*hull[q]=(Point){x,y};
	for(;q&1;q>>=1,build(q-1));
}
inline void pop(){
	for(int re p=mx+now-->>1;siz[p]>0;p>>=1)siz[p]=0;
}

inline ll query(int t,cs Point &p){
	if(!siz[t])return std::max(query(t<<1,p),query(t<<1|1,p));
	a=hull[t];int l=0,r=siz[t]-1,mid;
	while(l+3<r){
		mid=l+r>>1;
		(p*a[mid]>p*a[mid+1])?r=mid:l=mid+1;
	}
	ll ans=p*a[l++];
	while(l<=r)ans=std::max(ans,p*a[l++]);
	return ans;
}
inline int query(){
	ll ans=-1ll<<61;
	int l=gi()+mx-1,r=gi()+mx+1,x=gi(),y=gi();
	Point p=(Point){x,y};
	for(;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=std::max(ans,query(l^1,p));
		if(r&1) ans=std::max(ans,query(r^1,p));
	}
	return (ans%mod+mod)%mod;
} 

inline void solve(){
	while(m--){
		switch(gi()){
			case 1:push();break;
			case 2:pop();break;
			case 3:ans^=query();
		}
	}
	cout<<ans<<"\n";
}
inline void init(){
	ans=now=0;
	for(int re l=mx,r=mx+std::min(N,m),d=0;l;l>>=1,r>>=1,++d)
	for(int re i=l;i<=r;++i)hull[i]=nd[d]+(i-l<<d),siz[i]=0;
	for(int re t=mx;t;t>>=1)siz[t]=siz[t-1]=-1;
}

signed main(){
#ifdef zxyoi
	freopen("unknown.in","r",stdin);
#endif
	gi();while(m=gi())init(),solve();
	return 0;
}