yukicoder : No.3238 Shadow

最終的にシンプルな解法になったが、それまでちょっと手間取った。
https://yukicoder.me/problems/no/3238

問題

1～Nの順列Pが与えられる。
これに対し、2次元座標上で座標(i,P[i])からなるN個の点を考える。

以下の手順を繰り返し、点がなくなるまで点を取り除いていく。

• 点BがAの陰にあるとは、AがBの左下にあることをいう。
• どこの陰にもない点の集合を同時に取り除く
  • その際のX座標・Y座標の最小値をそれぞれ答えよ。

解法

各点が何回目の手順で取り除かれるかを考えると、左下にある点のうち取り除かれる回次の最大値をxとするとx+1回目となる。
xは平面走査+区間最大値のSegTreeで求めることができる。

int N;
int P[202020];
pair<int,int> X[202020];
int dp[202020];

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_ma(){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_ma<int,1<<20> st;
int RX[202020],RY[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		X[i]={P[i],i};
	}
	sort(X,X+N);
	FOR(i,N+1) {
		RX[i]=RY[i]=1<<20;
	}
	int ma=0;
	FOR(i,N) {
		x=X[i].second;
		dp[x]=st.getval(0,x)+1;
		ma=max(ma,dp[x]);
		st.update(x,dp[x]);
		RX[dp[x]]=min(RX[dp[x]],x+1);
		RY[dp[x]]=min(RY[dp[x]],P[x]+1);
	}
	FOR(i,ma) cout<<RX[i+1]<<" "<<RY[i+1]<<endl;
		
}

まとめ

短めのコードになってよかったね。