直接暴力分块
完整块 修改永久懒标记
两端不完整块暴力修改元素值
单点查询值 = 元素值 + 懒标记
完整块数量不超过 \(\sqrt n\), 两不完整块总长度不超过 \(2 \sqrt n\)
总复杂度\(O(n \sqrt{n})\)
//知识点:分块
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <cmath>
#define ll long long
const int MARX = 5e4 + 10;
//===========================================================
//Belong:元素所在块的编号; Fir, Las:第i个块的左右边界
int N, lazyNum, Belong[MARX], Fir[MARX], Las[MARX];
ll Number[MARX], lazy[MARX]; //Number:元素值; lazy:第i个块的永久懒标记
//===========================================================
inline int read()
{
int w = 0, f = 1; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Prepare() //预处理
{
N = read();
for(int i = 1; i <= N; i ++) Number[i] = (ll) read();
lazyNum = sqrt(N);
for(int i = 1; i <= lazyNum; i ++) //进行分块
Fir[i] = (i - 1) * lazyNum + 1,
Las[i] = i * lazyNum;
//处理数列尾的 不完整块
if(Las[lazyNum] < N) lazyNum ++, Fir[lazyNum] = Las[lazyNum - 1] + 1, Las[lazyNum] = N;
for(int i = 1; i <= lazyNum; i ++) //处理每个元素 所在块的编号
for(int j = Fir[i]; j <= Las[i]; j ++)
Belong[j] = i;
}
void Change(int L, int R, ll Val) //区间加
{
if(Belong[L] == Belong[R]) //当修改区间 被一个块包含 (不完整块
{
for(int i = L; i <= R; i ++) Number[i] += Val; //直接暴力修改
return ;
}
for(int i = Belong[L] + 1; i <= Belong[R] - 1; i ++) lazy[i] += Val; //修改完整块
for(int i = L; i <= Las[Belong[L]]; i ++) Number[i] += Val; //修改左端不完整块
for(int i = Fir[Belong[R]]; i <= R; i ++) Number[i] += Val; //修改右端不完整块
}
//===========================================================
int main()
{
Prepare();
for(int i = 1; i <= N; i ++)
{
int opt = read(), L = read(), R = read(), Val = read();
if(! opt) Change(L, R, (ll) Val);
else printf("%lld\n", Number[R] + lazy[Belong[R]]); //单点查询
}
return 0;
}同 1, 先进行分块, 再分别考虑完整块与不完整块 :
先不考虑 修改操作 :
不完整块 可直接暴力查询
对于完整块, 查询小于给定值元素数, 易联想到 lower_bound 操作
由于分块后单个块较小, 则可直接暴力排序, 再通过 lower_bound 求得元素数
再考虑 修改操作
同样, 不完整块 可直接进行暴力修改
对于完整块, 区间加后, 不影响它们之间的排名, 排序后 顺序不变
进行区间加 x 后 再进行区间查询 y , 与 在区间加 x 之前, 区间查询 y - x , 得到的结果相同
则可使用类似 1 的懒惰标记法 进行区间修改, 并根据懒标记调整查询的值
由上, 则需记录 未排序的数列 与 排序后的数列(需要进行 lower_bound)
可使用 vector 类, 来储存每一排序后的完整块
修改时 :
不完整块 暴力修改未排序数列, 将 原排序后的数列 重新赋值并排序 (为了便于 查询)
其总长度不超过 \(2\sqrt n\) , 单次排序复杂度 \(O(\sqrt n\log \sqrt n)\)
完整块直接更新 懒标记即可, 其个数 不超过 \(\sqrt n\)
则单次修改总复杂度为 \(O(\sqrt n + \sqrt n\log \sqrt n)\)
查询时 :
不完整块 暴力查询未排序数列, 其总长度不超过 \(2\sqrt n\)
完整块 对排序后数列进行 lower_bound,
其个数 不超过 \(\sqrt n\), 单次 lower_bound 复杂度为 \(O(\sqrt n\log \sqrt n)\)
则单次修改总复杂度也为 \(O(\sqrt n + \sqrt n\log \sqrt n)\)
在预处理分块时 需要对整个数列进行排序预处理, 复杂度 \(O(n \log n)\)
则上述算法 总复杂度为 \(O(n\log n + n\sqrt n\log\sqrt n)\)
//知识点:分块
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
const int MARX = 5e4 + 10;
//===========================================================
int N, original[MARX];
int BlockNum, Belong[MARX], Fir[MARX], Las[MARX], lazy[MARX];
std :: vector <int> block[510]; //存 排序之后的每个块
//===========================================================
inline int read()
{
int w = 0, f = 1; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Reset(int pos) //为第pos个块 重新赋值并排序
{
block[pos].clear(); //清空
for(int i = Fir[pos]; i <= Las[pos]; i ++) block[pos].push_back(original[i]); //
std :: sort(block[pos].begin(), block[pos].end()); //重排序
}
void Prepare() //预处理分块
{
N = read();
for(int i = 1; i <= N; i ++) original[i] = read();
BlockNum = sqrt(N);
for(int i = 1; i <= BlockNum; i ++)
Fir[i] = (i - 1) * BlockNum + 1, //
Las[i] = i * BlockNum;
if(Las[BlockNum] < N) BlockNum ++, Fir[BlockNum] = Las[BlockNum - 1] + 1, Las[BlockNum] = N;
for(int i = 1; i <= BlockNum; i ++)
for(int j = Fir[i]; j <= Las[i]; j ++)
Belong[j] = i;
for(int i = 1; i <= BlockNum; i ++) Reset(i); //数列排序 初始化
}
void Change(int L, int R, int Val) //区间加操作
{
int Bell = Belong[L], Belr = Belong[R];
if(Bell == Belr) //修改不完整块
{
for(int i = L; i <= R; i ++) original[i] += Val;
Reset(Bell); //更新排序后数列
return ;
}
for(int i = Bell + 1; i <= Belr - 1; i ++) lazy[i] += Val; //修改完整块
for(int i = L; i <= Las[Bell]; i ++) original[i] += Val; //修改不完整块
Reset(Bell);
for(int i = Fir[Belr]; i <= R; i ++) original[i] += Val; //修改不完整块
Reset(Belr);
}
int Query(int L, int R, int Val) //区间查询小于给定值 元素数
{
int Bell = Belong[L], Belr = Belong[R], ret = 0;
if(Bell == Belr) //不完整块
{
for(int i = L; i <= R; i ++) ret += (original[i] + lazy[Bell] < Val); ///暴力查询
return ret;
}
for(int i = L; i <= Las[Bell]; i ++) ret += (original[i] + lazy[Bell] < Val); //不完整块
for(int i = Fir[Belr]; i <= R; i ++) ret += (original[i] + lazy[Belr] < Val); //不完整块
for(int i = Bell + 1; i <= Belr - 1; i ++) ret += lower_bound(block[i].begin(), block[i].end(), Val - lazy[i]) - block[i].begin(); ///完整块 二分
return ret;
}
//===========================================================
int main()
{
Prepare();
for(int i = 1; i <= N; i ++)
{
int opt = read(), L = read(), R = read(), Val = read();
if(! opt) Change(L, R, Val);
else printf("%d\n", Query(L, R, Val * Val));
}
return 0;
}算法1 :
套用 数列分块2 的做法, 在进行lower_bound时 求得每个块中 小于给定值 最大元素,
再将多个块的答案合并 取最大值.
总复杂度 \(O(n\log n + n\sqrt n\log\sqrt n)\).
算法2 :
查询前驱 ? 来发Splay
可以对每个块 都维护一个set, 来代替算法 1 中的排序数组.
重赋值和插入操作 都会变得更方便
但出题人的写法有些问题
重赋值时 擦除操作 会擦除 插入的新元素
将 std 中的 set 改为 multiset即可
//知识点:分块
/*
By:Luckyblock
*/
#include <cstdio>
#include <cctype>
#include <cmath>
#include <set>
#include <algorithm>
#define ll long long
const int MARX = 1e5 + 10;
//===========================================================
int N, original[MARX];
int BlockNum, Belong[MARX], Fir[MARX], Las[MARX], lazy[MARX];
std :: multiset <int> block[1010];
//===========================================================
inline int read()
{
int w = 0, f = 1; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Prepare() //预处理
{
N = read();
for(int i = 1; i <= N; i ++) original[i] = read();
BlockNum = sqrt(N);
for(int i = 1; i <= BlockNum; i ++)
Fir[i] = (i - 1) * BlockNum + 1, //
Las[i] = i * BlockNum;
if(Las[BlockNum] < N) BlockNum ++, Fir[BlockNum] = Las[BlockNum - 1] + 1, Las[BlockNum] = N;
for(int i = 1; i <= BlockNum; i ++)
for(int j = Fir[i]; j <= Las[i]; j ++)
Belong[j] = i, block[i].insert(original[j]); //插入set
}
void Change(int L, int R, int Val) //修改
{
int Bell = Belong[L], Belr = Belong[R];
if(Bell == Belr) //不完整块
{
for(int i = L; i <= R; i ++) //将l ~ r全部加入set
{
block[Bell].erase(original[i]); //擦除原有元素
original[i] += Val;
block[Bell].insert(original[i]); //插入新元素
}
return ;
}
for(int i = Bell + 1; i <= Belr - 1; i ++) lazy[i] += Val;
for(int i = L; i <= Las[Bell]; i ++) //不完整块
{
block[Bell].erase(original[i]); //擦除原有元素
original[i] += Val;
block[Bell].insert(original[i]); //插入新元素
}
for(int i = Fir[Belr]; i <= R; i ++)
{
block[Belr].erase(original[i]);
original[i] += Val;
block[Belr].insert(original[i]);
}
}
int Query(int L, int R, int Val) //查询
{
int Bell = Belong[L], Belr = Belong[R], ret = - 1;
if(Bell == Belr) //不完整块
{
for(int i = L; i <= R; i ++) //暴力查询
if(original[i] + lazy[Bell] < Val)
ret = std :: max(ret, original[i] + lazy[Bell]);
return ret;
}
for(int i = L; i <= Las[Bell]; i ++) //不完整块
if(original[i] + lazy[Bell] < Val) //暴力查询
ret = std :: max(ret, original[i] + lazy[Bell]);
for(int i = Fir[Belr]; i <= R; i ++) //不完整块
if(original[i] + lazy[Belr] < Val) //暴力查询
ret = std :: max(ret, original[i] + lazy[Belr]);
for(int i = Bell + 1; i <= Belr - 1; i ++) //完整块
{
int value = Val - lazy[i];
std :: set <int> :: iterator it = block[i].lower_bound(value); //查询前驱
if(it == block[i].begin()) continue; //无前驱
ret = std :: max(ret, *(-- it) + lazy[i]);
}
return ret;
}
//===========================================================
int main()
{
Prepare();
for(int i = 1; i <= N; i ++)
{
int opt = read(), L = read(), R = read(), Val = read();
if(! opt) Change(L, R, Val);
else printf("%d\n", Query(L, R, Val));
}
return 0;
}gugunbguguwansui原文：https://www.cnblogs.com/luckyblock/p/12112955.html