比赛 2024.5.23练习赛 评测结果 WWWWWWEEEE
题目名称 新年快乐! 最终得分 0
用户昵称 Untitled 运行时间 7.945 s
代码语言 C++ 内存使用 15.23 MiB
提交时间 2024-05-23 20:05:53
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int const N=100010;
int n,m,res;
ll k,a[N];
struct node{
	ll add;
	int l,r,cnt;
	ll minn,maxx;
} t[N<<2];

void pushup(int p){
	int l=p<<1,r=l|1;
	if (t[l].maxx>t[r].maxx) t[p].maxx=t[l].maxx;
	else t[p].maxx=t[r].maxx;
	if (t[l].minn<t[r].minn) t[p].minn=t[l].minn;
	else t[p].minn=t[r].minn;
	t[p].maxx+=t[p].add,t[p].minn+=t[p].add;
	t[p].add=0;
	return;
}

void pushdown(int p){
	t[p].maxx+=t[p].add,t[p].minn+=t[p].add;
	t[p<<1].add+=t[p].add,t[p<<1|1].add+=t[p].add,t[p].add=0;
	return;
}

void init(int p,int L,int R){
	t[p].l=L,t[p].r=R;
	if (L==R){
		t[p].cnt=1;
		t[p].minn=a[L],t[p].maxx=a[L];
		return;
	}
	int mid=(L+R)>>1;
	init(p<<1,L,mid);init(p<<1|1,mid+1,R);
	t[p].cnt=t[p<<1].cnt+t[p<<1|1].cnt;
	pushup(p);
	return;
}

void add(int p,int L,int R,ll v){
	int l=t[p].l,r=t[p].r;
	if (r<L || R<l) return;
	if (l==r){
		t[p].maxx+=v+t[p].add,t[p].minn+=v+t[p].add;
		t[p].add=0;
		return;
	}
	if (L<=l && r<=R){
		t[p].add+=v;
		return;
	}
	pushdown(p);
	add(p<<1,L,R,v);add(p<<1|1,L,R,v);
	pushup(p);
	return;
}

void query(int p,int L,int R){
	int l=t[p].l,r=t[p].r;
	if (r<L || R<l) return;
	if (k<t[p].minn) return;
	pushdown(p);
	if (t[p].maxx<=k){
		res+=t[p].cnt;
		return;
	}
	if (l==r) return;
	query(p<<1,L,R);query(p<<1|1,L,R);
}

int main(){
	freopen("dss.in","r",stdin);
	freopen("dss.out","w",stdout);
	
	int opt,l,r;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	init(1,1,n);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d %d %d %lld",&opt,&l,&r,&k);
		if (opt==1) add(1,l,r,k);
		else{
			res=0;
			query(1,l,r);
			printf("%d\n",res);
		}
	}
	
	return 0;
}