CF1710B Rain

纪念一下赛时想出正解细节调炸心态。

找性质+二维偏序

首先拿到题没啥思路，感觉可能是高妙的数据结构但是不会。

硬着头皮写下式子：

• 对于 $j\in [x_i-p_i,x_i]$ 水位增加 $p_i-x_i+j$。

• 对于 $j\in (x_i,x_i+p_i]$ 水位增加 $p_i-j+x_i$。

可以发现最后 $j$ 位置的水位只与一个由 $p_i,x_i$ 得到的常数和 $j$ 有关，进一步发现这其实就是一个一次函数。某一次的修改会使得某个区间的函数发生改变，但始终是一次。

不妨另 $w_j=a_j+b_j\times j$，进行区间加即可预处理出每个位置的最终水位。

那么既然是一次函数了，那么极值肯定就在端点取到了。

那么不妨设 $x_i,x_i-p_i,x_i+p_i$ 为关键点，那么折线的拐点只会在这些点取到，接下来我们将只看这些关键点。

考虑水位 $>m$ 的点 $j$，标出坐标 $(j,w_j-m)$。

不妨将一场雨的影响画成一个等腰直角三角形。

如果有一个等腰直角三角形把上面标出的点全部包含，那么即意味着这场雨被消除后所有点水位都 $\leq m$。

然后把你手上的草稿纸旋转 $45\degree$,你就会发现要求的就是所有点都被包含在一个矩形中，搞搞二维偏序就行了。

可能会有一个疑问就是盖住标记点是否就能消除全部影响，即盖住整个折线。其实因为折现斜率要么是 $0$ ，也就是平的，这条线的另一头夜视被标记的点。要么斜率的绝对值 $\geq 1$，方向相同的话最多就是与当前的线平行，不可能越出这个三角形，如果方向相反则会产生另一个标记点。

异常丑陋及常数大的赛时改版代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
#define grep(b,c) for(int c(head[b]);c;c=nxt[c])
#define Clear(a,n) memset(a,0,((n)+3)*sizeof(a[0]))
typedef long long LL;
#define int LL

inline int read()
{
	int res=0;char ch=getchar();bool flag=0;while(ch<'0'||ch>'9')flag^=(ch=='-'),ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return flag ? -res : res ;
}
inline void print(LL x){if(x>9)print(x/10);putchar(x%10+'0');}
template<typename T> inline T min(const T&x,const T&y){return x<y?x:y;}
template<typename T> inline T max(const T&x,const T&y){return x<y?y:x;}
template<typename T> inline T Swap(T&x,T&y){T tmp=x;x=y;y=tmp;}
template<typename T> inline T Abs(T&x){return x<0?-x:x;}

const int N=1.2e6+10;int Pos[N<<1],P,x[N],p[N],n,m,a[N],b[N],BIT[N<<1];
inline void Add(int p,int w){while(p<=P)BIT[p]+=w,p+=(p&-p);}
inline int Qry(int p){int res=0;while(p)res+=BIT[p],p^=(p&-p);return res;}
inline int bnd(int k){int l=1,r=P,m;while(l<=r)Pos[m=(l+r)>>1]<=k?l=m+1:r=m-1;return l-1;}
inline void add(int *a,int l,int r,int w){a[l]+=w;a[r+1]-=w;}
struct node{int x,y;}t[N];int tot,ans[N];std::vector<int> Op[N<<1],Qy[N<<1];
inline void Solve()
{
	n=read();m=read();rep(1,n,i)
	{
		x[i]=read();p[i]=read();
		Pos[++P]=x[i]-p[i];Pos[++P]=x[i]+p[i];Pos[++P]=x[i];
	}
	std::sort(Pos+1,Pos+P+1);P=std::unique(Pos+1,Pos+P+1)-Pos-1;
	memset(a,0,(P+3)*sizeof(a[0]));
	memset(b,0,(P+3)*sizeof(b[0]));
	rep(1,n,i)
	{
		int l=bnd(x[i]-p[i]),m=bnd(x[i]),r=bnd(x[i]+p[i]);
		add(a,l,m,p[i]-x[i]);add(b,l,m,1);
		add(a,m+1,r,p[i]+x[i]);add(b,m+1,r,-1); 
	}//差分预处理关键点的水位
	tot=0;rep(1,P,i)
	{
		a[i]+=a[i-1];b[i]+=b[i-1];int W=a[i]+b[i]*Pos[i]-m;
		if(W>0)t[++tot]=(node){Pos[i]+W,W-Pos[i]}; 
	}//标出标记点并旋转45度
	P=0;rep(1,tot,i)Pos[++P]=t[i].x,Pos[++P]=t[i].y;
	rep(1,n,i){Pos[++P]=x[i]+p[i];Pos[++P]=p[i]-x[i];}
	std::sort(Pos+1,Pos+P+1);P=std::unique(Pos+1,Pos+P+1)-Pos-1;
	rep(1,P,i)Op[i].clear(),Qy[i].clear();
	rep(1,tot,i)Op[bnd(t[i].x)].push_back(bnd(t[i].y));
	rep(1,n,i){Qy[bnd(x[i]+p[i])].push_back(i);}
	memset(BIT,0,(P+3)*sizeof(BIT[0]));
	memset(ans,0,(n+3)*sizeof(ans[0]));
	rep(1,P,X)
	{
		for(int v:Op[X])Add(v,1);
		for(int i:Qy[X]){ans[i]=Qry(bnd(p[i]-x[i]));}
	}
	//离线做二维偏序 
	rep(1,n,i)putchar(ans[i]==tot?'1':'0');putchar('\n');
}

signed main()
{
//	FIN("data.txt");
	int T=read();
	while(T--)Solve();
	return 0;
}