题目描述：
N(N<10000)多线段[l,r](1<=l<=r<=1,000,000,000)相互覆盖，每个线段颜色不同，请问最后有多少种颜色?
吐槽：
1. 说好的平衡树呢.... 扼.... 原谅我... 昨天包宿搞了一晚上
这题... 今天一直头痛，所以就没有信心把
维护数列那题再拿出来做了....
2. 也是去年因为各种原因没有填上的坑，貌似我一遇到离散化就悲剧？？？
3. 不用make编译的下场... 不用IDE的下场... 就是tm刚写完然后就p颠p颠打了一句： g++ 2528.cc -o 2528.cc ...
4. ... .. . .... 就这水平.... 省赛能行么...
算法分析：
线段覆盖那部分可以和这题一起搞，也可以拿线段树来搞。
zkw版线段树也是可以支持“懒惰标记”的.... 具体见ins()函数
比较难搞的是离散化，看discuss板ms数据不完备？？
不过discuss板里的大牛的数据我都通过了，于是乎就说说我的方法把。
1. 把所有询问的点抽出来排序.... 再去掉相同的
2. 如果点a[i]和点a[i+1]相差1，那么先不管，如果超过1，那么我们要在a[i]和a[i+1]之间再加一个点来表示“空白”
应该很简单吧.... 把“空白”表示出来就好...
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<algorithm>
5 using namespace std;
6 #define re(i,n) for(int i=0;i<n;i++)
7 #define re1(i,n) for(int i=1;i<=n;i++)
8 #define dbg(n) cout<<#n<<"="<<n<<endl;
9 template <typename T> inline
void chkmax(T &a,
const T b){
if(a<b) a=b;}
10 int seg[200005],M,__hash,
base[30];
11 int q,hash[40005][2],num[20005],query[10005][2],n;
12 int ins(
int l,
int r,
int color){
13 for(l += M-1, r += M+1; l^r^1; l >>=1 , r>>=1){
14 if(l&1^1) seg[l^1] = color;
15 if(r&1) seg[r^1] = color;
16 }
17 }
18 void build(){
19 re(i,30)
if(
base[i]>__hash+1) {M =
base[i];
break;}
20 re(i,2*M) seg[i] = 0;
21 }
22 int cal(){
23 int __ans = 0;
24 re1(i,q) num[i] = 0;
25 re1(i,__hash) {
26 int pos = i+M;
27 int color = seg[pos];
28 while(pos>>=1) chkmax(color,seg[pos]);
29 num[color] = 1;
30 }
31 re1(i,q) __ans += num[i];
32 return __ans;
33 }
34 int find(
int val){
35 int l = 0, r = n;
36 while(l<r){
37 int mid = l+r >>1;
38 if(hash[mid][0] < val) l = mid +1;
39 else r = mid;
40 }
41 return hash[r][1];
42 }
43 int main(){
44 int t;
45 cin >>t;
46 base[0] = 1;
47 re(i,29)
base[i+1] =
base[i]*2;
48 while(t--){
49 int N = 0;
50 scanf("%d",&q);
51 re(i,q) {
52 scanf("%d%d",&query[i][0],&query[i][1]);
53 num[N++] = query[i][0]; num[N++] = query[i][1];
54 }
55 __hash = 0, n = 0;
56 sort(num,num+N);
57 re(i,N) {
58 if(i == 0 || num[i] != num[i-1]){
59 __hash += 1 + (num[i] > num[i-1] + 1);
60 hash[n][0] = num[i];
61 hash[n][1] = __hash;
62 n ++;
63 }
64 }
65 build();
66 re(i,q){
67 int l = find(query[i][0]), r = find(query[i][1]);
68 ins(l,r,i+1);
69 }
70 printf("%d\n",cal());
71 }
72 return 0;
73 }
74 posted on 2012-05-03 19:21
西月弦 阅读(532)
评论(0) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目