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