bzoj 1171 大sz的戏& 2892 强袭作战 (线段树+单调队列+永久性flag)

大sz的游戏

Time Limit: 50 Sec  Memory
Limit: 357 MB
Submit: 536  Solved: 143
[Submit][Status][Discuss]

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

input1
3 1
1 2 1
2 3 2
input 2
3 3
1 2 1
2 3 2

Sample Output

output1
1
2
output2
1
1
30%之多寡满足N <=20000;
100%底数据满足2 <=N<=
2.5*10^5、0<=xi,yi,li<=2*10^9,1<=L<=2*10^9,xi<=yi.

HINT

 

Source

By
俞华程

 

题解

    发现相差有单调性质,所以可以想到单调性航天科技,将xi,xj抽象成一长线条,

    发现当半漫漫线段发生混合的下又,距离满足条件时是可转移的,

    那么怎样考虑也?

    发现好拿xi,xj离散化,这样的话,就好以线段树一截距离中寻找最小值,

    但是出现一个题材,最小值是休能够去的,就是距不满足了,怎么去

    无法成功,所以待以每个点吃开一个枯燥队列,这才是及时道题目的困难。

    

    先了解一个概念,什么叫永久性flag,对于常见的flag,是无是索要标记下传

    也就是说,标记不是定点的,二永久性标记,顾名思义就是免欲下传标记,

        航天科技 1

    比如革命线段是待摸索的,那么对于包括这条线段的,并且是满足整长达线段包括的

    我的代码中分成一个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 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注