本文共 3057 字，大约阅读时间需要 10 分钟。
裸的区间第k大问题，划分树搞起。
#pragma comment(linker, "/STACK:10240000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define X first#define Y second#define pb push_back#define mp make_pair#define all(a) (a).begin(), (a).end()#define fillchar(a, x) memset(a, x, sizeof(a))#define fillarray(a, b) memcpy(a, b, sizeof(a))typedef long long ll;typedef pair pii;typedef unsigned long long ull;#ifndef ONLINE_JUDGEvoid RI(vector &a,int n){a.resize(n);for(int i=0;i void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){ int d=p void print(const T t){cout< < void print(const F f,const R...r){cout< <<", ";print(r...);}template void print(T*p, T*q){ int d=p <<*p<<", ";p+=d;}cout< bool umax(T&a, const T&b){ return b<=a?false:(a=b,true);}template bool umin(T&a, const T&b){ return b>=a?false:(a=b,true);}const double PI = acos(-1.0);const int INF = 1e9 + 7;const double EPS = 1e-12;/* -------------------------------------------------------------------------------- */const int maxn = 1e5 + 7;/** 过程：快排的过程，通过记录进入左子区间的个数的前缀和来解决区间第k大问题 **/class PartitionTree { int cnt[20][maxn], val[20][maxn], buf[maxn]; int n; void init(int a[], int n) { this->n = n; fillchar(cnt, 0); fillchar(val, 0); fillarray(val[0], a); fillarray(buf, a); sort(buf, buf + n); } void build(int l, int r, int dep) { if (l == r) return ; int m = (l + r) >> 1, c = 0, small = 0; for (int i = l; i <= r; i ++) small += val[dep][i] < buf[m]; for (int i = l; i <= r; i ++) { if (c < m - l + 1) { if (val[dep][i] < buf[m] || val[dep][i] == buf[m] && small < m - l + 1) { cnt[dep][i] = 1; val[dep + 1][l + c ++] = val[dep][i]; small += val[dep][i] == buf[m]; } } else break; } for (int i = l; i <= r; i ++) { if (!cnt[dep][i]) val[dep + 1][l + c ++] = val[dep][i]; } build(l, m, dep + 1); build(m + 1, r, dep + 1); } /** 第k小 */ int querykth(int L, int R, int k, int l, int r, int dep) { if (k <= 0 || k > R - L + 1) return - 1; if (L == R) return val[dep][L]; int m = (l + r) >> 1, cl = cnt[dep][L - 1] - cnt[dep][l - 1], cr = cnt[dep][R] - cnt[dep][l - 1]; if (cr - cl >= k) return querykth(l + cl, l + cr - 1, k, l, m, dep + 1); return querykth(m + 1 + L - l - cl, m + R - l + 1 - cr, k - cr + cl, m + 1, r, dep + 1); }public: void build(int a[], int n) { init(a, n); build(1, n, 0); for (int i = 0; i < 20; i ++) { for (int j = 2; j <= n; j ++) { cnt[i][j] += cnt[i][j - 1]; } } } int querykth(int L, int R, int k) { return querykth(L, R, k, 1, n, 0); }};/** 下标从1开始 */PartitionTree pt;int a[maxn];int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif // ONLINE_JUDGE int n, m; while (cin >> n >> m) { for (int i = 1; i <= n; i ++) { scanf("%d", a + i); } pt.build(a, n); int l, r, k; for (int i = 0; i < m; i ++) { scanf("%d%d%d", &l, &r, &k); printf("%d\n", pt.querykth(l, r, k)); } } return 0;}
转载于:https://www.cnblogs.com/jklongint/p/4749192.html