比赛 |
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;
}