1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 500000; const int MAXM = 500000; int n, m; int ans[MAXM + 5]; // 第i个矩形的答案 struct OP { // op==0:加入一个树 (x,y) // op>0: 需要查询 (1,1)~(x,y) 有多少树,把答案乘w后加入ans[op] int op, x, y, w; }; bool operator<(const OP &a, const OP &b) { if (a.x != b.x) return a.x < b.x; if (a.y != b.y) return a.y < b.y; return a.op < b.op;//优先加树再询问 } vector<OP> o; // 离散化y的辅助数组 vector<int> temp; // 树状数组 int t[MAXN + MAXM * 4 + 5], treeN; int lowbit(int x) { return x & (-x); } // 第x个数加k void update(int x, int k) { for (int i = x; i <= treeN; i += lowbit(i)) t[i] += k; } // 返回前x个数的和 int query(int x) { int res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += t[i]; return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; x++, y++; o.push_back((OP){0, x, y, 0}); temp.push_back(y); } for (int i = 1; i <= m; i++) { ans[i] = 0; int x, y, xx, yy; cin >> x >> y >> xx >> yy; x++, y++, xx++, yy++; o.push_back((OP){i, xx, yy, 1}); o.push_back((OP){i, x - 1, yy, -1}); o.push_back((OP){i, xx, y - 1, -1}); o.push_back((OP){i, x - 1, y - 1, 1}); temp.push_back(yy); temp.push_back(y - 1); } // 对y离散化 sort(temp.begin(), temp.end()); treeN = 0; for (int i = 0; i < o.size(); i++) { o[i].y = lower_bound(temp.begin(), temp.end(), o[i].y) - temp.begin(); // 让y离散化后从1开始 o[i].y += 1; treeN = max(treeN, o[i].y); } // 按x坐标排序所有操作,然后依次处理 sort(o.begin(), o.end()); for (int i = 0; i < o.size(); i++) { //cout << o[i].op << " " << o[i].x << " " << o[i].y << " " << o[i].w << ": "; if (o[i].op == 0) { update(o[i].y, 1); //cout << "add (" << o[i].x << "," << o[i].y << ")\n"; } else { ans[o[i].op] += o[i].w * (query(o[i].y)); //cout << "ans[" << o[i].op << "]+=" << o[i].w << "*" << query(o[i].y) << "\n"; } } for (int i = 1; i <= m; i++) cout << ans[i] << "\n"; return 0; }
信息
- ID
- 2946
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 6
- 已通过
- 3
- 上传者