首页 > 代码库 > Codeforces Beta Round #12 (Div 2 Only) D. Ball 树状数组查询后缀、最值
Codeforces Beta Round #12 (Div 2 Only) D. Ball 树状数组查询后缀、最值
http://codeforces.com/problemset/problem/12/D
这里的BIT查询,指的是查询[1, R]或者[R, maxn]之间的最值,这样就够用了。
设三个权值分别是b[1], b[2], b[2];
首先,先把b[1]值离散化,离散成一个个id,那么只能是在id比较大的地方找了。然后把b[2]排序,倒序查询,也就是先查询最大的,当然它是没可能自杀的,因为它已经最大了,然后查询完后,把它压进bit后,以后在bit查询,就不需要管b[2]了,因为在bit里面的b[2]永远都是较大者,其实这是一个常用的方法啦。hack点是相同的值不能提前更新,细节看代码 + 慢慢debug
现在说说bit的作用,bit维护的是b[3],因为我们已经离散化b[1]了,那么每一个元素的下标就相当于离散化的b[1],所以加进去BIT的时候用id做下标即可。bit维护后缀最大值。
hack点的意思是,假如你的a[i].b[2] == a[j].b[2],那么不能在查询a[j]前提前把a[i]加入bit,因为bit查询默认是b[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> #include <bitset> #include <stack> const int maxn = 5e5 + 20; int c[maxn], en; int lowbit(int x) { return x & (-x); } void upDate(int pos, int val) { while (pos) { c[pos] = max(c[pos], val); pos -= lowbit(pos); } } int ask(int pos) { int ans = -1; while (pos <= en) { ans = max(ans, c[pos]); pos += lowbit(pos); } return ans; } struct Node { int a[5], id; }a[maxn]; stack<int> st; bool cmp0(struct Node a, struct Node b) { return a.a[1] < b.a[1]; } bool cmp1(struct Node a, struct Node b) { return a.a[2] < b.a[2]; } void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i].a[1]); for (int i = 1; i <= n; ++i) scanf("%d", &a[i].a[2]); for (int i = 1; i <= n; ++i) scanf("%d", &a[i].a[3]); sort(a + 1, a + 1 + n, cmp0); en = 1; a[1].id = en; for (int i = 2; i <= n; ++i) { if (a[i].a[1] == a[i - 1].a[1]) { a[i].id = en; } else a[i].id = ++en; } en += 2; memset(c, -1, sizeof c); sort(a + 1, a + 1 + n, cmp1); // for (int i = 1; i <= n; ++i) { // cout << a[i].a[1] << " " << a[i].a[2] << " " << a[i].a[3] << " " << a[i].id << endl; // } st.push(n); int ans = 0; for (int i = n - 1; i >= 1; --i) { if (a[i].a[2] == a[i + 1].a[2]) { st.push(i); int res = ask(a[i].id + 1); ans += res > a[i].a[3]; } else { while (!st.empty()) { int res = st.top(); st.pop(); upDate(a[res].id, a[res].a[3]); } int res = ask(a[i].id + 1); ans += res > a[i].a[3]; st.push(i); // upDate(a[i].id, a[i].a[3]); } } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
Codeforces Beta Round #12 (Div 2 Only) D. Ball 树状数组查询后缀、最值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。