摘要：
#包括<；向量<；seg[maxn<；inta[maxn]；intn；voidpushUp（intcur）{merge（seg[cur<；1|1].begin（）；1|1].end（）；pushUp（cur）；=be&；&；}else{intpos=upper_bound（seg[cur].begn（）；intlans=0；if（查询（L；
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; }