1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define int long long
const int N=200005 ,sqrtN=1005;
int n ,m;
int id[N] ,s[sqrtN] ,t[sqrtN];
int a[N] ,ans[N];
int b[N] ,c[N] ,tag[sqrtN];
struct abc{
int opt ,i ,x ,y ,id;
}q[N];
int cnt;
bool operator<(abc x ,abc y){
return x.x<y.x||(x.x==y.x&&x.i<y.i);
}
bool cmp(abc a ,abc b){
return a.i<b.i;
}
int query(int l ,int r ,int x){
int ans=0;
int L=id[l] ,R=id[r];
if(l>r)return 0;
if(L==R){
for(int i=l;i<=r;i++)
ans+=(b[i]>=x-tag[L]);
return ans;
}
ans+=query(l ,t[L] ,x);
ans+=query(s[R] ,r ,x);
for(int i=L+1;i<R;i++)
ans+=((c+t[i])-lower_bound(c+s[i] ,c+t[i]+1 ,x-tag[i])+1);
return ans;
}
void update(int l, int r ,int x){
if(l>r)return ;
int L=id[l] ,R=id[r];
if(L==R){
for(int i=l;i<=r;i++)
b[i]+=x;
for(int i=s[L];i<=t[L];i++)
c[i]=b[i];
sort(c+s[L] ,c+t[L]+1);
return ;
}
update(l ,t[L] ,x);
update(s[R] ,r ,x);
for(int i=L+1;i<R;i++)
tag[i]+=x;
}
main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=1;i<=m;i++){
int opt ,l ,r ,x;
cin >> opt;
if(opt==1){
cin >> l >> r >> x;
q[++cnt]=(abc){opt ,i ,l ,x ,cnt};
q[++cnt]=(abc){opt ,i ,r+1 ,-x ,cnt};
}
else{
cin >> l >> r;
q[++cnt]={opt ,i ,l ,r ,cnt};
}
}
sort(q+1 ,q+cnt+1);
int L=sqrt(m+1) ,cntt=(m+L-1)/L;
t[0]=-1;
for(int i=1;i<=cntt;i++){
s[i]=t[i-1]+1;
t[i]=min(L*i-1 ,m);
for(int j=s[i];j<=t[i];j++)
id[j]=i;
}
for(int i=1 ,cur=0;i<=cnt;i++){
if(q[i].x>n)break;
if(q[i].x!=cur){
update(0 ,m ,a[q[i].x]-a[cur]);
cur=q[i].x;
}
if(q[i].opt==1){
update(q[i].i ,m ,q[i].y);
}
else{
ans[q[i].id]=query(0 ,q[i].i-1 ,q[i].y);
}
}
sort(q+1 ,q+cnt+1 ,cmp);
for(int i=1;i<=cnt;i++)
if(q[i].opt==2)
cout << ans[i] << endl;
}
|
