題目描述：
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
西月弦 閱讀(547)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目