题意：给一些线段，然后给m个查询，每次查询都给出一些点，问有多少条线段包含这个点集中的一个或多个点
解法：直接离线以点为基准和以线段为基准都不好处理，“正难则反”，我们试着求有多少线段是不包含某个查询的任意一个点的。这时候我们可以建立点集的补集，以线段的形式，如果点集的补集线段包含了某条给出的线段，那么被包含的那条线段肯定不会包括任意一个点，那么该组查询的答案ans--即可。 用树状数组做，离线读入数据，按容易被包含的线段优先排个序，然后扫一遍，边统计边修改即可。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; #define N 1000007 int 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-ans[i]); } return 0; }