首页 > 代码库 > 【hdu】Mayor's posters(线段树区间问题)
【hdu】Mayor's posters(线段树区间问题)
需要离散化处理,线段树的区间修改问题。
需要注意的就是离散化的时候,由于给的数字是一段单位长度,所以需要特殊处理(因为线段的覆盖和点的覆盖是不一样的)
比如:(1,10)(1,4) (6,10)
离散化之后是 1 , 4 , 6 , 10 分别离散为 1 2 3 4
覆盖的时候先覆盖1 4 之后覆盖了1 2 之后覆盖了 2 3,结果为2
但是实际上应该是3
13450359 | 201301052100 | 2528 | Accepted | 1140K | 985MS | C++ | 1960B | 2014-09-17 15:42:33 |
985MS险过。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; typedef long long LL; const int maxn = 11111; int n,m,ans; bool vis[maxn]; int arr[maxn << 2]; int arr_l[maxn]; int arr_r[maxn]; int tr[maxn << 4]; void UpDate(int l,int r,int value,int L,int R,int pos){ if(l <= L && R <= r){ tr[pos] = value; return ; } if(tr[pos] != -1){ tr[pos << 1] = tr[pos]; tr[(pos << 1)|1] = tr[pos]; tr[pos] = -1; } int m = (L + R) >> 1; if(l <= m) UpDate(l,r,value,L,m,pos << 1); if(r > m) UpDate(l,r,value,m + 1,R,(pos << 1)|1); return ; } void Query(int L,int R,int pos){ if(tr[pos] != -1){ int e = tr[pos]; if(!vis[e]){ vis[e] = true; ans ++; } return ; } if(L == R) return ; int m = (L + R) >> 1; Query(L,m,pos << 1); Query(m + 1,R,(pos << 1)|1); return ; } int main(){ int T; scanf("%d",&T); while(T--){ memset(vis,false,sizeof(vis)); memset(tr,-1,sizeof(tr)); scanf("%d",&m); int size = 0; for(int i = 0 ; i < m ; i++){ scanf("%d%d",&arr_l[i],&arr_r[i]); arr[size ++] = arr_l[i]; arr[size ++] = arr_r[i]; } sort(arr,arr + size); n = unique(arr,arr + size) - arr; //去重复 for(int i = n - 1 ; i > 0 ; i--) //区间转化成点 if(arr[i] != arr[i - 1] + 1) arr[n ++] = arr[i - 1] + 1; sort(arr,arr + n); ans = 0; for(int i = 0 ; i < m ; i++){ int l = find(arr,arr + n,arr_l[i]) - arr; //二分查找 int r = find(arr,arr + n,arr_r[i]) - arr; //二分查找 UpDate(l,r,i,0,n - 1,1); } Query(0,n - 1,1); printf("%d\n",ans); } return 0; }
【hdu】Mayor's posters(线段树区间问题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。