听灌多
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/12/11 19:10
  • 上次更新2024/12/11 22:11:04
查看原帖
听灌多
608410
封禁用户楼主2024/12/11 19:10

为什么用Root这个变量名就会wa,而用rt就过了

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 2e5 + 5;

int tot;
int a[maxn], b[maxn];
int root[maxn], L[maxn << 5], R[maxn << 5], sum[maxn << 5];

int n, m, Root;

int build(int l, int r) {
	int rt = ++tot;
	int mid = l + r >> 1;
	if (l < r) {
		L[rt] = build(l, mid);
		R[rt] = build(mid + 1, r);
	}
	return rt;
}

int update(int pre, int l, int r, int x) {
//上一个节点,左,右, 该点编号
    Root = ++tot;
    L[Root] = L[pre], R[Root] = R[pre];sum[Root] = sum[pre] + 1;
    if (l < r) {
    	int mid = l + r >> 1;
    	if (x <= mid) L[Root] = update(L[pre], l, mid, x);
    	else R[Root] = update(R[pre], mid + 1, r, x);
	}
    
//    if (l >= r) return Root;
//    int mid = l + r >> 1/*l + ((r - l) >> 1)*/;
//    if (x <= mid) L[Root] = update(L[pre], l, mid, x);
//    else R[Root] = update(R[pre], mid + 1, r, x);
    return Root;
}

int query(int u, int v, int l, int r, int k) {
    if (l >= r) return l;
    int x = sum[L[v]] - sum[L[u]];
    int mid = l + r >> 1/*l + ((r - l) >> 1)*/;
    if (x >= k) return query(L[u], L[v], l, mid, k);
    else return query(R[u], R[v], mid + 1, r, k - x);
}

int main() {
    n = read(), m = read();
//	scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;i++) b[i] = a[i] = read();
//	for (int i = 1;i <= n;i++) {
//		scanf("%d", &a[i]);b[i] = a[i];
//	}

    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    
    root[0] = build(1, len);

    for (int i = 1;i <= n;i++) {
        int x = lower_bound(b + 1, b + 1 + len, a[i]) - b;
        root[i] = update(root[i - 1], 1, len, x);
    }
    
//    cerr << 114514 << '\n';

    while (m--) {
        int x = read(), y = read(), k = read();
//		int x, y, k;scanf("%d%d%d", &x, &y, &k);
        write(b[query(root[x - 1], root[y], 1, len, k)]);puts("");//puts!!!!!111
    }

    return 0;
}
2024/12/11 19:10
加载中...