yukicoder : No.1625 三角形の質問

想定解じゃなかったっぽい？
https://yukicoder.me/problems/no/1625

問題

2次元座標上で、N個の三角形が与えられる。
以後、以下のクエリに答えよ。

• 指定された三角形を追加する。
• X座標が[L,R]の範囲に収まる三角形のうち、面積の最大値を2倍したものを答えよ。

解法

自分は平面走査と平方分割で解いた。

まずクエリを平方分割する。
後者のクエリに対し、分割したバケット内で追加された三角形については、愚直に総当たりで判定する。
初期状態または、過去のバケット内で追加された三角形は、平面走査で処理する。

平面走査は以下のように行う。
まず、区間最大値を求めるSegTreeを準備する。このSegTreeでは、三角形の左端をキーとし、面積を値として格納する。
X座標については先に座標圧縮しておくとよい。
次にX座標を小さい順に走査しよう。

• 三角形の右端が走査中のX座標に到達したら、SegTreeにその三角形の情報を追加する。
• クエリの右端が走査中のX座標に到達したら、SegTree中で[L,R]の範囲の最大値を求める。

int N,Q;
int L[202020],R[202020];
ll A[202020];
int T[202020];
ll ret[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1;
	V comp(V l,V r){ return max(l,r);};
	
	void init(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> Xs;
	cin>>N>>Q;
	FOR(i,N) {
		ll X[3],Y[3];
		cin>>X[0]>>Y[0]>>X[1]>>Y[1]>>X[2]>>Y[2];
		L[i]=min({X[0],X[1],X[2]});
		R[i]=max({X[0],X[1],X[2]});
		X[1]-=X[0];
		X[2]-=X[0];
		Y[1]-=Y[0];
		Y[2]-=Y[0];
		A[i]=abs(X[1]*Y[2]-X[2]*Y[1]);
		Xs.push_back(L[i]);
		Xs.push_back(R[i]);
	}
	FOR(i,100000) {
		if(i<Q) {
			cin>>T[i+N];
			if(T[i+N]==1) {
				ll X[3],Y[3];
				cin>>X[0]>>Y[0]>>X[1]>>Y[1]>>X[2]>>Y[2];
				L[i+N]=min({X[0],X[1],X[2]});
				R[i+N]=max({X[0],X[1],X[2]});
				X[1]-=X[0];
				X[2]-=X[0];
				Y[1]-=Y[0];
				Y[2]-=Y[0];
				A[i+N]=abs(X[1]*Y[2]-X[2]*Y[1]);
			}
			else {
				cin>>L[i+N]>>R[i+N];
				ret[i+N]=-1;
			}
		}
		else {
			T[i+N]=0;
		}
		Xs.push_back(L[i+N]);
		Xs.push_back(R[i+N]);
	}
	Xs.push_back(0);
	Xs.push_back(1<<30);
	sort(ALL(Xs));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	FOR(i,N+Q) {
		L[i]=lower_bound(ALL(Xs),L[i])-Xs.begin();
		R[i]=lower_bound(ALL(Xs),R[i])-Xs.begin();
	}
	int pre;
	const int DI=1000;
	for(i=0;i<100000;i+=DI) {
		vector<pair<int,int>> ev;
		st.init();
		FOR(j,N+i) {
			if(j<N||T[j]==1) {
				ev.push_back({R[j],j});
			}
		}
		for(j=N+i;j<N+i+DI;j++) {
			if(T[j]==2) {
				ev.push_back({R[j],j});
				for(x=N+i;x<j;x++) if(T[x]==1 && L[j]<=L[x]&&R[x]<=R[j]) ret[j]=max(ret[j],A[x]);
			}
		}
		sort(ALL(ev));
		FORR2(r,i,ev) {
			if(i<N||T[i]==1) {
				st.update(L[i],A[i]);
			}
			else {
				ret[i]=max(ret[i],st.getval(L[i],R[i]));
			}
		}
		for(j=N+i;j<N+i+DI;j++) {
			if(T[j]==2) cout<<ret[j]<<endl;
		}
		continue;
		
	}
	
	
}

まとめ

平方分割+SegTreeで割と重いが、4sでどうにか通った。