[CF369E]Valera and Queries_离线_树状数组
2024-09-01 13:07:59
Valera and Queries
题目链接:codeforces.com/problemset/problem/369/E
数据范围:略。
题解:
这种题,就单独考虑一次询问即可。
我们发现,包括了至少一个给定点的个数,等于总个数减掉一个给定点都不包括的线段数。
一个都不包括,就表示这个线段的在两个给定点中间,这个可以把线段抽象成二维平面上的点,然后离线+树状数组查询。
代码:
#include <bits/stdc++.h> #define N 1000010 using namespace std; char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) int rd() {
int x = 0;
char c = nc();
while (c < 48) {
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x;
} int cnt = 0; struct Node {
int x, y1, y2, id, c, opt;
}a[N * 10]; inline bool cmp(const Node &a, const Node &b) {
return a.x == b.x ? a.opt > b.opt : a.x < b.x;
} int q[N]; int tree[N]; inline int lowbit(int x) {
return x & (-x);
} void update(int x) {
for (int i = x; i < N; i += lowbit(i)) {
tree[i] ++ ;
}
} int query(int x) {
int ans = 0;
for (int i = x; i; i -= lowbit(i)) {
ans += tree[i];
}
return ans;
} int ans[N]; int main() {
int n = rd(), m = rd();
// opt : 1 -> query, 2 -> update
for (int i = 1; i <= n; i ++ ) {
int x = rd(), y = rd();
a[ ++ cnt] = (Node) {x, y, 0, 0, 1, 2};
}
// cout << cnt << endl ;
for (int i = 1; i <= m; i ++ ) {
int num = rd();
for (int j = 1; j <= num; j ++ ) {
q[j] = rd();
}
q[0] = 0;
q[ ++ num] = N - 1;
// cout << num << endl ;
for (int j = 1; j <= num; j ++ ) {
if (q[j] - q[j - 1] >= 2) {
// printf("Fuck %d\n", j);
int x = q[j - 1] + 1, y = q[j] - 1;
a[ ++ cnt] = (Node) {x - 1, x, y, i, -1, 1};
a[ ++ cnt] = (Node) {y, x, y, i, 1, 1};
}
}
}
// cout << cnt << endl ;
sort(a + 1, a + cnt + 1, cmp);
// for (int i = 1; i <= cnt; i ++ ) {
// printf("%d %d %d %d %d %d\n", a[i].x, a[i].y1, a[i].y2, a[i].id, a[i].c, a[i].opt);
// }
for (int i = 1; i <= cnt; i ++ ) {
// printf("id :: %d\n", i);
if (a[i].opt == 2) {
update(a[i].y1);
}
else {
// cout << query(a[i].y2) << ' ' << query(a[i].y1) << ' ' << a[i].c << endl ;
// cout << (query(a[i].y2) - query(a[i].y1)) * a[i].c << endl ;
ans[a[i].id] += (query(a[i].y2) - query(a[i].y1)) * a[i].c;
}
} for (int i = 1; i <= m; i ++ ) {
printf("%d\n", n - ans[i]);
}
return 0;
}
最新文章
- iOS开发工程师面试题(二)
- 【抓包工具】wireshark
- Windows - 杀死占用某个端口号的进程
- 知乎背景图 canvas 效果
- linux 不能用clock 计算sleep的时间
- docker learning
- SIGPIPE信号详解
- OpenJudge计算概论-计算鞍点
- placeholder插件及placeholder默认颜色修改
- Android Non-UI to UI Thread Communications(Part 2 of 5)
- PHP数据学习-二维数组【3】
- 关于HTML编辑页面(1)
- 使用jdbc存储图片和大文本
- Creating your own auto-configuration
- ListView的setOnItemClickListener位置错乱问题
- Android开发之Activity
- scrapy进阶(CrawlSpider爬虫__爬取整站小说)
- jqgrid 单击行启用行编辑,切换行保存原编辑行
- [SQLite][Error Code] 21 misuse
- (GoRails )使用Vue.js制作拖拉list功能(v1-4) gem &#39;acts_as_list&#39;(自动排列顺序)