【BZOJ-2892&1171】强袭作战&大sz的游戏 权值线段树+单调队列+标记永久化+DP

时间:2021-12-21 16:24:26

2892: 强袭作战

Time Limit: 50 Sec  Memory Limit: 512 MB
Submit: 45  Solved: 30
[Submit][Status][Discuss]

Description

在一个没有冬马的世界里,经历了学园祭后的春希着急着想要见到心爱的雪菜。然而在排队想见雪菜的fans太多了,春希一时半会凑不到雪菜面前。
作为高帅富,这样的问题怎么能难倒春希?春希从武也手中拿到了取自金闪闪宝库里的多啦A梦的传话筒,并且给每一个排队的fans都发了一个传话筒。
于是现在有N个人排成一列,第一个人是雪菜,后面N个人是雪菜的fans。第I个fan能在他的左侧中选一个距离不超过L的人发出频率在[xi,yi]的音波,并且第I个fan也能接受频率在[xi,yi]的音波。特别的,雪菜能接受所有频率的音波。
春希有些话想通过传话筒告诉雪菜,他想选择一个人作为传话的起始点,但不知道选谁比较好,作为春希的好友的你,能告诉他答案吗?
传话的具体解释:第I个人能选择其左边的距离不超过L的一个人J,只要双方对应的区间有交集,那么第I个人就能将信息传达给J。然后J又可以继续找下一个人传达信息。传达一次信息要1单位时间。

Input

第一行两个正整数N、L。接下来N-1行,第i行包含了三个正整数xiyili,其中li表示第i个人距离雪菜有li的距离,满足li严格递增。

Output

总共N-1行,每行一个数分别表示2到N号fan至少需要多少单位时间,雪菜才能收到信息,如果无法传到雪菜则输出-1。

Sample Input

3 1
1 2 1
2 3 2

Sample Output

1
2
【数据规模和约定】
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

1171: 大sz的游戏

Time Limit: 50 Sec  Memory Limit: 357 MB
Submit: 320  Solved: 98
[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 俞华程

Solution

线段树标记永久化+单调队列+DP

首先一眼DP:  $dp[i]=min(dp[j])+1$ 其中 $\left | l[i]-l[j] \right |<L,\left [ x[i],y[i] \right ]\bigcap \left [ x[j],y[j] \right ]\neq \O $

那么需要优化复杂度,考虑利用数据结构(可以利用很多种,这里选用权值线段树+单调队列)

x[],y[]范围过大,单很稀疏,离散,建权值线段树,支持区间修改区间查询;维护区间中的答案,需要在区间中加入一个单调队列

发现标记不适合下传,即标记需要永久化,和之前维护直线的思想类似,这样复杂度就一样能保证在$O(nlogn)$

如果当前区间完全覆盖,则不需要下传;维护的最小值,即区间的单调队列队首,和左右区间的最小三者取最小

查询的时候查询有交集的所有区间,线段树中节点的信息只是维护了完全包含于这个区间的区间的信息,我们还需要知道和这个区间有交集的但不包含于这个区间的信息,所以往子树递归的时候把路径上的信息也一块统计就好啦。

总结:

1.标记永久化的思想更加加深

2.对于类似这样的单调的问题,同样可以用线段树去维护,据说类似问题线段树是比CDQ之类还要无敌的??

3.对于每个线段树区间套上单调队列时,容易爆,开始手写单调队列,炸编译,改成动态RE,所以可以考虑用<list>

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<list>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 250010
#define inf 0x7fffffff
int N,L,tot,ls[maxn<<],val[maxn<<],dp[maxn],que[maxn],x[maxn],y[maxn],l[maxn];
struct DQueueNode{list<int>q;}Tree[maxn<<];
int Get(int now) {return !Tree[now].q.empty()?dp[Tree[now].q.front()]:inf;}
void update(int now,int l,int r) {val[now]=min(Get(now),(l==r)?inf:min(val[now<<],val[now<<|]));}
void Build(int now,int l,int r)
{
val[now]=inf;
if (l==r) return;
int mid=(l+r)>>;
Build(now<<,l,mid); Build(now<<|,mid+,r);
}
void Insert(int now,int l,int r,int L,int R,int x,int f)
{
if (L<=l && R>=r)
{
if (f) while (!Tree[now].q.empty() && Tree[now].q.front()<=x) Tree[now].q.pop_front();
else {while (!Tree[now].q.empty() && dp[Tree[now].q.back()]>=dp[x]) Tree[now].q.pop_back(); Tree[now].q.push_back(x);}
update(now,l,r);
return;
}
int mid=(l+r)>>;
if (L<=mid) Insert(now<<,l,mid,L,R,x,f);
if (R>mid) Insert(now<<|,mid+,r,L,R,x,f);
update(now,l,r);
}
int Query(int now,int l,int r,int L,int R)
{
if (L<=l && R>=r) return val[now];
int mid=(l+r)>>,re=Get(now);
if (L<=mid) re=min(re,Query(now<<,l,mid,L,R));
if (R>mid) re=min(re,Query(now<<|,mid+,r,L,R));
return re;
}
int main()
{
N=read(),L=read();
for (int i=; i<=N-; i++) ls[++tot]=x[i]=read(),ls[++tot]=y[i]=read(),l[i]=read();
sort(ls+,ls+tot+);
int Tot=; for (int i=; i<=tot; i++) if (ls[i]!=ls[i-]) ls[++Tot]=ls[i];
for (int i=; i<=N-; i++) x[i]=lower_bound(ls+,ls+Tot+,x[i])-ls,y[i]=lower_bound(ls+,ls+Tot+,y[i])-ls;
Tot=unique(ls+,ls+Tot+)-ls-;
// for (int i=1; i<=N-1; i++) printf("%d %d\n",x[i],y[i]);
Build(,,Tot);
int he=-,ta=-; dp[]=; x[]=,y[]=Tot; que[++ta]=;
Insert(,,Tot,x[],y[],,);
for (int i=; i<=N-; i++)
{
int tmp;
while (he<ta && l[i]-l[que[he+]]>L) tmp=que[++he],Insert(,,Tot,x[tmp],y[tmp],tmp,);
dp[i]=Query(,,Tot,x[i],y[i])+;
if (dp[i]!=inf+) printf("%d\n",dp[i]),que[++ta]=i,Insert(,,Tot,x[i],y[i],i,);
else puts("-1");
}
return ;
}