(2番目の最短経路)POJ-3255-Roadblocks

問題URL→http://poj.org/problem?id=3255

蟻本に載っている問題。
2番目の最短路を求めるにはdistを2つ用意する。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
//*/
#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 edge
{
    int to;
    int cost;
    
    edge() {}
    edge(int to, int cost) : to(to), cost(cost) {}
};

int N, R;
vector<edge> G[5050];

int dist[5050];     //最短距離
int dist2[5050];    //2番目の最短距離

signed main()
{
    cin >> N >> R;
    REP(i,R) {
        int A, B, D;
        cin >> A >> B >> D;
        A--; B--;
        G[A].push_back(edge(B, D));
        G[B].push_back(edge(A, D));
    }

    //firstが小さい順に取り出せる
    //first:距離 second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    fill(dist, dist + N, INF);
    fill(dist2, dist2 + N, INF);
    dist[0] = 0;
    que.push(P(0, 0));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;
        if (dist2[v] < d) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            int d2 = d + e.cost;
            if (dist[e.to] > d2) {
                swap(dist[e.to], d2);
                que.push(P(dist[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist[e.to] < d2) {
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }

    cout << dist2[N - 1] << endl;
}

(BIT・X番目の数)ARC-033-C-データ構造

問題URL→http://arc033.contest.atcoder.jp/tasks/arc033_3

問題概要
分からなかったので解説を見て解いた。BITは久しぶりに実装したかも。
解説にあるとおり、「X番目の数」を「それ以下の数がX個であるような数のうち最も小さい数」という言い換えが重要。
この言い換えを使うと、「ある数以下の数がいくつあるか」が高速にも求まるデータ構造BITやセグメント木を使える。今回はBITを使った。
平方分割の別解もある模様。

#include <bits/stdc++.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
using namespace std;
typedef long long ll;
const int INF = 1e9;

const int MAX_N = 202020;
//[1,n]のBIT
int bit[MAX_N+1], n;

int sum(int i)
{
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x)
{
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

int Q;
int T, X;

signed main()
{
    cin >> Q;

    n = 200000;
    REP(i,Q) {
        cin >> T >> X;
        if (T == 1) {
            add(X, 1);
        } else {
            int lb = 0, ub = 200000;
            while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (sum(mid) >= X) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }
            cout << ub << endl;
            add(ub, -1);
        }
    }
}

(K番目の値を求める・セグメント木)ARC-028-B-特別賞

問題URLhttp://arc028.contest.atcoder.jp/tasks/arc028_2

問題概要
解説を見たら自分のやり方よりはるかに簡単なやり方が書いてあったが、自分は蟻本のK-th Numberを写した。

#include <bits/stdc++.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
using namespace std;
typedef long long ll;
const int INF = 1e9;
 
const int MAX_N = 101010;
const int ST_SIZE = (1 << 18) - 1;
 
int A[MAX_N];
int nums[MAX_N];            //Aをソートしたもの
vector<int> dat[ST_SIZE];   //セグメント木のデータ
 
//セグメント木を構築する
//kは節点の番号で、区間[l,r)に対応する
void init(int k, int l, int r)
{
    if (r - l == 1) {
        dat[k].push_back(A[l]);
    } else {
        int lch = k * 2 + 1, rch = k * 2 + 2;
        init(lch, l, (l + r) / 2);
        init(rch, (l + r) / 2, r);
        dat[k].resize(r - l);
 
        //STLのmerge関数を用いて、子の2つの列をマージ
        merge(dat[lch].begin(), dat[lch].end(), dat[rch].begin(), dat[rch].end(), dat[k].begin());
    }
}
 
//[i,j)のx以下の数の個数を数える
//kは節点の番号で、区間[l,r)に対応する
int query(int i, int j, int x, int k, int l, int r)
{
    if (j <= l || r <= i) {
        //完全に交差しない
        return 0;
    } else if (i <= l && r <= j) {
        //完全に含まれる
        return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
    } else {
        //子について再帰的に求める
        int lc = query(i, j, x, k * 2 + 1, l, (l + r) / 2);
        int rc = query(i, j, x, k * 2 + 2, (l + r) / 2, r);
        return lc + rc;
    }
}
 
int N, K;
map<int, int> ma;
 
signed main()
{
    cin >> N >> K;
    REP(i,N) {
        cin >> A[i];
        nums[i] = A[i];
        ma[A[i]] = i;
    }
 
    sort(nums, nums + N);
    init(0, 0, N);
 
    for (int i=K; i<=N; i++) {
        int lb = -1, ub = N - 1;
        while (ub - lb > 1) {
            int md = (ub + lb) / 2;
            int c = query(0, i, nums[md], 0, 0, N);
            if (c >= K) ub = md;
            else lb = md;
        }
        //cout << nums[ub] << endl;
        cout << ma[nums[ub]] + 1 << endl;
        //cout << ub << endl;
    }
}