头像

大沈琢




离线:7小时前


最近来访(42)
用户头像
wjyue2001
用户头像
Lecxcy
用户头像
冷-离
用户头像
Crisp
用户头像
_wyp_
用户头像
五吨重
用户头像
LINE_6
用户头像
停笔醉书情
用户头像
Horseman
用户头像
잘자내여자
用户头像
用户头像
Kai.
用户头像
流苏贺风
用户头像
寂静之主
用户头像
小橘子鸭
用户头像
chen_57
用户头像
不要问我叫什么
用户头像
linjunhao2009
用户头像
@Moli
用户头像
余睿


大沈琢
8小时前

回顾一下 1148. 秘密的牛奶运输

关键是添加一条非树边以后,怎么快速的求出环上的最大和严格次大的树边。
方法如下:
1 随便选一个点做MST的根,我们就选1.
2 预处理三个数组,LCA父节点倍增数组,每个点向上倍增跳,经过边的最大和严格次大。
3 求连接两个点的LCA,然后在跳到LCA的过程中,aggregate两条路径最大和严格次大的边。

容易错的坑:
1 adjList初始化成-1。
2 UF忘记初始化。
3 求最大和次大时,只有当前值小于最大才能去覆盖次大。避免最大和次大是同一个值。

代码贴一下:

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;

const int N = 100010;
const int M = 300010;
const int L = 17;

struct Edge {
    int a, b, c;
    bool treeEdge;
    bool operator< (const Edge &other) const{
        return c < other.c;
    };
} edges[M];

int n, m;

int adjList[N], ne[2*N], e[2*N], w[2*N], idx;

int dp[N][L];
int dist[N][L][2];
int depth[N];

int pa[N];
int find(int x) {
    if (x != pa[x]) {
        pa[x] = find(pa[x]);
    }

    return pa[x];
}

bool isConnected(int x, int y) {
    return find(x) == find(y);
}

void connect(int x, int y) {
    if (isConnected(x, y))
        return;

    pa[find(x)] = find(y);
}

void dfs(int curr, int pa) {
    for (int i = adjList[curr]; ~i; i = ne[i]) {
        int next = e[i];
        int cost = w[i];

        if (next == pa)
            continue;

        depth[next] = depth[curr] + 1;
        dp[next][0] = curr;
        dist[next][0][0] = cost;
        dfs(next, curr);
    }
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = adjList[a];
    adjList[a] = idx++; 
}

void update(int d[2], PII & res) {
    if (d[0] > res.first) {
        res.second = res.first;
        res.first = d[0];

        res.second = max(res.second, d[1]);
    } else if (d[0] < res.first && d[0] > res.second) {
        res.second = d[0];
    }
}

PII lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);

    PII res;
    for (int l = L-1; l >= 0; l--) {
        if (depth[dp[a][l]] >= depth[b]) {
            update(dist[a][l], res);
            a = dp[a][l];
        }
    }

    for (int l = L-1; l >= 0; l--) {
        if (dp[a][l] != dp[b][l]) {
            update(dist[a][l], res);
            update(dist[b][l], res);
            a = dp[a][l];
            b = dp[b][l];
        }
    }

    update(dist[a][0], res);
    update(dist[b][0], res);

    return res;
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    memset(adjList, -1, sizeof adjList);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        pa[i] = i;

    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    }


    sort(edges, edges+m);

    LL mstW = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].c;
        if (isConnected(a, b))
            continue;

        connect(a, b);
        mstW += c;
        edges[i].treeEdge = true;
        add(a, b, c);
        add(b, a, c);
    }

    depth[1] = 1;
    dfs(1, -1);

    for (int l = 1; l < L; l++) {
        for (int i = 1; i <= n; i++) {
            dp[i][l] = dp[dp[i][l-1]][l-1];
        }
    }

    for (int l = 1; l < L; l++) {
        for (int i = 1; i <= n; i++) {
            dist[i][l][0] = dist[i][l-1][0];
            dist[i][l][1] = dist[i][l-1][1];

            if (dist[dp[i][l-1]][l-1][0] > dist[i][l][0]) {
                dist[i][l][1] = dist[i][l][0];
                dist[i][l][0] = dist[dp[i][l-1]][l-1][0];

                dist[i][l][1] = max(dist[i][l][1], dist[dp[i][l-1]][l-1][1]);
            } else if (dist[dp[i][l-1]][l-1][0] < dist[i][l][0] && dist[dp[i][l-1]][l-1][0] > dist[i][l][1]){
                dist[i][l][1] = dist[dp[i][l-1]][l-1][0];
            }
        }
    }

    LL res = LONG_MAX;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].c;

        if (edges[i].treeEdge)
            continue;

        PII p = lca(a, b);

        if (p.first == c) {
            res = min(res, mstW - p.second + c);
        } else {
            res = min(res, mstW - p.first + c);
        }
    }

    cout << res << endl;


    return 0;
}




活动打卡代码 AcWing 356. 次小生成树

大沈琢
8小时前
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;

const int N = 100010;
const int M = 300010;
const int L = 17;

struct Edge {
    int a, b, c;
    bool treeEdge;
    bool operator< (const Edge &other) const{
        return c < other.c;
    };
} edges[M];

int n, m;

int adjList[N], ne[2*N], e[2*N], w[2*N], idx;

int dp[N][L];
int dist[N][L][2];
int depth[N];

int pa[N];
int find(int x) {
    if (x != pa[x]) {
        pa[x] = find(pa[x]);
    }

    return pa[x];
}

bool isConnected(int x, int y) {
    return find(x) == find(y);
}

void connect(int x, int y) {
    if (isConnected(x, y))
        return;

    pa[find(x)] = find(y);
}

void dfs(int curr, int pa) {
    for (int i = adjList[curr]; ~i; i = ne[i]) {
        int next = e[i];
        int cost = w[i];

        if (next == pa)
            continue;

        depth[next] = depth[curr] + 1;
        dp[next][0] = curr;
        dist[next][0][0] = cost;
        dfs(next, curr);
    }
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = adjList[a];
    adjList[a] = idx++; 
}

void update(int d[2], PII & res) {
    if (d[0] > res.first) {
        res.second = res.first;
        res.first = d[0];

        res.second = max(res.second, d[1]);
    } else if (d[0] < res.first && d[0] > res.second) {
        res.second = d[0];
    }
}

PII lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);

    PII res;
    for (int l = L-1; l >= 0; l--) {
        if (depth[dp[a][l]] >= depth[b]) {
            update(dist[a][l], res);
            a = dp[a][l];
        }
    }

    for (int l = L-1; l >= 0; l--) {
        if (dp[a][l] != dp[b][l]) {
            update(dist[a][l], res);
            update(dist[b][l], res);
            a = dp[a][l];
            b = dp[b][l];
        }
    }

    update(dist[a][0], res);
    update(dist[b][0], res);

    return res;
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    memset(adjList, -1, sizeof adjList);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        pa[i] = i;

    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    }


    sort(edges, edges+m);

    LL mstW = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].c;
        if (isConnected(a, b))
            continue;

        connect(a, b);
        mstW += c;
        edges[i].treeEdge = true;
        add(a, b, c);
        add(b, a, c);
    }

    depth[1] = 1;
    dfs(1, -1);

    for (int l = 1; l < L; l++) {
        for (int i = 1; i <= n; i++) {
            dp[i][l] = dp[dp[i][l-1]][l-1];
        }
    }

    for (int l = 1; l < L; l++) {
        for (int i = 1; i <= n; i++) {
            dist[i][l][0] = dist[i][l-1][0];
            dist[i][l][1] = dist[i][l-1][1];

            if (dist[dp[i][l-1]][l-1][0] > dist[i][l][0]) {
                dist[i][l][1] = dist[i][l][0];
                dist[i][l][0] = dist[dp[i][l-1]][l-1][0];

                dist[i][l][1] = max(dist[i][l][1], dist[dp[i][l-1]][l-1][1]);
            } else if (dist[dp[i][l-1]][l-1][0] < dist[i][l][0] && dist[dp[i][l-1]][l-1][0] > dist[i][l][1]){
                dist[i][l][1] = dist[dp[i][l-1]][l-1][0];
            }
        }
    }

    LL res = LONG_MAX;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].c;

        if (edges[i].treeEdge)
            continue;

        PII p = lca(a, b);

        if (p.first == c) {
            res = min(res, mstW - p.second + c);
        } else {
            res = min(res, mstW - p.first + c);
        }
    }

    cout << res << endl;


    return 0;
}




活动打卡代码 AcWing 1171. 距离

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;

const int N = 10010;
const int M = 2 * N;
const int L = 17;

int adjList[N], ne[M], e[M], w[M], idx;
int n, m;

int dp[N][L];
int depth[N], dist[N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = adjList[a];
    adjList[a] = idx++;
}

void dfs(int curr, int pa, int d) {
    if (pa != -1) {
        depth[curr] = depth[pa] + 1; 
        dist[curr] = dist[pa] + d; 
        dp[curr][0] = pa;
    }

    for (int next = adjList[curr]; next != -1; next = ne[next]) {
        if (e[next] == pa)
            continue;

        dfs(e[next], curr, w[next]);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }

    for (int l = L-1; l >= 0; l--) {
        if (depth[dp[a][l]] >= depth[b])
            a = dp[a][l];
    }

    if (a == b)
        return a;

    for (int l = L-1; l >= 0; l--) {
        if (depth[dp[a][l]] == -1)
            continue;

        if (dp[a][l] != dp[b][l]) {
            a = dp[a][l];
            b = dp[b][l];
        }
    }

    return dp[a][0];
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    memset(adjList, -1, sizeof adjList);
    memset(depth, -1, sizeof depth);
    memset(dist, -1, sizeof dist);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    depth[1] = dist[1] = 0;

    dfs(1, -1, 0);

    for (int l = 1; l < L; l++) {
        for (int i = 1; i <= n; i++) {
            dp[i][l] = dp[dp[i][l-1]][l-1];
        }
    }

    while (m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        cout << dist[a] + dist[b] - 2 * dist[p] << endl;
    }

    return 0;
}





我的implementation和y老师的不太一样。

1 我直接开pa数组记录,我的爸爸是谁。
2 我的图是儿子指向爸爸的,y老师是爸爸指向儿子,这两个建图方式都满足拓扑序。
3 我算depth是dfs,因为我是儿子指向爸爸。
4 depth更深的往上爬,爬到一样高,看看是否重合。

坑:
倍增的时候一定要先遍历步数,在遍历点。原因是要把每一个点的往上一步都算好了,才能算往上两步的。

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 40010;
const int L = 20;

int pa[N];
int depth[N];
int n, m;
int dp[N][L];

int dfs(int curr) {
    if (depth[curr] != -1)
        return depth[curr];

    depth[curr] = 1 + dfs(pa[curr]);

    return depth[curr];
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    cin >> n;
    memset(pa, INF, sizeof pa);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        pa[a] = max(0, b);

        dp[a][0] = max(0, b);
    }

    for (int l = 1; l < L; l++) {
        for (int i = 1; i < N; i++) {
            if (pa[i] == INF)
                continue;
            dp[i][l] = dp[dp[i][l-1]][l-1];
        }
    }

    memset(depth, -1, sizeof depth);
    depth[0] = 0;
    for (int i = 0; i < N; i++) {
        if (pa[i] == INF)
            continue;

        dfs(i);
    }

    cin >> m;

    while (m--) {
        int a, b;
        cin >> a >> b;

        if (depth[a] > depth[b]) {
            int pa = a;
            for (int i = L-1; i >= 0; i--) {
                if (depth[dp[pa][i]] >= depth[b])
                    pa = dp[pa][i];
            }

            if (pa == b)
                cout << 2 << endl;
            else 
                cout << 0 << endl;

        } else if (depth[a] < depth[b]) {
            int pb = b;
            for (int i = L-1; i >= 0; i--) {
                if (depth[dp[pb][i]] >= depth[a])
                    pb = dp[pb][i];
            }

            if (a == pb)
                cout << 1 << endl;
            else 
                cout << 0 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 1e9+7;
typedef pair<int, int> PII;
const int N = 40010;
const int L = 20;

int pa[N];
int depth[N];
int n, m;
int dp[N][L];

int dfs(int curr) {
    if (depth[curr] != -1)
        return depth[curr];

    depth[curr] = 1 + dfs(pa[curr]);

    return depth[curr];
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    cin >> n;
    memset(pa, INF, sizeof pa);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        pa[a] = max(0, b);

        dp[a][0] = max(0, b);
    }

    for (int l = 1; l < L; l++) {
        for (int i = 1; i < N; i++) {
            if (pa[i] == INF)
                continue;
            dp[i][l] = dp[dp[i][l-1]][l-1];
        }
    }

    memset(depth, -1, sizeof depth);
    depth[0] = 0;
    for (int i = 0; i < N; i++) {
        if (pa[i] == INF)
            continue;

        dfs(i);
    }

    cin >> m;

    while (m--) {
        int a, b;
        cin >> a >> b;

        if (depth[a] > depth[b]) {
            int pa = a;
            for (int i = L-1; i >= 0; i--) {
                if (depth[dp[pa][i]] >= depth[b])
                    pa = dp[pa][i];
            }

            if (pa == b)
                cout << 2 << endl;
            else 
                cout << 0 << endl;

        } else if (depth[a] < depth[b]) {
            int pb = b;
            for (int i = L-1; i >= 0; i--) {
                if (depth[dp[pb][i]] >= depth[a])
                    pb = dp[pb][i];
            }

            if (a == pb)
                cout << 1 << endl;
            else 
                cout << 0 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}




活动打卡代码 AcWing 1053. 修复DNA

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 3;
typedef pair<int, int> PII;

const int N = 1010;

int trie[N][4], fail[N], cnt[N];
int idx;
int dp[N][N];

string p;
int charToId[26];
string idToChar = "AGCT";  

void add(string & str) {
    int curr = 0;
    for (char c : str) {
        int i = charToId[c - 'A'];
        if (trie[curr][i] == 0)
            trie[curr][i] = ++idx;

        curr = trie[curr][i];
    }

    cnt[curr] = 1;
    // cout << curr << " " << endl;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 4; i++) {
        if (trie[0][i])
            q.push(trie[0][i]);
    }

    while (q.size()) {
        int pa = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            if (trie[pa][i]) {
                q.push(trie[pa][i]);
                fail[trie[pa][i]] = trie[fail[pa]][i];
                if (cnt[fail[trie[pa][i]]])
                    cnt[trie[pa][i]] = 1;
            } else {
                trie[pa][i] = trie[fail[pa]][i];
            }
        }
    }
}

int dfs(int node, int pos) {
    if (pos >= p.size())
        return 0;

    if (dp[node][pos] != INF)
        return dp[node][pos];

    for (int i = 0; i < 4; i++) {
        if (cnt[trie[node][i]])
            continue;

        int cost = idToChar[i] != p[pos];
        dp[node][pos] = min(dp[node][pos], cost + dfs(trie[node][i], pos+1));
    }

    return dp[node][pos];
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    charToId['A' - 'A'] = 0; 
    charToId['G' - 'A'] = 1; 
    charToId['C' - 'A'] = 2; 
    charToId['T' - 'A'] = 3;

    int caseN = 1;
    while (true) {
        idx = 0;
        memset(trie, 0, sizeof trie);
        memset(cnt, 0, sizeof cnt);
        memset(fail, 0, sizeof fail);
        memset(dp, INF, sizeof dp);
        int n;
        cin >> n;
        if (n == 0)
            break;

        for (int i = 0; i < n; i++) {
            string t;
            cin >> t;
            add(t);
        }

        build();

        cin >> p;  

        int res = dfs(0, 0);

        if (res == INF) 
            cout << "Case " << caseN++ << ": -1" << endl;
        else
            cout << "Case " << caseN++ << ": " << res << endl;

    }

    return 0;
}




活动打卡代码 AcWing 1285. 单词

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 3;
typedef pair<int, int> PII;

const int N = 1000010;

int trie[N][26], fail[N];
int cnt[N];
int idx;

vector<string> words;
vector<int> nodeIdxByLvl;

void add(string & str) {
    int curr = 0;
    for (char c : str) {
        int i = c - 'a';
        if (trie[curr][i] == 0) 
            trie[curr][i] = ++idx;

        curr = trie[curr][i];
        cnt[curr]++;
    }
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (trie[0][i]) {
            q.push(trie[0][i]);
        }
    }

    while (q.size()) {
        int pa = q.front();
        q.pop();

        nodeIdxByLvl.push_back(pa);
        for (int i = 0; i < 26; i++) {
            if (trie[pa][i] == 0) {
                trie[pa][i] = trie[fail[pa]][i];
            } else {
                fail[trie[pa][i]] = trie[fail[pa]][i];
                q.push(trie[pa][i]);
            }
        }
    }
}

int query(string & str) {
    int curr = 0;
    for (char c : str) {
        curr = trie[curr][c - 'a'];
    }

    return cnt[curr];
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    int n;
    cin >> n;
    while (n--) {
        string str;
        cin >> str;
        words.push_back(str);
        add(str);
    }

    build();

    for (int i = nodeIdxByLvl.size() - 1; i >= 0; i--) {
        cnt[fail[nodeIdxByLvl[i]]] += cnt[nodeIdxByLvl[i]];
    }

    for (auto & w : words) 
        cout << query(w) << endl;

    return 0;
}



活动打卡代码 AcWing 1282. 搜索关键词

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 3;
typedef pair<int, int> PII;

const int N = 50 * 10010;

int trie[N][26];
int fail[N], cnt[N];
int idx;
int n;

void add(string & p) {
    int curr = 0;
    for (char c : p) {
        int i = c - 'a';

        if (trie[curr][i] == 0) 
            trie[curr][i] = ++idx;

        curr = trie[curr][i];
    }

    cnt[curr]++;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (trie[0][i]) 
            q.push(trie[0][i]);
    }

    while (q.size()) {
        int pa = q.front();
        q.pop();

        for (int i = 0; i < 26; i++) {
            if (trie[pa][i]) {
                fail[trie[pa][i]] = trie[fail[pa]][i];
                q.push(trie[pa][i]);
            }
            else {
                trie[pa][i] = trie[fail[pa]][i];
            }
        }
    }
}

int query(string & str) {
    int curr = 0, res = 0;
    for (char c : str) {
        int i = c - 'a';

        curr = trie[curr][i];

        int f = curr;
        while (f) {
            res += cnt[f];
            cnt[f] = 0;
            f = fail[f];
        }
    }

    return res;
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    int t;
    cin >> t;
    while (t--) {
        memset(trie, 0, sizeof trie);
        memset(fail, 0, sizeof fail);
        memset(cnt, 0, sizeof cnt);
        idx = 0;
        cin >> n;

        while (n--) {
            string p;
            cin >> p;

            add(p);
        }

        build();

        string t;
        cin >> t;

        cout << query(t) << endl;
    }

    return 0;
}



大沈琢
14天前

这篇题解已经写的非常好了,我再啰嗦几句自己的体会。

可持久化的思想就是保存每一个版本,我们用两个指针,一个指向当前版本,一个指向前一个版本。然后两个两个指针一起动。

首先要搞明白什么是权值线段树,就是按照值域来存每个数的cnt,所以要离散化。

以前的线段树都是直接开4倍数组,树的结构是静态的,根是x,儿子是2x和2x+1。线段树节点里面的lr存的是原来数组的区间。

主席树必须动态开点,也就是lr表示的是左右儿子节点的index,权值边界是从参数传进去的。

y老师说主席树不好支持区间修改,我就当知识点记住了。

建好主席树以后,区间最第k小数是运用前缀和的思想,我们把版本r和版本l-1每一个结点的size对位相减就能得到l到r之间这个数出现的个数,然后就是基本的第k大数搜索。

int build(int l, int r) {
    // 这里一定要要把idx存下来,因为在递归的过程中idx会变化。
    // 这个坑卡了好久
    int q = ++idx;
    if (l == r) {
        return q;
    }

    int mid = l + r >> 1;
    tr[q].l = build(l, mid);
    tr[q].r = build(mid+1, r);

    return q;
}


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

大沈琢
14天前
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 3;
typedef pair<int, int> PII;

const int N = 100010;

struct Node {
    int l, r;
    int size = 0;
} tr[20*N];

int n, m;
int arr[N];
vector<int> dedup;
unordered_map<int, int> hashmap;
int idx;

int root[N];

void pushup(int u) {
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size;
}

int build(int l, int r) {
    int q = ++idx;
    if (l == r) {
        return q;
    }

    int mid = l + r >> 1;
    tr[q].l = build(l, mid);
    tr[q].r = build(mid+1, r);

    return q;
}

int update(int l, int r, int p, int num) {
    int q = ++idx;
    if (l == r) {
        tr[q].size = 1;
        return q;
    }

    int mid = l + r >> 1;
    if (num <= mid) {
        tr[q].l = update(l, mid, tr[p].l, num);
        tr[q].r = tr[p].r;
    } else {
        tr[q].l = tr[p].l;
        tr[q].r = update(mid+1, r, tr[p].r, num);
    }

    pushup(q);
    return q;
}

int query(int p, int q, int l, int r, int size) {
    if (l == r) {
        return r;
    }

    int lsize = tr[tr[q].l].size - tr[tr[p].l].size;
    int mid = l + r >> 1;

    if (lsize >= size) {
        return query(tr[p].l, tr[q].l, l, mid, size);
    } else {
        return query(tr[p].r, tr[q].r, mid+1, r, size - lsize);
    }
}

int main() {

    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dedup.push_back(arr[i]);
    }

    sort(dedup.begin(), dedup.end());
    dedup.erase(unique(dedup.begin(), dedup.end()), dedup.end());

    for (int i = 0; i < dedup.size(); i++) 
        hashmap[dedup[i]] = ++idx;

    int len = idx;
    idx = 0;
    root[0] = build(1, len);
    for (int i = 1; i <= n; i++) {
        root[i] = update(1, len, root[i-1], hashmap[arr[i]]);
    }

    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;

        int res = query(root[a-1], root[b], 1, len, c);
        cout << dedup[res-1] << endl;
    }

    return 0;
}