首页 > 代码库 > bzoj1935
bzoj1935
树状数组+离线
按x排序,y离散化,树状数组查询,跟逆序对一样
#include<bits/stdc++.h> using namespace std; const int N = 500010; int n, m, tot, lim; vector<int> v; int ans[N], aa[N], b[N], c[N], d[N], xx[N], yy[N]; map<int, int> mp; struct BIT { int tree[N]; int lowbit(int i) { return i & (-i); } void update(int pos, int delta) { for(int i = pos; i <= lim; i += lowbit(i)) tree[i] += delta; } int query(int pos) { int ret = 0; for(int i = pos; i; i -= lowbit(i)) ret += tree[i]; return ret; } } t; struct data { int x, y, f, id, type; data(int x = 0, int y = 0, int f = 0, int type = 0, int id = 0) : x(x), y(y), f(f), type(type), id(id) {} bool friend operator < (data A, data B) { if(A.x == B.x) return A.type < B.type; return A.x < B.x; } } a[N * 5]; int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { int x, y; scanf("%d%d", &xx[i], &yy[i]); v.push_back(yy[i]); } for(int i = 1; i <= m; ++i) { scanf("%d%d%d%d", &aa[i], &b[i], &c[i], &d[i]); v.push_back(b[i]); v.push_back(d[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for(int i = 0; i < v.size(); ++i) mp[v[i]] = i + 2; lim = v.size() + 1; for(int i = 1; i <= n; ++i) { a[++tot].x = xx[i]; a[tot].y = mp[yy[i]]; a[tot].type = 0; } for(int i = 1; i <= m; ++i) { a[++tot] = data(c[i], mp[d[i]], 1, 1, i); a[++tot] = data(aa[i] - 1, mp[b[i]] - 1, 1, 1, i); a[++tot] = data(aa[i] - 1, mp[d[i]], -1, 1, i); a[++tot] = data(c[i], mp[b[i]] - 1, -1, 1, i); } sort(a + 1, a + tot + 1); for(int i = 1; i <= tot; ++i) { if(a[i].type == 0) t.update(a[i].y, 1); if(a[i].type == 1) ans[a[i].id] += t.query(a[i].y) * a[i].f; } for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]); return 0; }
bzoj1935
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。