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;
}

最新文章

  1. iOS开发工程师面试题(二)
  2. 【抓包工具】wireshark
  3. Windows - 杀死占用某个端口号的进程
  4. 知乎背景图 canvas 效果
  5. linux 不能用clock 计算sleep的时间
  6. docker learning
  7. SIGPIPE信号详解
  8. OpenJudge计算概论-计算鞍点
  9. placeholder插件及placeholder默认颜色修改
  10. Android Non-UI to UI Thread Communications(Part 2 of 5)
  11. PHP数据学习-二维数组【3】
  12. 关于HTML编辑页面(1)
  13. 使用jdbc存储图片和大文本
  14. Creating your own auto-configuration
  15. ListView的setOnItemClickListener位置错乱问题
  16. Android开发之Activity
  17. scrapy进阶(CrawlSpider爬虫__爬取整站小说)
  18. jqgrid 单击行启用行编辑,切换行保存原编辑行
  19. [SQLite][Error Code] 21 misuse
  20. (GoRails )使用Vue.js制作拖拉list功能(v1-4) gem &#39;acts_as_list&#39;(自动排列顺序)

热门文章

  1. 51nod 1434
  2. opencv 学习一安装环境vs2015+opencv3
  3. windows gogs 安装
  4. Sprite Atlas与Sprite Mask详解
  5. Scrapy 教程(11)-API启动爬虫
  6. zabbix (一) 初识
  7. .net core 资料网站 和 开源项目
  8. Linux用户组
  9. Chrome接口调试工具
  10. new HttpClient().PostAsync封装参数