参考：「分块」数列分块入门1 – 9 by hzwer
2
Description
给出一个长为(n)的数列，以及(n)个操作，操作涉及区间加法，询问区间内小于某个值(x)的元素个数。
思路
每个块内保持升序排列。
则块外暴力统计，块内二分查找分界点。
一些注意点，如：
- 要记录下标；
- 块外暴力修改完之后需要再排序；
- 在块内二分查找的值是(c-tag[i])而非(c).
Code
#include <bits/stdc++.h>
#define maxn 50010
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int tag[maxn], bl[maxn], n, blo;
struct node {
int x, p;
bool operator < (const node& nd) const { return x < nd.x; }
}a[maxn];
inline int val(int x) { return a[x].x + tag[bl[x]]; }
int query(int l, int r, int c) {
int ret=0;
F(i, bl[l]*blo, min((bl[l]+1)*blo, n)) if (a[i].p>=l&&a[i].p<=r && val(i)<c) ++ret;
if (bl[l]!=bl[r]) F(i, bl[r]*blo, min((bl[r]+1)*blo, n)) if (a[i].p>=l&&a[i].p<=r && val(i)<c) ++ret;
F(i, bl[l]+1, bl[r]) ret += lower_bound(a+i*blo, a+(i+1)*blo, (node){c-tag[i], 0}) - (a+i*blo);
return ret;
}
void add(int l, int r, int c) {
F(i, bl[l]*blo, min((bl[l]+1)*blo,n)) if (a[i].p>=l&&a[i].p<=r) a[i].x+=c;
sort(a+bl[l]*blo, a+min((bl[l]+1)*blo, n));
if (bl[l]!=bl[r]) {
F(i, bl[r]*blo, min((bl[r]+1)*blo, n)) if (a[i].p>=l&&a[i].p<=r) a[i].x+=c;
sort(a+bl[r]*blo, a+min((bl[r]+1)*blo, n));
}
F(i, bl[l]+1, bl[r]) tag[i] += c;
}
int main() {
scanf("%d", &n); blo = sqrt(n);
F(i, 0, n) scanf("%d", &a[i].x), a[i].p = i, bl[i] = i/blo;
int num = (n+blo-1)/blo;
F(i, 0, num-1) sort(a+i*blo, a+(i+1)*blo);
sort(a+(num-1)*blo, a+n);
F(i, 0, n) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c); --l, --r;
if (op) printf("%d
", query(l, r, c*c));
else add(l, r, c);
}
return 0;
}
3
Description
给出一个长为(n)的数列，以及(n)个操作，操作涉及区间加法，询问区间内小于某个值(x)的最大值。
思路
法一
做法基本同上。
法二
在每个块内用其他数据结构维护，如set，每次修改时，结合原序数组进行修改。
Code
Ver. 1
#include <bits/stdc++.h>
#define maxn 100010
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int tag[maxn], bl[maxn], n, blo;
struct node {
int x, p;
bool operator < (const node& nd) const { return x < nd.x; }
}a[maxn];
inline int val(int x) { return a[x].x + tag[bl[x]]; }
int query(int l, int r, int c) {
int ans=-1, diff=INT_MAX, temp;
F(i, bl[l]*blo, min((bl[l]+1)*blo, n)) {
if (a[i].p>=l&&a[i].p<=r && (temp=c-val(i))>0 && temp<diff) ans = val(i), diff = temp;
}
if (bl[l]!=bl[r]) F(i, bl[r]*blo, min((bl[r]+1)*blo, n)) {
if (a[i].p>=l&&a[i].p<=r && (temp=c-val(i))>0 && temp<diff) ans = val(i), diff = temp;
}
F(i, bl[l]+1, bl[r]) {
int p = lower_bound(a+i*blo, a+(i+1)*blo, (node){c-tag[i], 0}) - (a+i*blo);
if (p==0) continue;
temp = val(i*blo+p-1);
if (c-temp>0 && c-temp<diff) diff = c-temp, ans = temp;
}
return ans;
}
void add(int l, int r, int c) {
F(i, bl[l]*blo, min((bl[l]+1)*blo,n)) if (a[i].p>=l&&a[i].p<=r) a[i].x+=c;
sort(a+bl[l]*blo, a+min((bl[l]+1)*blo, n));
if (bl[l]!=bl[r]) {
F(i, bl[r]*blo, min((bl[r]+1)*blo, n)) if (a[i].p>=l&&a[i].p<=r) a[i].x+=c;
sort(a+bl[r]*blo, a+min((bl[r]+1)*blo, n));
}
F(i, bl[l]+1, bl[r]) tag[i] += c;
}
int main() {
scanf("%d", &n); blo = sqrt(n);
F(i, 0, n) scanf("%d", &a[i].x), a[i].p = i, bl[i] = i/blo;
int num = (n+blo-1)/blo;
F(i, 0, num-1) sort(a+i*blo, a+(i+1)*blo);
sort(a+(num-1)*blo, a+n);
F(i, 0, n) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c); --l, --r;
if (op) printf("%d
", query(l, r, c));
else add(l, r, c);
}
return 0;
}
Ver. 2
然而我写(T)了
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
using namespace std;
typedef long long LL;
int n, blo, bl[maxn], a[maxn], tag[maxn];
multiset<int> st[1010];
void modify(int l, int r, int c) {
F(i, l, min((bl[l]+1)*blo, r+1)) {
st[bl[l]].erase(st[bl[l]].find(a[i]));
st[bl[l]].insert(a[i]+=c);
}
if (bl[l]!=bl[r]) F2(i, bl[r]*blo, r) {
st[bl[r]].erase(st[bl[r]].find(a[i]));
st[bl[r]].insert(a[i]+=c);
}
F(i, bl[l]+1, bl[r]) tag[i] += c;
}
inline int val(int x) { return a[x] + tag[bl[x]]; }
int query(int l, int r, int c) {
int ans=-1;
F(i, l, min((bl[l]+1)*blo, r+1)) {
if (val(i)<c) ans = max(ans, val(i));
}
if (bl[l]!=bl[r]) F2(i, bl[r]*blo, r) {
if (val(i)<c) ans = max(ans, val(i));
}
F(i, bl[l]+1, bl[r]) {
auto it = st[i].lower_bound(c-tag[i]);
if (it==st[i].begin()) continue;
int x;
ans = max(ans, x=*(--it)+tag[i]);
}
return ans;
}
LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main() {
scanf("%d", &n); blo = 1000;
F(i, 0, n) {
a[i] = read();
st[bl[i]=i/blo].insert(a[i]);
}
F(i, 0, n) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c); --l, --r;
if (op) printf("%d
", query(l, r, c));
else modify(l, r, c);
}
return 0;
}