自动搬运

查看原文

来自洛谷，原作者为

	Meatherm 个人博客：https://www.cnblogs.com/Meatherm | QQ：2725908309 欢迎大家加 Q！说不定我就认识一位未来的 NOI / IOI 选手了呢hhhh

搬运于2025-08-24 21:53:30，当前版本为作者最后更新于2019-11-28 13:07:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如果只有一个数，似乎就很好维护了。

维护每一个时刻这个数加上的值。查询某一段时间里大于某个值的时间数量。将时间分块就可以做了。

但如果是 $n$ 个数呢？如果在线搞的话，似乎并不能很好的维护。那么离线下来，给询问排序，依次处理就好了。

那怎么处理区间修改操作呢？观察到如果在 $t$ 时刻给 $[l,r]$ 加上 $v$，会对处理 $[l,r]$ 中每一个数时都造成同样的影响。所以将每一个修改操作分成两部分：

• 第一部分，在处理第 $l$ 个数的时候将时刻 $[t,m]$ 都加上 $v$。
• 第二部分，在处理第 $r+1$ 个数的时候将时刻 $[t,m]$ 都减去 $v$，抵消影响（因为这个操作不会对 $r+1$ 及其之后的数造成影响，故减去）。

（是不是感觉有点像扫描线呢）

这样我们就可以得到每一个数每个时刻被加上的值。

处理第 $i$ 个数第 $t$ 秒的询问时，分块查询 $[0,t-1]$ 有多少个时刻的值大于等于 $y - a_i$ 即可。

注意到最后输出结果时是按照输入顺序输出，所以还要处理一下询问的顺序。

# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=100010;
struct Line{//修改
	int x;
	int Time;
	int v;
}a[N<<1];
struct Asker{//查询
	int x,v; 
	int Time;
	int Index;// 记录是第几次询问
}ask[N];
int cnta,cntb;//修改数量 & 查询数量
int ans[N]; // 存储每一次询问的答案
int val[N];
int n,m;
/* 分块部分 */
int tseque[N];
int fseque[N];
int add[N];
int Kuai[N];
int KL[N],KR[N];
/* 分块部分 */
int siz;// 要分的块大小
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')	
		res=res*10+c-48;
	return res*f;		
}
inline bool cmp_Line(Line X,Line Y){//给修改排序
	return X.x!=Y.x?X.x<Y.x:X.Time<Y.Time;
}
inline bool cmp_Ask(Asker X,Asker Y){//给询问排序
	return X.x!=Y.x?X.x<Y.x:X.Time<Y.Time;
}
inline bool cmp_Integer(int X,int Y){//为了给块内元素从大到小排序用的
	return X>Y;
}
inline void resort(int x){//每次修改之后，块内元素需要重新排序
	for(rr int i=KL[x];i<=KR[x];++i)
		fseque[i]=tseque[i];
	std::sort(fseque+KL[x],fseque+KR[x]+1,cmp_Integer);
	return;	
}
inline void change(int l,int r,int v){// 分块修改操作
	l=std::max(l,0ll);
	r=std::min(r,m);
	if(Kuai[l]==Kuai[r]){
		for(rr int i=l;i<=r;++i){
			tseque[i]+=v;
		}
		resort(Kuai[l]);
		return;
	}
	for(rr int i=l;i<=KR[Kuai[l]];++i)
		tseque[i]+=v;
	resort(Kuai[l]);
	for(rr int i=r;i>=KL[Kuai[r]];--i)
		tseque[i]+=v;
	resort(Kuai[r]);
	for(rr int i=Kuai[l]+1;i<=Kuai[r]-1;++i){
		add[i]+=v;
	}
	return;
}
inline int query(int l,int r,int v){// 分块查询操作
	int cnt=0;
	if(Kuai[l]==Kuai[r]){
		for(rr int i=l;i<=r;++i)
			if(tseque[i]+add[Kuai[i]]>=v)
				++cnt;
		return cnt;		
	}
	for(rr int i=l;i<=KR[Kuai[l]];++i)
		if(tseque[i]+add[Kuai[i]]>=v)
			++cnt;
	for(rr int i=r;i>=KL[Kuai[r]];--i)
		if(tseque[i]+add[Kuai[i]]>=v)
			++cnt;
	for(rr int i=Kuai[l]+1;i<=Kuai[r]-1;++i){
		int L=KL[i],R=KR[i],ans=KL[i]-1;
		while(L<=R){
			int mid=(L+R)>>1;
			if(fseque[mid]+add[Kuai[mid]]>=v){
				ans=mid;
				L=mid+1;
			}else{
				R=mid-1;
			}
		}
		cnt+=(ans-KL[i])+1;
	}
	return cnt;
}
# undef int
int main(void){
# define int long long
	n=read(),m=read();
	for(rr int i=1;i<=n;++i){
		val[i]=read();
	}
	for(rr int i=1,opt;i<=m;++i){
		opt=read();
		if(opt==1){
			int l=read(),r=read(),v=read();
			a[++cnta].x=l;
			a[cnta].Time=i;
			a[cnta].v=v;
			a[++cnta].x=r+1;
			a[cnta].Time=i;
			a[cnta].v=-v;
		}else{
			int p=read(),y=read();
			ask[++cntb].x=p;
			ask[cntb].Index=cntb;
			ask[cntb].v=y;
			ask[cntb].Time=i;
		}
	}
	std::sort(a+1,a+1+cnta,cmp_Line);
	std::sort(ask+1,ask+1+cntb,cmp_Ask);// 读入、存储并排序每一个操作
	siz=sqrt(m);
	for(rr int i=0;i<=m;++i){
		Kuai[i]=i/siz+1;
	}
	for(rr int i=1;(i-1)*siz<=m;++i){
		KL[i]=(i-1)*siz;
		KR[i]=std::min(i*siz-1,m);
	}
	int now=1;
	for(rr int i=1;i<=cntb;++i){
		while((a[now].x<ask[i].x||(a[now].x==ask[i].x&&a[now].Time<ask[i].Time))&&now<=cnta){
			change(a[now].Time,m,a[now].v);
			++now;
		}
		ans[ask[i].Index]=query(0,ask[i].Time-1,ask[i].v-val[ask[i].x]);
	}
	for(rr int i=1;i<=cntb;++i)
		printf("%lld\n",ans[i]);
	return 0;
}