AtCoder ABC #136 : F - Enclosed Points

本番わちゃわちゃしてしまってもったいない。
https://atcoder.jp/contests/abc136/tasks/abc136_f

問題

２次元座標上で格子点の座標がN個与えられる。
なお、X座標やY座標が一致する点の対はない。

この点のうちゼロでない部分集合を選び、軸に平行なbounding boxを取ることを考える。(1点だけ取った場合、面積0のbounding boxとなるがそれでもよい)
このようなbounding box全通りに対し、含まれるN個の点の総和を求めよ。

解法

各点に対し、その点を含む部分集合が何通りあるか考える。
そのため、まず各点に対し左上・右上・左下・右下に何個の点があるかを求めよう。
これはX,Y座標を座標圧縮したうえで、X座標を昇順に走査していき、通過済みの点の左側においてY座標毎の点の数をカウントするBITと、右側の点の数をカウントするBITを持てばよい。

さて、左上・右上・左下・右下にある点の数が決まると、各方向について、その向きにある点が1個でも部分集合に含んでいるケースと1個も含まないケース系2**4通りを考える。
左上と右下、もしくは左下と右上の点を含むケースは、今見ている点を部分集合に含もうが含まなかろうがbounding box内にこの点が含まれるので、2倍カウントする。
それ以外は、選んだ点の集合は今見ている点を含まないので、今見ている点を明にbounding boxに入れるには、今見ている点を部分集合に含める一択で1倍分カウントする。

int N;
int X[202020],Y[202020];
ll mo=998244353;
vector<int> Xs,Ys;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> Lbt,Rbt;
int ev[202020];
ll p2[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,202010) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		Xs.push_back(X[i]);
		Ys.push_back(Y[i]);
	}
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	
	FOR(i,N) {
		X[i]=lower_bound(ALL(Xs),X[i])-Xs.begin();
		Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin();
		ev[X[i]]=Y[i];
		Rbt.add(Y[i],1);
	}
	ll ret=0;
	FOR(i,N) {
		Rbt.add(ev[i],-1);
		int lt,ld,rt,rd;
		FOR(lt,2) FOR(ld,2) FOR(rt,2) FOR(rd,2) {
			ll LT=lt?p2[Lbt(N)-Lbt(ev[i])]-1:1;
			ll LD=ld?p2[Lbt(ev[i])]-1:1;
			ll RT=rt?p2[Rbt(N)-Rbt(ev[i])]-1:1;
			ll RD=rd?p2[Rbt(ev[i])]-1:1;
			int cand=1;
			if((lt&&rd)||(ld&&rt)) cand++;
			(ret+=LT*LD%mo*RD%mo*RT*cand)%=mo;
		}
		
		Lbt.add(ev[i],1);
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
	
}

まとめ

本番16通りコピペと微修正で対応したので非常に疲れた。