poj1741，POJ 1769

2023-10-15 阅读 27 评论 0

摘要：題意：用m個區間去覆蓋1~n，求最小使用數。題解：線段樹，覆蓋[l,r]：找出線段樹上含了l的最小的區間數x，讓線段樹[l,r]區間取它本身與x的最小值，最后在求n處的最小值即可，復雜度O(mlogn)。開始的時候還想pushdown等操作

題意：用m個區間去覆蓋1~n，求最小使用數。

題解：線段樹，覆蓋[l,r]：找出線段樹上含了l的最小的區間數x，讓線段樹[l,r]區間取它本身與x的最小值，最后在求n處的最小值即可，復雜度O(mlogn)。開始的時候還想pushdown等操作，結果超時，后來一算發現直接暴力線段樹更好。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=50005,M=500005;
 6 const int inf=1<<29;
 7 struct Line
 8 {
 9     int left,right,val;
10 }line[N*4];
11 struct data
12 {
13     int x,y;
14     bool operator<(const data &ne)const
15     {
16         if(x!=ne.x)
17             return x<ne.x;
18         else
19             return y<ne.y;
20     }
21 }po[M];
22 void build(int now,int left,int right)
23 {
24     line[now].left=left;
25     line[now].right=right;
26     line[now].val=inf;
27     if(left==right)
28         return;
29     int mid=(left+right)>>1;
30     build(now*2,left,mid);
31     build(now*2+1,mid+1,right);
32 }
33 int getpos(int now,int pos)
34 {
35     int ll=line[now].left,rr=line[now].right,mid=(ll+rr)>>1;
36     if(ll==rr)
37         return line[now].val;
38     else if(pos<=mid)
39         return min(line[now].val,getpos(now*2,pos));
40     else
41         return min(line[now].val,getpos(now*2+1,pos));
42 }
43 void modify(int now,int left,int right,int v)
44 {
45     int ll=line[now].left,rr=line[now].right,mid=(ll+rr)>>1,val=line[now].val;
46     if(ll==left&&rr==right)
47     {
48         line[now].val=min(val,v);
49         return;
50     }
51     if(right<=mid)
52         modify(now*2,left,right,v);
53     else if(left>mid)
54         modify(now*2+1,left,right,v);
55     else
56     {
57         modify(now*2,left,mid,v);
58         modify(now*2+1,mid+1,right,v);
59     }
60 }
61 int main()
62 {
63     int n,m;
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         build(1,1,n);
67         modify(1,1,1,0);
68         for(int i=0;i<m;i++)
69         {
70             scanf("%d%d",&po[i].x,&po[i].y);
71             int x=max(po[i].x,1),y=min(po[i].y,n);
72             int tp=getpos(1,x);
73             if(tp==inf)
74                 continue;
75             modify(1,x,y,tp+1);
76         }
77         printf("%d\n",getpos(1,n));
78     }
79     return 0;
80 }