首页 > 代码库 > Codeforces Round #216 (Div. 2) E. Valera and Queries (BIT)
Codeforces Round #216 (Div. 2) E. Valera and Queries (BIT)
题目大意:
给出很多条分布在 x 轴上的线段。
然后给出很多点集,问这些点集分布在多少条不同的线段上。
思路分析:
把点集分散成若干条线段。
如果点集做出的线段包含了某一条给出的线段的话,也就是说这个点集上不会有点在这条线段上。
所以我们就是求出 点集做出的线段包含了多少个给出的线段就可以了。
那么也就是比较l r的大小,排序之后用BIT
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define lowbit(x) (x&(-x)) #define maxn 1000005 using namespace std; struct node { int l,r,p; bool operator < (const node &cmp)const { if(l!=cmp.l)return l>cmp.l; if(r!=cmp.r)return r<cmp.r; return p<cmp.p; } } line[maxn]; int bit[maxn],ans[maxn],n,m,S=1e6+1; int sum(int x) { int res=0; for(;x;x-=lowbit(x))res+=bit[x]; return res; } int add(int x) { for(;x<=S;x+=lowbit(x))bit[x]++; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d%d",&line[i].l,&line[i].r); int T=n,cnt,p,x; for(int i=1;i<=m;i++) { ans[i]=n; scanf("%d%d",&cnt,&p); if(p>1)line[++T].l=1,line[T].r=p-1,line[T].p=i; for(;--cnt;p=x) { scanf("%d",&x); if(x>p+1)line[++T].l=p+1,line[T].r=x-1,line[T].p=i; } line[++T].l=p+1,line[T].r=S,line[T].p=i; } sort(line+1,line+1+T); for(int i=1;i<=T;i++) if(line[i].p) ans[line[i].p]-=sum(line[i].r); else add(line[i].r); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。