yukicoder : No.743 Segments on a Polygon

これはあまり迷わなかったかな。
https://yukicoder.me/problems/no/743

問題

凸M角形があるとする。各点は順に0～(M-1)のラベルを持つとする。
ここで、このM点を端点とするN個の線分を追加するとする。
線分同士の交点はいくつになるか。なお、同一の点を３つ以上の線分が通過する場合、交点は重複してカウントする。
なお、線分同士が端点を共有することはないものとする。

解法

辺の両端の点を(u,v) (u＜v)と表現することにする。
u＜xである時、(u,v)と(x,y)が交点を持つにはx＜u＜yであればよい。
言い換えれば、u＜x＜vであるようなxのうちv＜yとなるものを数え上げればよい。

全頂点に対し、辺の両端のu,vをそれぞれ番号順に並べ、走査しながらBITで数えていくことができる。

• 線分の始点uを処理する場合

- BITのu番目の要素をインクリメントする

• 線分の終端vを処理する場合

- BITで[(u+1),∞]の間の要素数を数える
- BITで始点側に対応するu番目の要素をデクリメントする

int N,M;
vector<pair<int,int>> V;

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> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		V.push_back({min(x,y),-1});
		V.push_back({max(x,y),min(x,y)});
	}
	
	ll ret=0;
	sort(ALL(V));
	FORR(v,V) {
		if(v.second==-1) {
			bt.add(v.first,1);
		}
		else {
			bt.add(v.second,-1);
			ret+=bt(1<<19)-bt(v.second);
		}
	}
	cout<<ret<<endl;
}

まとめ

意外にコードもすっきり。