F - Rectilinear Polygons

[Q] https://atcoder.jp/contests/abc211/tasks/abc211_f

解説AC。すごい。
https://www.youtube.com/watch?v=f3qwIMEoEbg&feature=youtu.be

二次元座標だけど、BITするのはy座標だけ。
クエリをx座標でソートして、xを0から100000まで探索する過程で、BITのyを適応させつつクエリ消化すれば、一次元(y座標)管理だけでおさまる。

1. 多角形を時計回りにそろえる。
2. x座標ごとに、y座標のデータを格納する。
3. xを0から100000まで動かして、BITを適応しつつ、クエリを消化する。

Q. 時計回り？

A. 入力例1を考える。
4
1 2 1 4 3 4 3 2
4
2 5 2 3 5 3 5 5

・1 2 1 4 3 4 3 2
↑→↓←の書き方なので、これは時計回り。
上昇するときに+1, 下降するときに-1の判定。

・2 5 2 3 5 3 5 5
↓→↑←なので反時計回り。逆転処理の対象。

{x,y}をpairで入れてsortすれば、座標の左下の始点が取れる。
始点から上にいけば時計回り、右にいけば反時計回りと判断する。

Q. BIT？
A. テンプレートを利用。
BITはadd(0, 1)をすると無限ループしてしまう(index0を渡すとだめ)
Bit.addの中で、index+1対応しているので、直接datの中身を見るときは注意。
dat[0]を見たかったら、dat[1]がそれ。

実装

// BIT,index = 1 ~ (0を投げるととまる
// indexを+1して格納する。
// https://atcoder.jp/contests/abc174/submissions/21572028
#define BT 100010
struct Bit
{
 ll dat[BT];
 Bit() {
   rep(i,BT) dat[i] = 0;
 }
 void add(ll i, ll x){
   ++i;
   for(; i<BT; i += i&-i) dat[i] += x;
 }
 ll sum(ll i){
   ++i;
   ll res = 0;
   for(; i>0; i -= i&-i) res += dat[i];
   return res;
 }
 ll rangesum(ll L, ll R){
   ++L, ++R;
   return sum(R) - sum(L-1);
 }
};

int main(){
 cincout();
 
 vector<pll> event[BT]; // event[x] = {y1, y2}
 ll N;
 cin >> N;
 rep(i, N){
   ll M;
   cin >> M;
   // 時計回りにしたい。(解説Vと逆回転。左下を原点とみなして判断。
   // 左下を見つける。右に行くようなら、逆転させたい。
   // 上プラス、下マイナス。
   vector<pll> P(M);
   rep(j, M) cin >> P[j].first >> P[j].second;
   ll s=0;
   rep(j, M) if(P[j] < P[s]) s=j; // 左下を見つけたい。
   rotate(P.begin(), P.begin()+s, P.end()); // 左下をスタート地点にする
   if (P[0].first != P[1].first) reverse(P.begin()+1, P.end()); // 右にいっちゃうなら回転を逆にする
   for(ll j=0; j<M; j+=2){
     event[P[j].first].push_back({P[j].second, P[j+1].second});
   }
 }
 
 ll Q;
 cin >> Q;
 ll ans[Q] = {};
 ll Y[Q] = {};
 vector<pll> VQ(Q);
 rep(i, Q){
   ll x;
   cin >> x >> Y[i];
   VQ[i] = {x, i}; // xでsort。indexを残したい
 }
 sort(all(VQ));

 Bit bits;
 ll q=0;
 rep(i, 100001){
   for(auto p: event[i]){
     ll w=1;
     ll down=p.first, up=p.second;
     if (up < down){ // 上から下にいくからマイナス
       swap(up, down);
       w=-1;
     }
     bits.add(down, w); // down==0だと壊れるからbitで+1判定
     bits.add(up, -w);
   }
   while (q<Q && VQ[q].first == i){
     ll id=VQ[q].second;
     ans[id] = bits.sum(Y[id]);
     ++q;
   }
   if (q==Q) break;
 }
 rep(i, Q) cout << ans[i] << endl;
}

https://atcoder.jp/contests/abc211/submissions/26066032