[线段树标记永久化单调队列] BZOJ 1171 大sz的游戏BZOJ 2892 强袭作战-USB迷|专注于互联网分享

[线段树标记永久化单调队列] BZOJ 1171 大sz的游戏 BZOJ 2892 强袭作战

很好的题解：.html

“考虑裸的n^2暴力dp. dp[i]=min(dp[j])+1 ( d[i]-d[j]<=L && [xi,yi]∪[xj,yj]!=∅)

由于第二个相对较难处理，首先考虑它. 把x,y离散化后搞个线段树，支持插入删除一个区间的答案，并且询问区间的答案即可.

关于如何维护区间里的答案，虽然答案是有可能被删除的，但由于满足单调性，考虑在区间里套个单调队列.

具体来说，for 循环到i,删掉一些dist大于L的区间答案，再到线段树中去询问至少覆盖了[xi,yi]的其中一部分的最小答案，用之求得dp[i]，再在线段树[xi,yi]插入dp[i]这个答案. 单调队列实在是比较显然，就不说了.

但是要注意这里的线段树是不大方便用lazy下传的，而且到达能被其完全覆盖的区间节点就插入，不再往下做了.

这样保证了时间和空间复杂度为o(nlogn)，因为每个星球的区间对应的线段树中的区间节点大概是logn个，该区间的dp值只能被插入到这~logn个单调队列里. blah的.

并且这样，完全覆盖了某个区间节点的最小值，应该是其到根节点路径上所有单调队列维护的值的最小值.

然，至少覆盖了某区间一部分的最小值，即为完全覆盖该区间子区间（包括本身）的最小值的最小值. 如果这是个线段树上的区间节点的话，即为其子树中的所有节点到根的最小值，即为子树到该节点的最小值和该节点到根的最小值. 前者显然用 val[cur]=min(val[cur],val[lson],val[rson]) 维护即可. 后者询问时顺便维护即可.”

#include<cstdio>
#include<cstdlib>
#include<list>
#include<algorithm>
#define oo (1<<30)
using namespace std;inline char nc()
{static char buf[100000],*p1=buf,*p2=buf;if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }return *p1++;
}inline void read (int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') c=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int N=250005;int sx[2*N],icnt;inline int Bin(int x){return lower_bound(sx+1,sx+icnt+1,x)-sx;
}int val[N*8];
list<int> Lis[N*8];int n,L;
int d[N],x[N],y[N];
int dp[N];
int Q[N],l,r;void build(int rt,int l,int r){val[rt]=oo;int mid=(l+r)>>1;if (l!=r)build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
}inline int get(int rt)
{return !Lis[rt].empty()?dp[Lis[rt].front()]:oo; 
}void modify(int k,int rt,int l,int r,int L,int R,int pos)
{if (L<=l && r<=R){if (k){while (!Lis[rt].empty() && Lis[rt].front()<=pos) Lis[rt].pop_front();}else{while (!Lis[rt].empty() && dp[pos]<=dp[Lis[rt].back()]) Lis[rt].pop_back();Lis[rt].push_back(pos);}}else{int mid=(l+r)>>1;if (R<=mid) modify(k,rt<<1,l,mid,L,R,pos);else if (L>mid) modify(k,rt<<1|1,mid+1,r,L,R,pos);else{modify(k,rt<<1,l,mid,L,mid,pos);modify(k,rt<<1|1,mid+1,r,mid+1,R,pos);}}val[rt]=min(get(rt),(l==r)?oo:min(val[rt<<1],val[rt<<1|1]));
}int query(int rt,int l,int r,int L,int R)
{if (R<l || L>r) return oo;if (L<=l && r<=R) return val[rt];int ret=get(rt);if (l!=r){int mid=(l+r)>>1;ret=min(ret,query(rt<<1,l,mid,L,R));ret=min(ret,query(rt<<1|1,mid+1,r,L,R));}	return ret;
}int main()
{freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n); read(L);for (int i=1;i<n;i++){read(x[i]),read(y[i]),read(d[i]);sx[++icnt]=x[i]; sx[++icnt]=y[i];}sort(sx+1,sx+icnt+1);icnt=unique(sx+1,sx+icnt+1)-sx-1;for (int i=1;i<n;i++)x[i]=Bin(x[i]),y[i]=Bin(y[i]);build(1,1,icnt);x[0]=1; y[0]=icnt;l=r=-1; dp[0]=d[0]=0;Q[++r]=0;modify(0,1,1,icnt,x[0],y[0],0);for (int i=1;i<n;i++){while (l<r && d[i]-d[Q[l+1]]>L) {int u=Q[++l];modify(1,1,1,icnt,x[u],y[u],u);}dp[i]=query(1,1,icnt,x[i],y[i]);if (dp[i]!=oo){printf("%d\n",++dp[i]);modify(0,1,1,icnt,x[i],y[i],i);Q[++r]=i;}else{printf("-1\n");}}return 0;
}