Codeforces 396 E. Valera and Queries
2024-10-19 04:29:11
题目链接:http://codeforces.com/problemset/problem/369/E
考虑将问题转化为有多少条线段没有覆盖这些点,如果一个询问的点集是${[x1,x2,...,xn]}$那么相当于询问有多少条线段在${\left [ 1,x1 \right )\bigcup (x1,x2)\bigcup ...(x_{n-1},x_n)\bigcup(x_n,1e6+1)}$这个范围内,所以离线询问,从左至右扫过去,每到一个点就把以这个点为右端点的线段的左端点的位置加入到树状数组中,然后统计答案
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define llg int
#define maxn 1000100
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg ans[maxn],n,m,c[maxn];
vector<llg>q[maxn],belong[maxn],line[maxn]; inline llg getint()
{
llg w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar(); while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} void inc(llg x) {for (;x<maxn;x+=x&-x) c[x]++;} llg sum(llg x) {if (x==) return ; llg val=; for (;x>;x-=x&-x) val+=c[x]; return val;} void init()
{
cin>>n>>m;
for (llg i=;i<=n;i++)
{
llg l=getint(),r=getint();
line[r].push_back(l);
}
for (llg i=;i<=m;i++)
{
ans[i]=n;
llg k=getint(),x=;
for (llg j=;j<=k;j++)
{
llg wz=getint();
q[wz].push_back(x);
belong[wz].push_back(i);
x=wz;
}
q[].push_back(x);
belong[].push_back(i);
}
} int main()
{
yyj("ds");
init();
for (llg i=;i<=;i++)
{
llg w=q[i].size();
for (llg j=;j<w;j++)
{
ans[belong[i][j]]-=sum(i-)-sum(q[i][j]);
}
w=line[i].size();
for (llg j=;j<w;j++)
{
llg x=line[i][j];
inc(x);
}
}
for (llg i=;i<=m;i++) printf("%d\n",ans[i]);
return ;
}
最新文章
- [MVC4]ASP.NET MVC4+EF5(Lambda/Linq)读取数据
- Altium Designer自动更新——解决方法
- opencl gauss filter优化(二)
- Struts之ForwardAction
- ocp 1Z0-047 131-276题解析
- frameset和iframe--框架对象及元素标签对象
- iOS 地图坐标系之间的转换WGS-84世界标准坐标、GCJ-02中国国测局(火星坐标,高德地图)、BD-09百度坐标系转换
- Android 流媒体系列(一)
- 菜鸟从零学编程(七)——搭建一个完整的Java开发环境
- 关于MYCAT 读写分离,与只读事务的问题.
- Windows 7 蓝屏原因
- [Swift]LeetCode93. 复原IP地址 | Restore IP Addresses
- MongoDB 主从和Replica Set
- Flask-SQLAlchemy常用操作
- docker-网络基础
- properties文件读写工具类
- HTTP 响应状态码
- Qt中的标准对话框之QMessageBox
- C#委托深入学习
- Delphi TClientDataSet的使用
热门文章
- linux架构师之路!
- 干了这杯Java之集合概览
- libcurl.a 跨平台
- 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165321
- 我与C++的初识
- Generator自动生成DAO和POJO代码
- .NetCore技术研究-EntityFramework Core 3.0 Preview
- Typora/VSCode/Sublime 更改Markdown默认宽度样式等
- 【Codeforces Round】 #432 (Div. 2) 题解
- spring boot常见问题