120565I

https://ac.nowcoder.com/acm/contest/120565/I

（不管怎么样数据结构还是没有白学）

非常暴力的做法。

注意到一次操作可以看着的差分序列，显然可以用区间修改的线段树维护。于是问题转化成：每次操作后，是否存在一个位置，的前缀和。

那么我们可以很快得到一组数据的答案是Yes还是No：只要在操作完之后逐一检查前缀和即可。但怎么找具体是从哪一次操作开始的呢？不难发现，这一次操作是一个分水岭：它和它后面一定都超过了，前面一定没超过。于是我们可以把操作记录下来，二分答案即可。时间复杂度。

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
long long h;
struct o{
	long long val,lan;
}tree[5000100];
struct oo{
	int p;
	long long f;
}a[1000100];
int ls(int k){return k<<1;}
int rs(int k){return k<<1|1;}
void add(int k,int l,int r,long long v){
	tree[k].val+=(r-l+1)*v;
	tree[k].lan+=v;
}
void pud(int k,int l,int r,int mid){
	if(tree[k].lan){
		add(ls(k),l,mid,tree[k].lan);
		add(rs(k),mid+1,r,tree[k].lan);
		tree[k].lan=0;
	}
}
void change(int k,int l,int r,int x,int y,long long v){
	if(x<=l&&y>=r){
		add(k,l,r,v);
		return;
	}
	int mid=(l+r)>>1;
	pud(k,l,r,mid);
	if(x<=mid) change(ls(k),l,mid,x,y,v);
	if(y>mid) change(rs(k),mid+1,r,x,y,v);
	tree[k].val=tree[ls(k)].val+tree[rs(k)].val;
}
long long ask(int k,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return tree[k].val;
	}
	int mid=(l+r)>>1;
	long long res=0;
	pud(k,l,r,mid);
	if(x<=mid) res=ask(ls(k),l,mid,x,y);
	if(y>mid) res+=ask(rs(k),mid+1,r,x,y);
	return res;
}
long long read(){
	char ch=getchar();long long x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int pd(){
	for(int i=1;i<=n;i++){
		if(ask(1,1,n,1,i)>h){
			return 1;
		}
	}
	return 0;
}
int main(){
	n=read();m=read();h=read();
	for(int i=1;i<=m;i++){
		int p=read();
		long long f=read();
		a[i].p=p;a[i].f=f;
		else{
			if(p>1)	change(1,1,n,2,p,1);
			change(1,1,n,1,1,f-p+1);
		}
		if(p<n) change(1,1,n,p+1,min(p+f,(long long)n),-1);
	}
	if(!pd()){
		puts("No");
		return 0;
	}
	int l=1,r=m,now=m;
	while(l<r){
		int mid=(l+r)>>1;
		while(now<mid&&now<=m){
			now++;
			int p=a[now].p;
			long long f=a[now].f;
			if((long long) p-f+1>=1) change(1,1,n,max(1ll,p-f+1),p,1);
			else{
				if(p>1)	change(1,1,n,2,p,1);
				change(1,1,n,1,1,f-p+1);
			}
			if(p<n) change(1,1,n,p+1,min(p+f,(long long)n),-1);
		}
		while(now>mid&&now>=0){
			int p=a[now].p;
			long long f=a[now].f;
			if((long long) p-f+1>=1) change(1,1,n,max(1ll,p-f+1),p,-1);
			else{
				if(p>1)	change(1,1,n,2,p,-1);
				change(1,1,n,1,1,-f+p-1);
			}
			if(p<n) change(1,1,n,p+1,min(p+f,(long long)n),1);
			now--;
		}
		if(pd()){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	puts("Yes");
	printf("%d",l);
	return 0;
}