题解：BISHI129 区间增量与区间小于计数
题目链接
题目描述
给定长度为 的数组
，支持两类操作：
- 区间增量：将
内每个元素加上
；
- 区间小于计数：统计
。
解题思路
使用分块（根号分解）+ 块内有序表 + 块懒标记：
- 将数组按块大小
划分为若干块，每块维护：
- 原始值数组片段
；
- 懒标记
（整块平移量）；
- 按当前“基值”排序的有序表，以支持整块二分计数。
- 原始值数组片段
- 区间加：
- 若跨多块，仅对两端零星块逐元素加并“重建”有序表；
- 对中间完整块，直接累加懒标记。
- 区间计数：
- 两端零星块逐元素判断
；
- 中间完整块用二分统计有序表中
的数量。
- 两端零星块逐元素判断
复杂度：每次操作 ，取
得均摊
，能通过本题。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; if(!(cin >> n >> q)) return 0;
vector<i64> a(n+1);
for(int i=1;i<=n;i++) cin >> a[i];
int B = max(1, (int)sqrt(n));
int num = (n + B - 1) / B;
vector<int> L(num+1), R(num+1), id(n+1);
for(int b=1;b<=num;b++){
L[b] = (b-1)*B + 1;
R[b] = min(n, b*B);
for(int i=L[b]; i<=R[b]; i++) id[i]=b;
}
vector<i64> tag(num+1, 0);
vector<vector<i64>> ord(num+1);
auto rebuild = [&](int b){
ord[b].clear(); ord[b].reserve(R[b]-L[b]+1);
for(int i=L[b]; i<=R[b]; i++) ord[b].push_back(a[i]);
sort(ord[b].begin(), ord[b].end());
};
for(int b=1;b<=num;b++) rebuild(b);
auto range_add = [&](int l, int r, i64 x){
int bl = id[l], br = id[r];
if(bl==br){
for(int i=l;i<=r;i++) a[i]+=x;
rebuild(bl);
return;
}
for(int i=l;i<=R[bl];i++) a[i]+=x; rebuild(bl);
for(int i=L[br];i<=r;i++) a[i]+=x; rebuild(br);
for(int b=bl+1;b<=br-1;b++) tag[b]+=x;
};
auto count_less = [&](int l, int r, i64 x){
long long ans = 0;
int bl = id[l], br = id[r];
if(bl==br){
for(int i=l;i<=r;i++) if(a[i]+tag[bl] < x) ans++;
return ans;
}
for(int i=l;i<=R[bl];i++) if(a[i]+tag[bl] < x) ans++;
for(int i=L[br];i<=r;i++) if(a[i]+tag[br] < x) ans++;
for(int b=bl+1;b<=br-1;b++){
i64 t = x - tag[b];
ans += lower_bound(ord[b].begin(), ord[b].end(), t) - ord[b].begin();
}
return ans;
};
while(q--){
int op; cin >> op;
if(op==1){ int l,r; i64 x; cin >> l >> r >> x; range_add(l,r,x); }
else { int l,r; i64 x; cin >> l >> r >> x; cout << count_less(l,r,x) << '\n'; }
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream in; private final byte[] buf = new byte[1<<16];
private int p=0,l=0; FastScanner(InputStream is){in=is;}
private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
long nextLong() throws IOException { int c; long s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int q = fs.nextInt();
long[] a = new long[n+1];
for(int i=1;i<=n;i++) a[i]=fs.nextLong();
int B = Math.max(1, (int)Math.sqrt(n));
int num = (n + B - 1) / B;
int[] L = new int[num+1], R = new int[num+1], id = new int[n+1];
for(int b=1;b<=num;b++){
L[b] = (b-1)*B + 1;
R[b] = Math.min(n, b*B);
for(int i=L[b]; i<=R[b]; i++) id[i]=b;
}
long[] tag = new long[num+1];
long[][] ord = new long[num+1][];
for(int b=1;b<=num;b++){
int len = R[b]-L[b]+1;
long[] v = new long[len];
for(int i=0;i<len;i++) v[i] = a[L[b]+i];
Arrays.sort(v); ord[b]=v;
}
Runnable rebuild = new Runnable(){ public void run(){} };
final class Helper{
void rebuild(int b){
int len = R[b]-L[b]+1; long[] v = new long[len];
for(int i=0;i<len;i++) v[i] = a[L[b]+i];
Arrays.sort(v); ord[b]=v;
}
int lowerBound(long[] v, long val){
int l=0, r=v.length;
while(l<r){ int m=(l+r)>>>1; if(v[m]<val) l=m+1; else r=m; }
return l;
}
}
Helper hp = new Helper();
while(q-- > 0){
int op = fs.nextInt();
if(op==1){
int l = fs.nextInt(), r = fs.nextInt(); long x = fs.nextLong();
int bl = id[l], br = id[r];
if(bl==br){ for(int i=l;i<=r;i++) a[i]+=x; hp.rebuild(bl); }
else{
for(int i=l;i<=R[bl];i++) a[i]+=x; hp.rebuild(bl);
for(int i=L[br];i<=r;i++) a[i]+=x; hp.rebuild(br);
for(int b=bl+1;b<=br-1;b++) tag[b]+=x;
}
}else{
int l = fs.nextInt(), r = fs.nextInt(); long x = fs.nextLong();
int bl = id[l], br = id[r]; long ans=0;
if(bl==br){ for(int i=l;i<=r;i++) if(a[i]+tag[bl] < x) ans++; }
else{
for(int i=l;i<=R[bl];i++) if(a[i]+tag[bl] < x) ans++;
for(int i=L[br];i<=r;i++) if(a[i]+tag[br] < x) ans++;
for(int b=bl+1;b<=br-1;b++){
long t = x - tag[b];
ans += hp.lowerBound(ord[b], t);
}
}
System.out.println(ans);
}
}
}
}
import sys, math, bisect
data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); q = int(next(it))
a = [0]*(n+1)
for i in range(1, n+1):
a[i] = int(next(it))
B = max(1, int(math.isqrt(n)))
num = (n + B - 1) // B
L = [0]*(num+1)
R = [0]*(num+1)
bid = [0]*(n+1)
for b in range(1, num+1):
L[b] = (b-1)*B + 1
R[b] = min(n, b*B)
for i in range(L[b], R[b]+1):
bid[i] = b
tag = [0]*(num+1)
ordv = [[] for _ in range(num+1)]
def rebuild(b: int):
v = [a[i] for i in range(L[b], R[b]+1)]
v.sort()
ordv[b] = v
for b in range(1, num+1):
rebuild(b)
def range_add(l: int, r: int, x: int):
bl, br = bid[l], bid[r]
if bl == br:
for i in range(l, r+1):
a[i] += x
rebuild(bl)
return
for i in range(l, R[bl]+1):
a[i] += x
rebuild(bl)
for i in range(L[br], r+1):
a[i] += x
rebuild(br)
for b in range(bl+1, br):
tag[b] += x
def count_less(l: int, r: int, x: int) -> int:
bl, br = bid[l], bid[r]
ans = 0
if bl == br:
for i in range(l, r+1):
if a[i] + tag[bl] < x:
ans += 1
return ans
for i in range(l, R[bl]+1):
if a[i] + tag[bl] < x:
ans += 1
for i in range(L[br], r+1):
if a[i] + tag[br] < x:
ans += 1
for b in range(bl+1, br):
t = x - tag[b]
ans += bisect.bisect_left(ordv[b], t)
return ans
out = []
for _ in range(q):
op = int(next(it))
if op == 1:
l = int(next(it)); r = int(next(it)); x = int(next(it))
range_add(l, r, x)
else:
l = int(next(it)); r = int(next(it)); x = int(next(it))
out.append(str(count_less(l, r, x)))
sys.stdout.write("\n".join(out))
算法及复杂度
- 算法：根号分解 + 懒标记 + 块内有序表二分
- 时间复杂度：
均摊
- 空间复杂度：
京公网安备 11010502036488号