题意
给出每个海报的位置,问最后没有被完全覆盖的海报有多少张
思路
这里给的海报的端点值很大,需要离散化之后再用线段树求解。离散化写挫被坑了好多发,注意这三组数据。
3
3
3 4
1 3
4 10
//答案是2
3
1 5
1 3
4 5
//答案是2
3
1 10
1 3
6 10
//答案是3
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int nMax = 100000; struct{ int l,r,val; //-1杂色 0无色 1---k纯色 }node[nMax * 3]; struct{ int a,b; }ad[nMax]; int num[4*nMax]; int hash[10000010]; void build(int l ,int r ,int u){ node[u].l = l; node[u].r = r; node[u].val = 0; if(l == r)return; int m = (l + r)>>1; build(l ,m ,u*2); build(m+1 ,r ,u*2+1); } void update(int left ,int right ,int val ,int u){ if(left == node[u].l && right == node[u].r){ // cout<<left <<" "<<right <<" "<<u<<endl; node[u].val = val; return; } if(node[u].val != -1){ node[u*2].val = node[u*2+1] .val = node[u].val; node[u].val = -1; } int m = (node[u].l + node[u].r)>>1; if(right <= m){ update(left ,right ,val ,u*2); return; } if(left >= m+1){ update(left ,right ,val ,u*2+1); return; } update(left ,m ,val ,u*2); update(m+1 ,right ,val ,u*2+1); } void query(int left ,int right ,int u){ // cout<<left <<" e e "<<right<<endl; if(node[u].val != -1){ // cout<<"get\n"; num[node[u].val] = 1; return; } int m =(node[u].l + node[u].r)>>1; if(left <= m){ query(left ,min(m ,right) ,u*2); } if(right >= m+1){ query(max(m+1 ,left) ,right ,u*2 + 1); } } int main(){ int tcs ,n ,i ,k; scanf("%d",&tcs); while(tcs--){ scanf("%d",&n); k = 0; for(i = 1 ;i <= n ;i++){ scanf("%d%d",&ad[i].a,&ad[i].b); num[k++] = ad[i].a; num[k++] = ad[i].b; } sort(num ,num + k); memset(hash,0,sizeof(hash)); int tmp = 0; hash[num[0]] = 1; int nk = 2; for(i=1 ;i < k ;i++){ if(num[i] - num[i-1] > 1)tmp++; if(!hash[num[i]]){ hash[num[i]] = nk + tmp; nk++; } // if(num[i]!=num[i-1])hash[num[i]] = (i + 1) + tmp; } for(i = 1 ;i <= n ;i++){ ad[i].a = hash[ad[i].a]; ad[i].b = hash[ad[i].b]; } build(1 ,nk + tmp,1); // cout<<" -------------\n"; for(i = 1 ;i <= n;i++){ // cout<<ad[i].a<<" "<<ad[i].b<<endl; update(ad[i].a ,ad[i].b ,i ,1); // cout<<endl<<endl; } memset(num ,0 ,sizeof(num)); int ans = 0; query(1 ,nk + tmp,1); for(i = 1 ;i <= n ;i++){ if(num[i])ans++; } printf("%d\n",ans); } return 0; }
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 ...
poj-2528 Mayor's posters 测试数据及答案
北大POJ2187-Beauty Contest 解题报告+AC代码
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
北大POJ1936-All in All 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
C + + language learning poj100 question bank and code
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1746750