洛谷题目传送门

题目描述

到冬天了，这意味着下雪了！从农舍到牛棚的路上有 N 块地砖，方便起见编号为 1…N，第 i 块地砖上积了 ​ 英尺的雪。 在 Farmer John 的农舍的地窖中，总共有 B 双靴子，编号为 1…B。其中某些比另一些结实，某些比另一些轻便。具体地说，第 i 双靴子能够让 FJ 在至多 si​ 英尺深的积雪中行走，能够让 FJ 每步至多前进 ​。

Farmer John 从 1 号地砖出发，他必须到达 N 号地砖才能叫醒奶牛们。1 号地砖在农舍的屋檐下，N 号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。帮助 Farmer John 求出哪些靴子可以帮助他走完这段艰辛的路程。

输入格式

第一行包含两个空格分隔的整数 N 和 B（1≤N,B≤）。
第二行包含N个空格分隔的整数；第 i 个整数为 ，即 i 号地砖的积雪深度（0≤​≤）。输入保证 ​=​=0。

下面 B 行，每行包含两个空格分隔的整数。第 i+2 行的第一个数为 ，表示第 i 双靴子能够承受的最大积雪深度。第 i+2 行的第二个数为 ，表示第 i 双靴子的最大步长。输入保证 0≤≤ 以及 1≤≤N−1。

输出格式

输出包含 B 行。第 i 行包含一个整数：如果 Farmer John 能够穿着第 i 双靴子从 1 号地砖走到 N 号地砖，为 1，否则为 0。

题意翻译

输入输出样例

输入 

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

输出

0
1
1
0
1
1
1

思路

我们把每个地砖看作步长为 0 的鞋子，每当我们遇到一个地砖就把他加入到地面，每遇到步长大于 0 的，就访问。

我们发现，如果我们把所有鞋子按深度递增排序，遇到步长大于 0 的，就不需要考虑深度，只需要考虑步长

如果每两个相邻地砖之间的距离(不包括端点)都小于这个鞋子的步长，则就可以穿这双鞋子走过去

我们定义 dp[ i ] 表示以第 i 个位置结束的连续没有地砖的长度

我们只需要用一个线段树去维护 dp[ i ]的最大值

我们考虑每个地砖加入时 dp 该如何变化

如:

 原来是：

编号: 1  2  3  4  5  6
vis : 1  0  0  0  0  1
dp  : 0  1  2  3  4  0 

在位置 4 加入一块地砖：

编号: 1  2  3  4  5  6
vis : 1  0  0  1  0  1
dp  : 0  1  2 3-3 4-3  0 

我们发现如果我们在 i 点加入一块地砖，那么 i 直到 i 后的   第一个 vis 值为1的点   的前一个点j

的dp值都要减少 dp[ i ]，因为 i 点dp变为0了，后面点都要依次向后加，直到下一块vi值为0

那么对于每一次修改，如果我们要在 i 加入一块地砖，我们只需要暴力求出点 j，将区间

[ i , j ]都减去dp[i]就可以了

注意一点，我们求出每一个询问的答案时不能直接输出，因为顺序是乱的。我们应先把他保存下来，最后输出就可以了

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
struct tre{
	int l,r,data,lzy;//data 保存最大值 
};
int b[N],c[N];//b 为dp的初始数组 
class segment_tree{//线段树 
private:
	tre tree[N*4];
public:
	void add(int u,int v){
		tree[u].data+=v;tree[u].lzy+=v;
	}
	void pushup(int u){
		tree[u].data=max(tree[u<<1].data,tree[u<<1|1].data);
	}
	void pushdown(int u){
		add(u<<1,tree[u].lzy);add(u<<1|1,tree[u].lzy);
		tree[u].lzy=0;
	}
	void build(int u,int l,int r){
		tree[u]={l,r,0,0};
		if(l==r){tree[u].data=b[l];return;}
		int mid=l+r>>1;
		build(u<<1,l,mid);build(u<<1|1,mid+1,r);
		pushup(u);
	}
	void chang(int u,int x,int y,int v){//区间修改 
		if(tree[u].l>y||tree[u].r<x)return;
		if(tree[u].l>=x&&tree[u].r<=y){add(u,v);return;}
		pushdown(u);
		chang(u<<1,x,y,v);chang(u<<1|1,x,y,v);
		pushup(u);
	}
	int getx(int u,int x){//单点查询 
		if(tree[u].l>x||tree[u].r<x)return 0;
		if(tree[u].l==tree[u].r&&tree[u].r==x){return tree[u].data;}
		pushdown(u);
		return max(getx(u<<1,x),getx(u<<1|1,x));
	}
	int getmax(int u,int x,int y){//区间访问 
		int l=tree[u].l,r=tree[u].r;
		if(y<l||x>r)return -0x3f3f3f3f;
		if(x<=l&&r<=y)return tree[u].data;
		int maxx=-INF;
		pushdown(u);
		maxx=max(maxx,getmax(u<<1,x,y));maxx=max(maxx,getmax(u<<1|1,x,y));
		return maxx;
	}
}t1;
int n,m,o;
struct S{
	int x,y,z,id;//x为深度，y为步长，z为砖的位置，id为鞋子的编号 
	friend bool operator<(S t1,S t2){//按深度排序，辅之以步长排序 
		return t1.x==t2.x?t1.y<t2.y:t1.x<t2.x;
	}
}a[N*2];
int ans[N];//保存答案 
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[++o].x;a[o].y=0;a[o].z=i;b[i]=i;
	}
	for(int i=1;i<=m;i++){
		o++;
		cin>>a[o].x>>a[o].y;
		a[o].z=0;a[o].id=i;
	}
	t1.build(1,1,n);//一定要记得建树 
	sort(a+1,a+1+o);
	c[n+1]=1;
	for(int i=1;i<=o;i++){
		if(a[i].y==0){
			int en;
			for(int j=a[i].z+1;j<=n+1;j++){//暴力求解右区间 
				if(c[j]==1){en=j;break;}
			}
			t1.chang(1,a[i].z,en-1,-t1.getx(1,a[i].z));//修改区间，注意i与a[i].z不要搞混了 
			c[a[i].z]=1;
		}
		else {
			ans[a[i].id]=(t1.getmax(1,1,n)<a[i].y);//保存答案 
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}