头像

心里没有一点AC数

LZU / NetEase/ www.fogsail.net


访客:16780

离线:19小时前


新鲜事 原文

点分树计数问题切的我好他妈累啊~ 归根结底还是自己智商不行
图片 图片 图片


新鲜事 原文

Todo List: 1. 树上分治:点分治,边分治(边分治经常和虚树一起乱搞),动态点分治 2. 树上的各种问题,虚树,替罪羊树式树合并


新鲜事 原文

我要是智商高一点就好了


活动打卡代码 AcWing 268. 流星

Acwing268-01.jpg
Acwing268-02.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

// ============================================================== //

const int maxn = 3 * 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int K = 0;
vector<int> vec[maxn];

class BIU {
public:
    int id;
    ll val;
    BIU() {}
    BIU(int id, ll val) : id(id), val(val) {}
} P[maxn], pl[maxn], pr[maxn];

class Met {
public:
    int l, r;
    ll a;
    Met() {}
    Met(int l, int r, ll a) : l(l), r(r), a(a) {}
} A[maxn];

class Fwick {
public:
    ll C[maxn];
    int n;

    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, ll d) {
        for(; x <= m; x += lowbit(x)) C[x] += d;
    }

    ll ask(int x) {
        ll ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void get(int k, int sgn) {
    ll val = sgn * A[k].a;

    if(A[k].l <= A[k].r) {
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
    else {
        fwick.add(1, val);
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
}

ll ans[maxn];

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) ans[P[i].id] = lval;
        return;
    }

    int mid = (lval + rval) >> 1;
    int lt = 0, rt = 0;

    _rep(i, lval, mid) get(i, 1);
    _rep(i, st, ed) {
        // P[i].id is cur BIU
        ll tot = 0;
        for(auto x : vec[P[i].id]) {
            tot += fwick.ask(x);
            if(tot > P[i].val) break;
        }

        if(tot >= P[i].val) pl[++lt] = P[i];
        else {
            P[i].val -= tot;
            pr[++rt] = P[i];
        }
    }

    _rep(i, lval, mid) get(i, -1);

    _rep(i, 1, lt) P[st + i - 1] = pl[i];
    _rep(i, 1, rt) P[st + lt + i - 1] = pr[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    init();
    // get data
    _rep(i, 1, m) {
        int o;
        scanf("%d", &o);
        vec[o].push_back(i);
    }
    _rep(i, 1, n) {
        P[i].id = i;
        scanf("%lld", &P[i].val);
    }
    scanf("%d", &K);
    _rep(i, 1, K) {
        int l, r;
        ll a;
        scanf("%d%d%lld", &l, &r, &a);
        A[i] = Met(l, r, a);
    }
    A[++K] = Met(1, m, inf);

    // then solve the problem
    fwick._init(maxn);

    solve(1, K, 1, n);

    _rep(i, 1, n) ans[i] == K ? puts("NIE") : printf("%lld\n", ans[i]);
}



Acwing268-01.jpg
Acwing268-02.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

// ============================================================== //

const int maxn = 3 * 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int K = 0;
vector<int> vec[maxn];

class BIU {
public:
    int id;
    ll val;
    BIU() {}
    BIU(int id, ll val) : id(id), val(val) {}
} P[maxn], pl[maxn], pr[maxn];

class Met {
public:
    int l, r;
    ll a;
    Met() {}
    Met(int l, int r, ll a) : l(l), r(r), a(a) {}
} A[maxn];

class Fwick {
public:
    ll C[maxn];
    int n;

    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, ll d) {
        for(; x <= m; x += lowbit(x)) C[x] += d;
    }

    ll ask(int x) {
        ll ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void get(int k, int sgn) {
    ll val = sgn * A[k].a;

    if(A[k].l <= A[k].r) {
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
    else {
        fwick.add(1, val);
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
}

ll ans[maxn];

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) ans[P[i].id] = lval;
        return;
    }

    int mid = (lval + rval) >> 1;
    int lt = 0, rt = 0;

    _rep(i, lval, mid) get(i, 1);
    _rep(i, st, ed) {
        // P[i].id is cur BIU
        ll tot = 0;
        for(auto x : vec[P[i].id]) {
            tot += fwick.ask(x);
            if(tot > P[i].val) break;
        }

        if(tot >= P[i].val) pl[++lt] = P[i];
        else {
            P[i].val -= tot;
            pr[++rt] = P[i];
        }
    }

    _rep(i, lval, mid) get(i, -1);

    _rep(i, 1, lt) P[st + i - 1] = pl[i];
    _rep(i, 1, rt) P[st + lt + i - 1] = pr[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    init();
    // get data
    _rep(i, 1, m) {
        int o;
        scanf("%d", &o);
        vec[o].push_back(i);
    }
    _rep(i, 1, n) {
        P[i].id = i;
        scanf("%lld", &P[i].val);
    }
    scanf("%d", &K);
    _rep(i, 1, K) {
        int l, r;
        ll a;
        scanf("%d%d%lld", &l, &r, &a);
        A[i] = Met(l, r, a);
    }
    A[++K] = Met(1, m, inf);

    // then solve the problem
    fwick._init(maxn);

    solve(1, K, 1, n);

    _rep(i, 1, n) ans[i] == K ? puts("NIE") : printf("%lld\n", ans[i]);
}


活动打卡代码 AcWing 89. a^b

快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, ll n, ll p) {
    ll ans = 1 % p;
    for(; n; n >>= 1) {
        if(n & 1) ans = (ans * 1ll * a) % p;
        a = a * a % p;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

// ============================================================== //

ll a, b, p;

int main() {
    ///freopen("input.txt", "r", stdin);
    cin >> a >> b >> p;

    ll ans = qpow(a, b, p);
    cout << ans << endl;
}



快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, ll n, ll p) {
    ll ans = 1 % p;
    for(; n; n >>= 1) {
        if(n & 1) ans = (ans * 1ll * a) % p;
        a = a * a % p;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

// ============================================================== //

ll a, b, p;

int main() {
    ///freopen("input.txt", "r", stdin);
    cin >> a >> b >> p;

    ll ans = qpow(a, b, p);
    cout << ans << endl;
}


活动打卡代码 AcWing 264. 权值

$\textbf{algorithm}$
$\textbf{i) solve}(x, \text{ans})$
$\quad \quad \text{dep}(x) = 0, \text{vis}(x) = 1$
$\quad \quad \textbf{cal}(x, ans)$
$\quad \quad \textbf{for } \forall y \in son(x)$
$\quad \quad \quad root \leftarrow getRoot(), \textbf{solve}(root, ans)$

$\textbf{ii) cal}(x, y), \text{难点在于cal的计算}$

Acwing264.jpg

$\textbf{用 vec1}[\cdots] \textbf{ 维护 D}[\cdots], \textbf{vec2}[\cdots] \textbf{ 维护 dep}[\cdots]$

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int N, K;

// == Graph definition ==
int m = 0;

class Edge {
public:
    int to, weight;
    Edge *next;

    Edge() {}
    Edge(int to, int w) : to(to), weight(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void initG() {
    m = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++m] = Edge(v, w);
    edges[m].next = head[u];
    head[u] = &edges[m];
}
// == Graph finished ==

// == get root ==
int root = 0;
int sn = N;
int sz[maxn];
int vis[maxn];

void getRoot(int x, int pa, int &res) {
    sz[x] = 1;

    int maxpart = 0;
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);

        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);

    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}
// == get root finished ==

// == solve ==
int dep[maxn];
int D[maxn];
int dp[maxn];

void dfs(int x, int pa, vector<int> &vec1, vector<int> &vec2) {
    vec1.push_back(D[x]);
    vec2.push_back(dep[x]);
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y] || y == pa) continue;

        dep[y] = dep[x] + 1;
        D[y] = D[x] + w;

        if(D[y] <= 1e6) dfs(y, x, vec1, vec2);
    }
}

queue<int> que;
void cal(int x, int &ans) {
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y]) continue;

        vector<int> vec1, vec2;
        dep[y] = dep[x] + 1;
        D[y] = D[x] + w;
        dfs(y, x, vec1, vec2);

        _for(i, 0, vec1.size()) {
            if(K >= vec1[i]) ans = min(ans, dp[K - vec1[i]] + vec2[i]);
        }

        _for(i, 0, vec1.size()) {
            que.push(vec1[i]);
            dp[vec1[i]] = min(dp[vec1[i]], vec2[i]);
        }
    }
    while (que.size()) {
        dp[que.front()] = inf;
        que.pop();
    }
}

void solve(int x, int &ans) {
    vis[x] = 1;
    dep[x] = 0;
    D[x] = 0;
    dp[0] = 0;

    cal(x, ans);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y]) continue;

        sn = sz[y];
        root = 0;
        int res = inf;
        getRoot(y, x, res);

        solve(root, ans);
    }
}
// == solve finished ==

void init() {
    root = 0;
    sn = N;
    Set(sz, 0);
    Set(vis, 0);
    Set(dep, 0);
    Set(D, 0);
    Set(dp, inf);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &K);
    initG();
    init();

    _for(i, 1, N) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u++; v++;
        add(u, v, w);
        add(v, u, w);
    }

    // then solve the problem
    int res = inf;
    getRoot(1, -1, res);
    int ans = inf;
    solve(root, ans);

    if(ans == inf) printf("-1\n");
    else printf("%d\n", ans);
}


活动打卡代码 AcWing 255. 第K个数

merge01.jpg
merge02.jpg
merge03.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

// ============================================================================= //

const int maxn = 1e5 + 10;
const int inf = 1e9;
int N, M;
int n = 0, tot = 0;
int ans[maxn];

// == discrete ==
int a[maxn], b[maxn];

void discrete() {
    sort(b + 1, b + 1 + N);
    n = unique(b + 1, b + 1 + N) - b - 1;
    _rep(i, 1, N) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
}
// original: b[a[i]], a in [1, n]
// == discrete finished ==

class Qry {
public:
    int x, y, z;
    int op;
    Qry() {}
    Qry(int x, int y, int z) : x(x), y(y), z(z) {}
    Qry(int x, int y) : x(x), y(y) {}
} qry[maxn << 1], lqry[maxn << 1], rqry[maxn << 1];

class Fwick {
public:
    int C[maxn];
    int n;
    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, int y) {
        for(; x <= n; x += lowbit(x)) C[x] += y;
    }

    int ask(int x) {
        int ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) {
            if(qry[i].op > 0) ans[qry[i].op] = b[lval];
        }
        return;
    }

    int mid = (lval + rval) >> 1;

    int lt = 0, rt = 0;
    _rep(i, st, ed) {
        if(qry[i].op == 0) {
            // x -> y
            if(qry[i].y <= mid) {
                fwick.add(qry[i].x, 1);
                lqry[++lt] = qry[i];
            }
            else rqry[++rt] = qry[i];
        }
        else {
            int cnt = fwick.ask(qry[i].y) - fwick.ask(qry[i].x - 1);
            if(cnt >= qry[i].z) lqry[++lt] = qry[i];
            else {
                qry[i].z -= cnt;
                rqry[++rt] = qry[i];
            }
        }
    }

    _rep(i, st, ed) {
        if(qry[i].op == 0 && qry[i].y <= mid) fwick.add(qry[i].x, -1);
    }

    _rep(i, 1, lt) qry[st + i - 1] = lqry[i];
    _rep(i, 1, rt) qry[st + lt + i - 1] = rqry[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    n = 0;
    tot = 0;
    memset(ans, 0, sizeof(ans));
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    init();

    // == get data ==
    _rep(i, 1, N) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    discrete();
    // == get data finished ==

    // == get query ==
    _rep(i, 1, N) {
        qry[++tot] = Qry(i, a[i]);
        qry[tot].op = 0;
    }

    _rep(i, 1, M) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        qry[++tot] = Qry(l, r, k);
        qry[tot].op = i;
    }
    // == query finished ==

    // then solve the problem
    fwick._init(n + 1);
    solve(1, n, 1, tot);

    _rep(i, 1, M) printf("%d\n", ans[i]);
}



整体二分

merge01.jpg
merge02.jpg
merge03.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

// ============================================================================= //

const int maxn = 1e5 + 10;
const int inf = 1e9;
int N, M;
int n = 0, tot = 0;
int ans[maxn];

// == discrete ==
int a[maxn], b[maxn];

void discrete() {
    sort(b + 1, b + 1 + N);
    n = unique(b + 1, b + 1 + N) - b - 1;
    _rep(i, 1, N) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
}
// original: b[a[i]], a in [1, n]
// == discrete finished ==

class Qry {
public:
    int x, y, z;
    int op;
    Qry() {}
    Qry(int x, int y, int z) : x(x), y(y), z(z) {}
    Qry(int x, int y) : x(x), y(y) {}
} qry[maxn << 1], lqry[maxn << 1], rqry[maxn << 1];

class Fwick {
public:
    int C[maxn];
    int n;
    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, int y) {
        for(; x <= n; x += lowbit(x)) C[x] += y;
    }

    int ask(int x) {
        int ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) {
            if(qry[i].op > 0) ans[qry[i].op] = b[lval];
        }
        return;
    }

    int mid = (lval + rval) >> 1;

    int lt = 0, rt = 0;
    _rep(i, st, ed) {
        if(qry[i].op == 0) {
            // x -> y
            if(qry[i].y <= mid) {
                fwick.add(qry[i].x, 1);
                lqry[++lt] = qry[i];
            }
            else rqry[++rt] = qry[i];
        }
        else {
            int cnt = fwick.ask(qry[i].y) - fwick.ask(qry[i].x - 1);
            if(cnt >= qry[i].z) lqry[++lt] = qry[i];
            else {
                qry[i].z -= cnt;
                rqry[++rt] = qry[i];
            }
        }
    }

    _rep(i, st, ed) {
        if(qry[i].op == 0 && qry[i].y <= mid) fwick.add(qry[i].x, -1);
    }

    _rep(i, 1, lt) qry[st + i - 1] = lqry[i];
    _rep(i, 1, rt) qry[st + lt + i - 1] = rqry[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    n = 0;
    tot = 0;
    memset(ans, 0, sizeof(ans));
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    init();

    // == get data ==
    _rep(i, 1, N) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    discrete();
    // == get data finished ==

    // == get query ==
    _rep(i, 1, N) {
        qry[++tot] = Qry(i, a[i]);
        qry[tot].op = 0;
    }

    _rep(i, 1, M) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        qry[++tot] = Qry(l, r, k);
        qry[tot].op = i;
    }
    // == query finished ==

    // then solve the problem
    fwick._init(n + 1);
    solve(1, n, 1, tot);

    _rep(i, 1, M) printf("%d\n", ans[i]);
}