K-th Number 线段树的区间第K大

http://poj.org/problem?id=2104

由于这题的时间限制不紧，所以用线段树水一水。

每个节点保存的是一个数组。

就是对应区间排好序的数组。

建树的时间复杂度需要nlogn

然后查询的时候，对于线段树覆盖了的区间，可以直接二分即可。

查询复杂度需要logn^2

所以复杂度需要mlognlogn

对于怎么确定是那个元素。可以二分一个值val

然后查询在个val在这个区间是否第k大即可。

所以复杂度需要mlognlognlog1e9

开始的时候，不知道怎么确定2、3、5、6的第3大。

我以为二分一个4出来也是第三大啊。

但4只是第二大，如果把它放进去数组里面，当然变成了第3大，但是现在是统计小于等于4的个数，只有2个。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#define root 1, n, 1
#define lson L, mid, cur << 1
#define rson mid + 1, R, cur << 1 | 1
const int maxn = 100000 + 20;
vector<int>seg[maxn << 2];
int a[maxn];
int n, m;
void pushUp(int cur) {
    merge(seg[cur << 1].begin(), seg[cur << 1].end(), seg[cur << 1 | 1].begin(), seg[cur << 1 | 1].end(), seg[cur].begin());
}
void build(int L, int R, int cur) {
    if (L == R) {
        seg[cur].clear();
        seg[cur].push_back(a[L]);
        return;
    }
    int mid = (L + R) >> 1;
    build(lson);
    build(rson);
    seg[cur].resize(R - L + 1);
    pushUp(cur);
}
int query(int be, int en, int val, int L, int R, int cur) {
    if (L >= be && R <= en) {
        if (val >= seg[cur].back()) {
            return R - L + 1;
        } else {
            int pos = upper_bound(seg[cur].begin(), seg[cur].end(), val) - seg[cur].begin();
            return pos;
        }
    }
    int mid = (L + R) >> 1;
    int lans = 0, rans = 0;
    if (mid >= be) {
        lans = query(be, en, val, lson);
    }
    if (mid < en) {
        rans = query(be, en, val, rson);
    }
    return lans + rans;
}
int tofind(int L, int R, int k) {
    int be = -1e9;
    int en = 1e9;
    while (be <= en) {
        int mid = (be + en) >> 1;
        if (query(L, R, mid, root) >= k) {
            en = mid - 1;
        } else be = mid + 1;
    }
    return be;
}
void work() {
    scanf("%d%d", &n, &m);
//    cout << n << " " << m << endl;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(root);
    while (m--) {
        int L, R, k;
        scanf("%d%d%d", &L, &R, &k);
        printf("%d
", tofind(L, R, k));
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
        work();
    return 0;
}

分块超时代码，不解

一直TLE, 20多次

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 100000 + 20;
int arr[maxn];
int tarr[maxn];
int tosort[maxn];
int n, m;
int magic;
void init() {
    for (int i = 1; i <= n;) {
        if (i + magic - 1 > n) break;
        sort(tosort + i, tosort + i + magic);
        i += magic;
    }
}
bool check(int L, int R, int val, int k) {
    int ans = 0;
    for (int i = L; i <= R;) {
        if (i % magic == 1 && i + magic - 1 <= R) {
            ans += upper_bound(tosort + i, tosort + i + magic, val) - (tosort + i - 1) - 1;
            i += magic;
        } else {
            if (val >= arr[i]) {
                ans++;
            }
            ++i;
        }
        if (ans >= k) return true;
    }
    return false;
}
int calc(int L, int R, int k) {
    int be = 1, en = n;
    while (be <= en) {
        int mid = (be + en) >> 1;
        if (check(L, R, tarr[mid], k)) {
            en = mid - 1;
        } else be = mid + 1;
    }
    return tarr[be];
}
void work() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
        tarr[i] = arr[i];
        tosort[i] = arr[i];
    }
    sort(tarr + 1, tarr + 1 + n);
    magic = (n / ((int)sqrt(n * log((double)n)) + 1));
    init();
//    cout << check(1, 7, 3, 3) << endl;
    while (m--) {
        int L, R, k;
        scanf("%d%d%d", &L, &R, &k);
        printf("%d
", calc(L, R, k));
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}