首页 > 代码库 > HDU 3436--Queue-jumpers （树状数组 or Splay Tree）
HDU 3436--Queue-jumpers （树状数组 or Splay Tree）
树状数组这个真心想了好久，还是没想出来 %%% www.cppblog.com/Yuan/archive/2010/08/18/123871.html
树状数组求前缀和大于等于k的最大值，第一次看到这种方法，很神奇，就是没看懂= =
二分也是可以求的，不过感觉会慢一些……
思路就是把所有没有询问到的数压缩
例如如果n等于10 值询问到了 2， 7 大概是这样的
【1，2】【3，4，5，6，7】【8，9，10】
1 2 3
分成3块，最多分为q块，实现离散化。
#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int N = 200005;int op[N], a[N], b[N], p[N], no[N];int n, q;struct BIT { int arr[N]; int n; int sum(int p) { int ans = 0; while (p) { ans += arr[p]; p -= lowbit(p); } return ans; } void add(int p, int v) { while (p <= n) { arr[p] += v; p += lowbit(p); } } int find(int k) { //在数组中找第一个大于等于k的位置 int pos = 0, cnt = 0; for (int i = 17; i >= 0; --i) { pos += (1<<i); if (pos >= n || cnt + arr[pos] >= k) pos -= (1<<i); else cnt += arr[pos]; } return pos+1; } void init(int n) { this->n = n; memset(arr, 0, sizeof arr); } int lowbit(int x) { return x&-x; }} bit;int main(){ //freopen("in.txt", "r", stdin); int T, cas = 0; scanf("%d", &T); while (T--) { printf("Case %d:\n", ++cas); scanf("%d%d", &n, &q); char ch[10]; int idx = 0; for (int i = 1; i <= q; ++i) { scanf("%s%d", ch, &a[i]); if (*ch == ‘T‘) op[i] = 1; else if (*ch == ‘Q‘) op[i] = 2; else op[i] = 3; if (op[i] < 3) b[++idx] = a[i]; } b[++idx] = n; sort(b+1, b+1+idx); n = unique(b+1, b+1+idx) - b - 1; bit.init(2*q); for (int i = 1; i <= n; ++i) { bit.add(q+i, b[i]-b[i-1]); no[q+i] = b[i]; // no[i] 数组i处的编号 原编号！！ p[i] = q+i; // p[i] 编号为i的位置 } int top = q; for (int i = 1; i <= q; ++i) { if (op[i] == 1) { int x = lower_bound(b+1, b+1+n, a[i]) - b; bit.add(p[x], -1); // 要把x挪到顶端 p[x]位置的数字个数减少一个 no[p[x]]--; // x走了 剩下的是x-1 p[x] = top; // x的位置变成了top bit.add(top, 1); // top位置有一个数字x +1 no[top] = a[i]; top--; } else if (op[i] == 2) { int x = lower_bound(b+1, b+1+n, a[i]) - b; printf("%d\n", bit.sum( p[ x ] )); } else { int pos = bit.find(a[i]); int sp = bit.sum(pos); if (sp == a[i]) printf("%d\n", no[pos]); else printf("%d\n", no[pos]-(sp-a[i])); } } } return 0;}
Splay 再补……
HDU 3436--Queue-jumpers （树状数组 or Splay Tree）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。