Time limit 5000 ms
Memory limit 32768 kB
OS Windows
Source )
解题思路
主席树求静态区间第k大
源代码
下面的代码可以AC，但是其实开的全局数组已经七十兆了(空间限制32兆)，能过的原因我猜是每个case之间没有使用memset清零，而是直接在下一个case赋值，所以那些用不到的空间就不会去碰，然后就没有报RE或MLE。试了一下，用memset清零果然MLE了。Ps:另外，最近每一篇分享给同学的博客都被或多或少指出几个错误，有交流才有提高啊……我菜死了
#include#include int T;int n, m;int a[200010];int val[200010], sz;inline int id(int x) { return std::lower_bound(val + 1, val + 1 + sz, x) - val; }struct Node{ int sum; int lson, rson;}tree[6000010];int root[200010],cnt=1;void build(int &rt, int l, int r){ rt = cnt++; tree[rt]={0,0,0}; if (l == r) return; int mid = l + r >> 1; build(tree[rt].lson, l, mid); build(tree[rt].rson, mid + 1, r);}void update(int &rt, int last, int l, int r, int pos){ rt = cnt++; tree[rt] = tree[last]; tree[rt].sum++; if (l == r) return; int mid = l + r >> 1; if (pos > mid) update(tree[rt].rson, tree[last].rson, mid + 1, r, pos); else update(tree[rt].lson, tree[last].lson, l, mid, pos);}int que(int srt, int trt, int l, int r, int k){ if (l == r) return l; int mid = l + r >> 1; int delta = tree[tree[trt].lson].sum - tree[tree[srt].lson].sum; if (k <= delta) return que(tree[srt].lson, tree[trt].lson, l, mid, k); else return que(tree[srt].rson, tree[trt].rson, mid + 1, r, k - delta);}int main(){ //freopen("test.in","r",stdin); scanf("%d", &T); while (T--) { cnt = 1; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); val[i] = a[i]; } std::sort(val + 1, val + 1 + n); sz = std::unique(val + 1, val + 1 + n) - (val + 1); build(root[0], 1, sz); for (int i = 1; i <= n; i++) { a[i] = id(a[i]); update(root[i], root[i - 1], 1, sz, a[i]); } for (int i = 1, ll, rr, k; i <= m; i++) { scanf("%d%d%d", &ll, &rr, &k); printf("%d\n", val[que(root[ll - 1], root[rr], 1, sz, k)]); } } return 0;}