首页 > 代码库 > Codeforces 369E Valera and Queries --树状数组+离线操作
Codeforces 369E Valera and Queries --树状数组+离线操作
题意：给一些线段，然后给m个查询，每次查询都给出一些点，问有多少条线段包含这个点集中的一个或多个点
解法：直接离线以点为基准和以线段为基准都不好处理，“正难则反”，我们试着求有多少线段是不包含某个查询的任意一个点的。这时候我们可以建立点集的补集，以线段的形式，如果点集的补集线段包含了某条给出的线段，那么被包含的那条线段肯定不会包括任意一个点，那么该组查询的答案ans--即可。 用树状数组做，离线读入数据，按容易被包含的线段优先排个序，然后扫一遍，边统计边修改即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;#define N 1000007int c[N],n,m,ans[300005],maxi;struct node{ int l,r,ind;}a[N];int lowbit(int x){ return x&-x; }void modify(int x){ while(x <= maxi) { c[x]++; x += lowbit(x); }}int getsum(int x){ int ans = 0; while(x > 0) { ans += c[x]; x -= lowbit(x); } return ans;}int cmp(node ka,node kb) //容易被覆盖的线段放在前面{ if(ka.l == kb.l) { if(ka.r == kb.r) return ka.ind < kb.ind; return ka.r < kb.r; } return ka.l > kb.l;}int main(){ int i,j,k,x,pre,cnt; maxi = N-5; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].ind = 0; memset(ans,0,sizeof(ans)); memset(c,0,sizeof(c)); int tot = n; for(i=1;i<=m;i++) { scanf("%d",&cnt); scanf("%d",&x); if(x > 1) a[++tot].l = 1, a[tot].r = x-1, a[tot].ind = i; pre = x; for(j=1;j<cnt;j++) { scanf("%d",&x); if(x-1 >= pre+1) a[++tot].l = pre+1, a[tot].r = x-1, a[tot].ind = i; pre = x; } a[++tot].l = pre+1, a[tot].r = maxi, a[tot].ind = i; } sort(a+1,a+tot+1,cmp); for(i=1;i<=tot;i++) { if(a[i].ind > 0) ans[a[i].ind] += getsum(a[i].r); else modify(a[i].r); } for(i=1;i<=m;i++) printf("%d\n",n-ans[i]); } return 0;}
Codeforces 369E Valera and Queries --树状数组+离线操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。