CodeForces - 369E Valera and Queries（树状数组）
[CodeForces - 369E Valera and Queries](http://codeforces.com/problemset/problem/369/E)
题目大意：给出n个线段(线段的左端点和右端点坐标)和m个查询，每个查询有cnt个点，要求给出有多少条线段包含至少其中一个点。
思路：如果按照题意正面去算有每个线段是否包含点，那么时间复杂度是不允许的；如果去算每个点被哪些线段包含，那么去重比较困难。正难则反，因此对于每个查询，选择去求有多少个线段没有覆盖任何一个点，那么答案则为n减所求。用树状数组来统计没有覆盖任何一个点的线段数，大致做法是将临界线段（如x1+1,x2-1）插入seg数组中，再按一定规则进行排序，之后通过树状数组维护统计被包含于临界线段的线段数，具体实现在代码中。
代码：
```C++
#include
#include
#include
using namespace std;
const int maxn=1000000+5;
struct segment
{
int l,r,id;
};
bool cmp(const segment& a,const segment& b)
{
if (a.l!=b.l)
return a.l>b.l;
if (a.r!=b.r)
return a.r0)
{
sum+=tree[i];
i-=i&-i;
}
return sum;
}
int ans[maxn];
int main()
{
int n,m,i,j;
cin>>n>>m;
for (i=0;i<n;++i)
{
scanf("%d%d",&seg[i].l,&seg[i].r);
seg[i].id=0;
}
int cnt,x,pre,tt=n;
for (i=1;i<=m;++i)
{
ans[i]=n;
pre=0;
scanf("%d",&cnt);
for (j=0;j<cnt;++j)
{
scanf("%d",&x);
if (pre+1<=x-1)
{
seg[tt].l=pre+1;
seg[tt].r=x-1;
seg[tt++].id=i;
}
pre=x;
}
seg[tt].l=pre+1;
seg[tt].r=maxn;
seg[tt++].id=i;
}
sort(seg,seg+tt,cmp);
for (i=0;i<tt;++i)
{
if (seg[i].id)
{
ans[seg[i].id]-=sum(seg[i].r);
}
else
{
add(seg[i].r,1);
}
}
for (i=1;i<=m;++i)
{
printf("%d\n",ans[i]);
}
return 0;
}
</font>最新文章
- js中的DOM事件与对象
- MySql: show databases/tables use database desc table
- Python与C++结构体交互
- Idol之坑
- linux内核分析 第七周
- HDU 1058 优先队列or堆
- “我爱淘”冲刺阶段Scrum站立会议6
- Android SurfaceView 绘图覆盖刷新及脏矩形刷新方法
- Codeforces Round #364
- 1、netlink 连接器 通信机制
- OC - 16.大文件下载
- MyBatis Parameter not found
- SQL Server 优化存储过程的七种方法
- hibernate动态切换数据源
- 2个域名重定向到https域名
- Oracle SQL Developer 连接数据库如何对应数据库配置文件
- OpenGL平面阴影
- 看我如何粘贴别人代码--socketserver
- GCOV&LCOV&GCOVR入门
- Servlet(3)—Servlet