(セグメント木・ラムダ式)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;
}

(セグメント木・区間加算区間和・遅延評価)AOJ-DSL_2-G-Range Query – RSQ and RAQ

問題URL→http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G&lang=jp

このブログを見て遅延評価セグメント木を実装した。

タイトル通り、この実装では区間加算と区間和のクエリに対応している。

//*
#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 LazySegmentTree
{
private:
    int n;
    vector<ll> node, lazy;

public:
    //初期化
    LazySegmentTree(vector<ll> v)
    {
        int sz = (int)v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i=0; i<sz; i++) node[i+(n-1)] = v[i];
        for (int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    //k番目のノードについて遅延評価を行う
    void eval(int k, int l, int r)
    {
        //遅延配列が空でない場合、自ノード及び子ノードへの
        //値の伝播が起こる
        if (lazy[k] != 0) {
            node[k] += lazy[k];

            //最下段かどうかのチェックをする
            //子ノードは親ノードの1/2の範囲であるため、
            //伝播させるときは半分にする
            if (r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }

            //伝播が終わったので、自ノードの遅延配列を空にする
            lazy[k] = 0;
        }
    }

    //区間加算
    void add(int a, int b, ll x, int k=0, int l=0, int r=-1)
    {
        if (r < 0) r = n;

        //k番目のノードに対して遅延評価を行う
        eval(k, l, r);

        //範囲外なら何もしない
        if (b <= l || r <= a) return;

        //完全に被覆しているならば、遅延配列に値を入れた後に評価
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }

        //そうでないならば、子ノードの値を再帰的に計算して、
        //計算済みの値をもらってくる
        else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    //区間和の取得
    ll getsum(int a, int b, int k=0, int l=0, int r=-1)
    {
        if (r < 0) r = n;

        //関数が呼び出されたらまず評価
        eval(k, l, r);

        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

signed main()
{
    int n, q;

    cin >> n >> q;
    vector<ll> a(n, 0);
    LazySegmentTree lst(a);

    REP(i,q) {
        int type;
        cin >> type;
        if (type == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            lst.add(s - 1, t, x);
        } else {
            int s, t;
            cin >> s >> t;
            cout << lst.getsum(s - 1, t) << endl;
        }
    }
}

(セグメント木・Range Sum Query・RSQ)AOJ-DSL_2-B-Range Query – Range Sum Query (RSQ)

問題URL→http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp

数列のある区間の和を取得できるようにした。
また更新クエリは数列のある項をupdateするメソッドと、ある項にある値を加算するaddメソッドを用意した。

//*
#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;


//Range Sum Query(RSQ)を処理するセグ木
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, 0);

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

    //★追加
    void add(int k, int val)
    {
        k += n - 1;
        node[k] += val;

        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    //要求区間[a,b)の要素の最小値を答える
    //k:=自分がいるノードのインデックス
    //対象区間は[l,r)にあたる
    int getsum(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 0;

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

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

signed main()
{
    int n, q;

    cin >> n >> q;
    vector<int> a(n, 0);

    SegmentTree st(a);
    REP(i,q) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            st.add(x - 1, y);
        } else {
            cout << st.getsum(x - 1, y) << endl;
        }
    }
}

(セグメント木・RMQ)AOJ-DSL_2-A-Range Query – Range Minimum Query (RMQ)

問題URL→http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp

つたじろうさんのこのブログを参考にセグメント木(RMQ)を書いた。

たぶん一番丁寧に書いた(コメントも大量に書いた)コード。

あとINFの定義をdefine int long longしてあるかで切り替えるようにした。
それと定数リテラルはint型なので大きい値になるときはLLを付けないといけないことに注意。

//*
#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);
    }
};

signed main()
{
    int n, q;

    cin >> n >> q;
    vector<int> a(n, (1LL << 31) - 1);

    SegmentTree st(a);
    REP(i,q) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com == 0) {
            st.update(x, y);
        } else {
            cout << st.getmin(x, y + 1) << endl;
        }
    }
}

(区間add区間和セグメント木)POJ-3468-A Simple Problem with Integers

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

蟻本に載っている問題。
区間に対してある値を加える操作と、区間の和を求める操作を実現したセグメント木を実装した。

/*
#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
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
const int INF = 1e9;
const ll LLINF = LLONG_MAX / 10;
typedef pair<int, int> P;
//typedef pair<double, double> P;

const int MAX_N = 101010;
const int MAX_Q = 101010;
const int DAT_SIZE = (1 << 18) - 1;

int N, Q;
int A[MAX_N];
char T[MAX_Q];
int L[MAX_Q], R[MAX_Q], X[MAX_Q];

//セグメント木本体
ll data[DAT_SIZE], datb[DAT_SIZE];

//[a,b)にxを加算する(最初は0)
//kは節点の番号で、区間[l,r)に対応する
void add(int a, int b, int x, int k, int l, int r)
{
    if (a <= l && r <= b) {
        //今見ている区間が加算する区間にすっぽり入っていた場合
        data[k] += x;
    } else if (l < b && a < r) {
        //今見ている区間が加算する区間と交差している場合
        datb[k] += (min(b, r) - max(a, l)) * x;
        add(a, b, x, k * 2 + 1, l, (l + r) / 2);
        add(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
}

//[a,b)の和を計算する
//kは節点の番号で、区間[l,r)に対応する
ll sum(int a, int b, int k, int l, int r)
{
    if (b <= l || r <= a) {
        return 0;
    } else if (a <= l && r <= b) {
        return data[k] * (r - l) + datb[k];
    } else {
        ll res = (min(b, r) - max(a, l)) * data[k];
        res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
        res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
        return res;
    }
}

signed main()
{
    //cin >> N >> Q;
    scanf("%lld %lld", &N, &Q);
    REP(i,N) {
        //cin >> A[i];
        scanf("%lld", &A[i]);
        add(i, i + 1, A[i], 0, 0, N);
    }
    REP(i,Q) {
        //cin >> T[i];
        scanf("\n%c", &T[i]);
        if (T[i] == 'C') {
            //cin >> L[i] >> R[i] >> X[i];
            scanf("%lld %lld %lld", &L[i], &R[i], &X[i]);
            add(L[i] - 1, R[i], X[i], 0, 0, N);
        } else {
            //cin >> L[i] >> R[i];
            scanf("%lld %lld", &L[i], &R[i]);
            cout << sum(L[i] - 1, R[i], 0, 0, N) << endl;
        }
    }
}

(セグメント木・行列積)yukicoder-No.510-二次漸化式

問題URL→https://yukicoder.me/problems/no/510

クエリで要素が書き換わる行列の積を高速に計算できればとける。
ノードに行列を持たせたセグメント木を作ることによりそれが可能となる。

#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 REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1e9;

//行列Aと行列Bの積を返す
mat f(mat A, mat B)
{
    mat C(A.size(), vec(B[0].size()));
    REP(i,A.size()) REP(j,B[0].size()) {
        REP(k,A[0].size()) {
            C[i][j] += (A[i][k] * B[k][j]) % MOD;
            C[i][j] %= MOD;
        }
    }
    return C;
}

mat defvalue(4, vec(4)), defvalue2(4, vec(4));

class SegTree
{
private:
    int n;
    vector<mat> val;

public:
    SegTree(int size)
    {
        n = 1;
        while (n < size) n <<= 1;
        val = vector<mat>(2 * n, defvalue);
    }

    void update(int q, int i, int a)
    {
        i += n - 1;
        if (q == 0) {
            val[i][0][2] = a;
        } else {
            val[i][1][1] = a;
            val[i][2][1] = 2 * a;
            val[i][2][2] = a * a % MOD;
        }
        while (i > 0) {
            i = (i - 1) / 2;
            val[i] = f(val[i * 2 + 2],val[i * 2 + 1]);
        }
    }

    mat query(int a, int b, int k = 0, int l = 0, int r = - 1)
    {
        if (r == -1) r = n;
        if (r <= a || b <= l) return defvalue2;
        if (a <= l && r <= b) return val[k];
        else return f(query(a, b, k * 2 + 2, (l + r) / 2, r),
                      query(a, b, k * 2 + 1, l, (l + r) / 2));
    }
};

int n, q;

signed main()
{
    cin >> n >> q;

    defvalue[0][0] = defvalue[1][3] = defvalue[2][3] = defvalue[3][3] = 1;
    defvalue2[0][0] = defvalue2[1][1] = defvalue2[2][2] = defvalue2[3][3] = 1;

    SegTree st(n + 1);
    while (q--) {
        int a, b;
        char c;

        cin >> c;
        if (c == 'x') {
            cin >> a >> b;
            st.update(0, a, b);
        } else if (c == 'y') {
            cin >> a >> b;
            st.update(1, a, b);
        } else if (c == 'a') {
            cin >> a;
            mat t = st.query(0, a);
            cout << (t[0][0]+t[0][1]+t[0][2]+t[0][3]) % MOD << 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;
    }
}