(拡張UnionFind・ラムダ式)ABC-040-D-道路の老朽化対策について

問題URL→http://abc040.contest.atcoder.jp/tasks/abc040_d

クエリを年代順にソートしてUnionFindする問題。
ただし普通のUnionFindではだめで、各集合のサイズも取得できるようにしないといけない。
今回はそれを実装した。
またUnionFindを汎用的に使えるようにclass化もしたので良いライブラリが出来たと思う。

ラムダ式便利。

#include <iostream>
#include <vector>
#include <string.h>
#include <climits>
#include <algorithm>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//UnionFind!!!
class UnionFind
{
private:
    vector<int> par;
    vector<int> myRank;
    vector<int> cnt;

public:
    //n要素で初期化
    UnionFind(int n)
    {
        par.resize(n);
        myRank.resize(n);
        cnt.resize(n);
        REP(i,n) {
            par[i] = i;
            myRank[i] = 0;
            cnt[i] = 1;
        }
    }

    //木の根を求める
    int find(int x)
    {
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    //xとyの属する集合を併合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (myRank[x] < myRank[y]) {
            par[x] = y;
            cnt[y] += cnt[x];
        } else {
            par[y] = x;
            cnt[x] += cnt[y];
            if (myRank[x] == myRank[y]) myRank[x]++;
        }
    }

    //xとyが同じ集合に属するか否か
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    //xが含まれる集合の要素数
    int count(int x)
    {
        return cnt[find(x)];
    }
};

int N, M;
int a[202020], b[202020], y[202020];
int Q;
int v[101010], w[101010];

struct Query
{
    int year;
    int qType;
    int idx;
    int a, b;
    int v;
};

Query qs[303030];

signed main()
{
    cin >> N >> M;
    REP(i,M) {
        cin >> qs[i].a >> qs[i].b >> qs[i].year;
        qs[i].a--; qs[i].b--;
        qs[i].qType = 1;
    }
    cin >> Q;
    REP(i,Q) {
        cin >> qs[M+i].v >> qs[M+i].year;
        qs[M+i].v--;
        qs[M+i].qType = 2;
        qs[M+i].idx = i;
    }

    sort(qs, qs + M + Q, [](Query a, Query b){
        if (a.year == b.year) {
            return a.qType > b.qType;
        } else {
            return a.year > b.year;
        }
    });

    /*
    REP(i,M+Q) {
        cout << qs[i].year << " : " << qs[i].qType << endl;
    }
    */

    UnionFind uf(101010);

    vector<int> ans(Q);

    REP(i,M+Q) {
        if (qs[i].qType == 1) {
            uf.unite(qs[i].a, qs[i].b);
        } else {
            ans[qs[i].idx] = uf.count(qs[i].v);
        }
    }

    REP(i,Q) {
        cout << ans[i] << endl;
    }
}

(セグメント木・ラムダ式)ABC-038-D-プレゼント

問題URL→http://abc038.contest.atcoder.jp/tasks/abc038_d

まず二次元平面に点を打つ。
あとは左から見ていって点が見つかったときに、その高さ未満の範囲から最も入れ子の数が大きい値をセグメント木を使って高速に求める。

初めてラムダ式を使った。これ超便利。

//*
#include <bits/stdc++.h>
//*/
/*
#include <iostream>
#include <vector>
#include <string.h>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

struct SegmentTree
{
private:
    int n;
    vector<int> node;

public:
    //元配列v(vector)をセグメント木で表現する
    SegmentTree(vector<int> v)
    {
        //最下段のノード数は元配列のサイズ以上になる最小の2冪→これをnとおく
        //セグメント木全体で必要なノード数は2n-1である
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2 * n - 1, INF);

        //最下段に値を入れたあとに、下の段から埋めていく
        //値を埋めるときは自分の2つの子を見ればいい
        REP(i,sz) node[i+(n-1)] = v[i];
        for (int i=n-2; i>=0; i--) {
            //★セグ木の処理を書き換えるときはここを書き換える
            node[i] = min(node[2*i+1], node[2*i+2]);
        }
    }

    void update(int x, int val)
    {
        //最下段のノードにアクセスする
        x += n - 1;

        //最下段のノードを更新したら、あとは親に登って更新していく
        node[x] = val;
        while (x > 0) {
            //x=0でないなら親がある
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }

    //要求区間[a,b)の要素の最小値を答える
    //k:=自分がいるノードのインデックス
    //対象区間は[l,r)にあたる
    int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        //最初に呼び出されたときの対象区間は[0,n)
        if (r < 0) r = n;

        //要求区間と対象区間が交わらない→答えに影響を与えない値を返す
        //★セグ木の機能によって変える
        if (r <= a || b <= l) return INF;

        //要求区間が対象区間を完全に被覆→対象区間を答えの計算に使う
        if (a <= l && r <= b) return node[k];

        //要求区間が対象区間の一部を被覆→子について探索を行う
        //左の子をvl、右の子をvrとしている
        //新しい対象区間は現在の対象区間を半分にしたもの
        int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int N;
P wh[101010];

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> wh[i].first >> wh[i].second;
    }

    sort(wh, wh + N, [](P x, P y){
        if (x.first == y.first) return x.second > y.second;
        else return x.first < y.first;
    });

    vector<int> a(101010, 0);
    SegmentTree st(a);

    int ans = 0;
    REP(i,N) {
        int h = wh[i].second;
        int now = -st.getmin(0, h) + 1;
        ans = max(ans, now);
        st.update(h, -now);
    }

    cout << ans << endl;
}