首页 > 代码库 > Codeforces 396 E. Valera and Queries
Codeforces 396 E. Valera and Queries
题目链接：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)}$这个范围内，所以离线询问，从左至右扫过去，每到一个点就把以这个点为右端点的线段的左端点的位置加入到树状数组中，然后统计答案
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cmath> 6 #include<cstring> 7 #include<queue> 8 #include<vector> 9 #include<map>10 using namespace std;11 #define llg int12 #define maxn 100010013 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 llg ans[maxn],n,m,c[maxn];15 vector<llg>q[maxn],belong[maxn],line[maxn];16 17 inline llg getint()18 {19 llg w=0,q=0; char c=getchar();20 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar();21 if (c==‘-‘) q=1, c=getchar(); while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar();22 return q ? -w : w;23 }24 25 void inc(llg x) {for (;x<maxn;x+=x&-x) c[x]++;}26 27 llg sum(llg x) {if (x==0) return 0; llg val=0; for (;x>0;x-=x&-x) val+=c[x]; return val;}28 29 void init()30 {31 cin>>n>>m;32 for (llg i=1;i<=n;i++)33 {34 llg l=getint(),r=getint();35 line[r].push_back(l);36 }37 for (llg i=1;i<=m;i++)38 {39 ans[i]=n;40 llg k=getint(),x=0;41 for (llg j=1;j<=k;j++)42 {43 llg wz=getint();44 q[wz].push_back(x);45 belong[wz].push_back(i);46 x=wz;47 }48 q[1000001].push_back(x);49 belong[1000001].push_back(i);50 }51 }52 53 int main()54 {55 yyj("ds");56 init();57 for (llg i=1;i<=1000002;i++)58 {59 llg w=q[i].size();60 for (llg j=0;j<w;j++)61 {62 ans[belong[i][j]]-=sum(i-1)-sum(q[i][j]);63 }64 w=line[i].size();65 for (llg j=0;j<w;j++)66 {67 llg x=line[i][j];68 inc(x);69 }70 }71 for (llg i=1;i<=m;i++) printf("%d\n",ans[i]);72 return 0;73 }
Codeforces 396 E. Valera and Queries
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。