BZOJ1171: 大sz的游戏&BZOJ2892: 强袭作战

时间：2021-12-21 16:23:44

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．
 
就这么出双倍经验题好么？
考虑DP，设f[i]表示从1到i号星球最少步数，则f[i]=min(f[j]+1|[xj,yj]∩[xi,yi]!=Φ)。
变形一下，f[i]=min(f[j]+1|xj<=yi&&yj>=xi)，这样就变成一个简单的二维偏序结构了，找一个支持在平面直角坐标系上增加删除点，询问区域最小值的数据结构就行了。
使用树套树或kd树或线段树分治+扫描线都可以，我使用了一棵kd树，不知道为什么跑得很慢，加上定期重构才通过。
#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define L T[o].lc

#define R T[o].rc

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define ren for(int i=first[x];i;i=next[i])

using namespace std;

const int BufferSize=1<<16;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

	if(head==tail) {

		int l=fread(buffer,1,BufferSize,stdin);

		tail=(head=buffer)+l;

	}

	return *head++;

}

inline int read() {

    int x=0,f=1;char c=Getchar();

    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';

    return x*f;

}

const int maxn=250010;

const int inf=2e9;

int n,len,D,rt,ToT;

int x[maxn],y[maxn],p[maxn];

struct Node {

	int x[2],mx[2],mn[2],minv,del;

	int lc,rc,val;

	bool operator < (const Node& ths) const {

		if(ths.x[D]!=x[D]) return x[D]<ths.x[D];

		if(ths.x[D^1]!=x[D^1]) return x[D^1]<ths.x[D^1];

		return val<ths.val;

	}

	bool operator == (const Node& ths) const {

		return x[0]==ths.x[0]&&x[1]==ths.x[1]&&val==ths.val;

	}

}T[maxn],A;

void maintain(int o) {

	T[o].minv=min(T[L].minv,T[R].minv);

	if(!T[o].del) {

		T[o].minv=min(T[o].minv,T[o].val);

		T[o].mx[0]=T[o].mn[0]=T[o].x[0];

		T[o].mx[1]=T[o].mn[1]=T[o].x[1];

	}

	rep(c,0,1) {

		T[o].mx[c]=max(T[o].mx[c],max(T[L].mx[c],T[R].mx[c]));

		T[o].mn[c]=min(T[o].mn[c],min(T[L].mn[c],T[R].mn[c]));

	}

}

void insert(int& o,int cur) {

	if(!o) T[o=++ToT]=A;

	else D=cur,insert(A<T[o]?L:R,cur^1);

	maintain(o);

}

void remove(int& o,int cur) {

	if(!o) {puts("2333");return;}

	if(!T[o].del&&T[o]==A) T[o].del=1;

	else D=cur,remove(A<T[o]?L:R,cur^1);

	maintain(o);

}

int query(int& o,int a,int b) {

	if(!o) return inf;

	int res=inf;

	if(T[o].mn[0]>b||T[o].mn[1]>a) return inf;

	if(T[o].mx[0]<=b&&T[o].mx[1]<=a) return T[o].minv;

	if(!T[o].del&&T[o].x[0]<=b&&T[o].x[1]<=a) res=min(res,T[o].val);

	if(T[L].mn[0]<=b&&T[L].mn[1]<=a) res=min(res,query(L,a,b));

	if(T[R].mn[0]<=b&&T[R].mn[1]<=a) res=min(res,query(R,a,b));

	return res;

}

void build(int& o,int l,int r,int cur) {

	o=0;if(l>r) return;

	int mid=l+r>>1;o=mid;D=cur;

	nth_element(T+l,T+mid,T+r+1);

	build(L,l,mid-1,cur^1);

	build(R,mid+1,r,cur^1);

	maintain(o);

}

void rebuild() {

	int m=0;

	rep(i,1,ToT) if(!T[i].del) T[++m]=T[i];

	build(rt,1,ToT=m,0);

}

int f[maxn];

int main() {

	T[0].mx[0]=T[0].mx[1]=-inf;

	T[0].mn[0]=T[0].mn[1]=T[0].minv=inf;

	n=read();len=read();x[1]=0;y[1]=inf;

	rep(i,2,n) x[i]=read(),y[i]=read(),p[i]=read();

	int cur=1;A.x[0]=0;A.x[1]=-inf;A.val=0;

	insert(rt,0);

	rep(i,2,n) {

		f[i]=inf;

		while(p[i]-p[cur]>len) {

			A.x[0]=x[cur];A.x[1]=-y[cur];A.val=f[cur];

			remove(rt,0);cur++;

		}

		f[i]=min(f[i],query(rt,-x[i],y[i])+1);

		A.x[0]=x[i];A.x[1]=-y[i];A.val=f[i];insert(rt,0);

		if(i%800==0) rebuild();

	}

	rep(i,2,n) printf("%d\n",f[i]==inf?-1:f[i]);

	return 0;

}

　　

相关文章