分块板子题

区间加法，区间求和

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
#define int long long
ll s[N], b[N], w[N], add[N];
ll l[N], r[N], belong[N];
ll len, tot, n, q;inline void init() {len = sqrt(n), tot = (n + len - 1) / len;for (int i = 1; i <= tot; ++i)l[i] = r[i - 1] + 1, r[i] = i * len;r[tot] = n;for (int i = 1; i <= tot; ++i) {for (int j = l[i]; j <= r[i]; ++j)b[i] += w[j], belong[j] = i;s[i] = s[i - 1] + b[i];}
}inline void modify(int ql, int qr, int c) {int p = belong[ql], q = belong[qr];if (p == q) {for (int i = ql; i <= qr; ++i)w[i] += c, b[p] += c;for (int i = p; i <= tot; ++i)s[i] = s[i - 1] + b[i];return;}for (int i = ql; i <= r[p]; ++i)w[i] += c, b[p] += c;for (int i = qr; i >= l[q]; --i)w[i] += c, b[q] += c;for (int i = p + 1; i <= q - 1; ++i)add[i] += c, b[i] += (r[i] - l[i] + 1) * c;for (int i = p; i <= tot; ++i)s[i] = s[i - 1] + b[i];
}inline ll query(int ql, int qr,ll c) {int p = belong[ql], q = belong[qr];ll res = 0;if (p == q) {for (int i = ql; i <= qr; ++i)res = (res+ w[i] + add[p])%c;return res;}res = s[q - 1] - s[p];for (int i = ql; i <= r[p]; ++i)res = (res+ w[i] + add[p])%c;for (int i = qr; i >= l[q]; --i)res = (res+ w[i] + add[q])%c;return res;}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >>n;q = n;for (int i = 1; i <= n; i++)cin >> w[i];init();while (q--) {int op, ql, qr, c;cin >> op >> ql >> qr>>c;if (!op){modify(ql, qr, c);}elsecout << query(ql,qr,c+1) << "\n";}return 0;}

分块 + 二分查询查询区间小于或者大于某个数的个数

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;
ll b[N],lz[N],w[N];
int l[N],r[N],belong[N];
int len,tot,ql,qr,n,q;inline void Sort(int k){for(int i=l[k];i<=r[k];++i)b[i] = w[i];sort(b+l[k],b+r[k]+1);
}inline void init()
{len = sqrt(n),tot = (n+len-1)/len;r[tot] = n;for(int i=1;i<=tot;i++)l[i] = r[i-1]+1,r[i] =i*len;for(int i=1;i<=tot;++i){for(int j=l[i];j<=r[i];++j)belong[j] = i;Sort(i);}
}inline void modify(int ql,int qr,int c){int p = belong[ql],q=belong[qr];if(p==q){for(int i=ql;i<=qr;++i)w[i]+=c;Sort(p);return;}for(int i=ql;i<=r[p];++i)w[i]+=c;for(int i=qr;i>=l[q];--i)w[i]+=c;Sort(p),Sort(q);for(int i=p+1;i<=q-1;++i)lz[i]+=c;// for(int i=p+1;i<=q-1;++i)Sort(i);}inline int query(int ql,int qr,ll c){int p =belong[ql],q = belong[qr];int res = 0;if(p==q){for(int i=ql;i<=qr;++i)if(w[i]+lz[p]<c)res++;return res;}for(int i=ql;i<=r[p];++i)if(w[i]+lz[p]<c)res++;for(int i=qr;i>=l[q];--i)if(w[i]+lz[q]<c)res++;for(int i=p+1;i<=q-1;++i)res+=lower_bound(b+l[i],b+r[i]+1,c-lz[i])-b-l[i];return res;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;q=n;for(int i=1;i<=n;++i)cin>>w[i];init();while(q--){int op,c;cin>>op>>ql>>qr>>c;if(!op)modify(ql,qr,c);else cout<<query(ql,qr,c*c)<<"\n";}}

分块 + 二分查询区间内某个数的前驱或者后驱

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;
ll w[N],b[N],lz[N];
int l[N],r[N],belong[N];
int n,q,len,tot,ql,qr,op,c;inline void Sort(int k){for(int i=l[k];i<=r[k];++i)b[i] = w[i];sort(b+l[k],b+r[k]+1);
}inline void init()
{len = sqrt(n),tot = (n+len-1)/len;r[tot] = n;for(int i=1;i<=tot;i++)l[i] = r[i-1]+1,r[i] =i*len;for(int i=1;i<=tot;++i){for(int j=l[i];j<=r[i];++j)belong[j] = i;Sort(i);}
}inline void modify(int ql,int qr,int c){int p = belong[ql],q = belong[qr];if(p==q){for(int i=ql;i<=qr;++i)w[i]+=c;Sort(p);return;}for(int i=ql;i<=r[p];++i)w[i]+=c;for(int i=qr;i>=l[q];--i)w[i]+=c;for(int i=p+1;i<=q-1;i++)lz[i]+=c;Sort(p),Sort(q);}inline int query(int ql,int qr,int c){int p = belong[ql],q = belong[qr];ll res = -1e12;if(p==q){for(int i=ql;i<=qr;++i)if(w[i]+lz[p]<c)res = max(res,w[i]+lz[p]);if(res!=-1e12)return res;return -1;}for(int i=ql;i<=r[p];++i)if(w[i]+lz[p]<c)res = max(res,w[i]+lz[p]);for(int i=qr;i>=l[q];--i)if(w[i]+lz[q]<c)res = max(res,w[i]+lz[q]);for(int i=p+1;i<=q-1;++i){int  t = lower_bound(b+l[i],b+r[i]+1,c-lz[i])-b-l[i];if(t>=1)res = max(res,b[l[i]+t-1]+lz[i]);}if(res!=-1e12)return res;return -1;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;q = n;for(int i=1;i<=n;i++)cin>>w[i];init();while(q--){cin>>op>>ql>>qr>>c;if(!op)modify(ql,qr,c);else cout<<query(ql,qr,c)<<"\n";}
}