백준 알고리즘 1615번 : 교차개수세기

링크

https://www.acmicpc.net/problem/1615

실패) 세그먼트 트리 + inversion counting

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

using pii = pair<int,int>;

struct SegTree {
	int tree[1 << 20];
	int sz = 1 << 19;
	void construct() {
		for (int i = sz - 1; i > 0; i--) {
			tree[i] = tree[i << 1] + tree[i << 1 | 1];
		}
	}
  // 1 - indexed
	void update(int i, int val) {
		--i |= sz; tree[i] = val;
		while (i >>= 1) {
			tree[i] = tree[i << 1] + tree[i << 1 | 1];
		}
	}
  // [l, r]
	int query(int l, int r) {
		--l |= sz, --r |= sz;
		int ret = 0;
		while (l <= r) {
			if (l & 1) ret += tree[l++];
			if (~r & 1) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		return ret;
	}
}ST;

int32_t main() {
  fastio;
  int n,m,r = 0; cin >> n >> m;
  vector<pii> v(m);
  for(auto& [a,b] : v) cin >> a >> b;
  sort(v.begin(),v.end(),[](pii a,pii b){
    if(a.first != b.first) return a.first < b.first;
    return a.second > b.second;
  });
  for(int i = 0; i < m; i++){
    int t = v[i].second;
    r += (t - 1 - ST.query(1, t - 1));
    ST.update(t, 1);
  }
  cout << r << "\n";
}

sol1) 펜윅트리 + inversion counting

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

using pii = pair<int,int>;

template<size_t sz>
struct FenwickTree {
    vector<int> tree;
    FenwickTree() : tree(sz + 1) {}
    void update(int i, int val) {
        for (; i <= sz; i += i & -i) tree[i] += val;
    }
    int query(int i) {
        int ret = 0;
        for (; i; i -= i & -i) ret += tree[i];
        return ret;
    }
};

int32_t main() {
  fastio;
  int n,m,r = 0; cin >> n >> m;
  FenwickTree<2001> FT;
  vector<pii> v(m);
  for(auto& [a,b] : v) cin >> a >> b;
  sort(v.begin(), v.end());
  for(int i = m - 1; i >= 0; i--){
    int t = v[i].second;
    r += FT.query(t - 1);
    FT.update(t, 1);
  }
  cout << r << "\n";
}