bzoj 1171 大sz的游戲& 2892 強襲作戰 （線段樹+單調隊列+永久性flag）

Description

大sz最近在玩一個由星球大戰改編的游戲。話說絕地武士當前共控制了N個星球。但是，西斯正在暗處悄悄地準備他們的復仇計劃。絕地評議會也感覺到了這件事。於是，準備加派絕地武士到各星球防止西斯的突襲。一個星球受到攻擊以後，會儘快通知到總基地。需要的時間越長的星球就需要越多絕地武士來防禦。為了合理分配有限的武士，大sz需要你幫他求出每個星球各需要多少時間能夠通知到總基地。由於某種原因，N個星球排成一條直線，編號1至N。其中總基地建在1號星球上。每個星球雖然都是絕地武士控制的，但是上面居住的生物不一定相同，並且科技水平也不一樣。第i個星球能收到並分析波長在[xi, yi]之間的信號，並且也能夠發出在這個區間的信號，但是不能發出其他任何波長的信號。由於技術原因，每個星球只能發信號到比自己編號小的距離不超過L的星球。特別地，強大的總基地可以接收任何波長的信號。每個星球處理接收到的數據需要1個單位時間，傳輸時間可以忽略不計。

Input

第一行兩個正整數N、L。接下來N-1行，總共第i行包含了三個正整數xi、yi、li，其中li表示第i個星球距離1號星球li，滿足li嚴格遞增。

Output

總共N-1行，每行一個數分別表示2到N號星球至少需要多少單位時間，總基地能夠處理好數據，如果無法傳到總基地則輸出-1。

Sample Input

Sample Output

HINT

Source

By 俞華程

題解

　　　　　　　　

　　　　比如紅色線段是需要尋找的，那麼對於包括這條線段的，並且是滿足整條線段包括的

　　　　我的代碼中分為一個tr與一個bj數組，

　　　　tr數組的意思是剛好完全包括這一段的，一個值，

　　　　而bj表示子區間中含有這一段的，

　　　　那麼，在尋找中，如果被tr包括，tr可以直接更新，因為這段全部都是滿足的。

　　　　如果當前尋找的這一段是包括了bj那麼bj中有子區間的值也一定被尋找段包括，所以可以更新，

　　　　這樣更新前維護單調性即可。

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<map>
 7 #include<list>
 8 
 9 #define N 2000007
10 #define inf 1000000007
11 #define fzy pair<int,int>
12 using namespace std;
13 inline int read()
14 {
15     int x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 
21 int n,L,num,siz;
22 int hd,tl,q[N],b[N],f[N];
23 struct Node
24 {
25     int x,y,l;
26 }a[N];
27 list<fzy>tr[N],bj[N];
28 map<int,int>p;
29 
30 
31 void ins(int p,int l,int r,int x,int y,fzy zhi)
32 {
33     if (x<=l&&r<=y)
34     {
35         while(!tr[p].empty()&&tr[p].back().second>=zhi.second)
36             tr[p].pop_back();
37         tr[p].push_back(zhi);
38         return;
39     }
40     
41     while(!bj[p].empty()&&bj[p].back().second>=zhi.second)
42         bj[p].pop_back();
43     bj[p].push_back(zhi);
44     
45     int mid=(l+r)>>1;
46     if (y<=mid) ins(p<<1,l,mid,x,y,zhi);
47     else if (x>mid) ins(p<<1|1,mid+1,r,x,y,zhi);
48     else ins(p<<1,l,mid,x,mid,zhi),ins(p<<1|1,mid+1,r,mid+1,y,zhi);
49 }
50 int query(int p,int l,int r,int x,int y,int wei)
51 {
52     int res;
53     
54     while(wei-tr[p].front().first>L&&!tr[p].empty())
55         tr[p].pop_front();
56     if (tr[p].empty()) res=inf;
57     else res=tr[p].front().second;
58     
59     
60     while(wei-bj[p].front().first>L&&!bj[p].empty()) bj[p].pop_front();
61     if (x<=l&&r<=y)
62     {
63         if (!bj[p].empty()) res=min(res,bj[p].front().second);
64         return res;
65     }
66     
67     int mid=(l+r)>>1;
68     if (y<=mid) res=min(res,query(p<<1,l,mid,x,y,wei));
69     else if (x>mid) res=min(res,query(p<<1|1,mid+1,r,x,y,wei));
70     else res=min(res,min(query(p<<1,l,mid,x,mid,wei),query(p<<1|1,mid+1,r,mid+1,y,wei)));
71     return res;
72 }
73 int main()
74 {
75     n=read(),L=read();
76     for (int i=1;i<n;i++)
77         a[i].x=read(),a[i].y=read(),a[i].l=read(),b[++num]=a[i].x,b[++num]=a[i].y;
78     sort(b+1,b+num+1);
79     for (int i=1;i<=num;i++)
80         if (b[i]!=b[i-1]) p[b[i]]=++siz;
81     for (int i=1;i<n;i++)
82         a[i].x=p[a[i].x],a[i].y=p[a[i].y];
83     
84     ins(1,1,siz,1,siz,make_pair(0,0));
85     for (int i=1;i<n;i++)
86     {
87         f[i]=query(1,1,siz,a[i].x,a[i].y,a[i].l)+1;
88         ins(1,1,siz,a[i].x,a[i].y,make_pair(a[i].l,f[i]));
89     }
90     for (int i=1;i<n;i++)
91         printf("%d\n",f[i]>=n?-1:f[i]);
92 }