当前位置: 首页 > news >正文

Luogu P3863 序列 题解 [ 紫 ] [ 分块 ] [ 扫描线 ]

序列:思路比较典的扫描线题。

一个经典 trick:对于涉及历史版本操作的题,新增代表“时间”的一个维度,刻画在 \(\bm{k + 1}\) 维空间上考虑。

对于此题,发现是查询序列历史版本大于等于 \(v\) 的值的个数,于是可以把它刻画在一个二维平面上,\(x\) 轴代表序列的维度,\(y\) 轴代表时间轴。操作可以转化为:

  • 修改操作:将 \(x\in[l, r], y \in [t, q]\) 的矩形加上 \(x\)
  • 查询操作:查询 \(x = p, y\in[0, t]\)单列矩形中大于等于 \(v\) 的数的个数。

注意到查询单列矩形的条件很特殊,于是我们可以用一个数据结构维护 \(y\) 轴,然后顺过去扫 \(x\) 轴。

发现即使是一维平面上,带修且查询单个区间中 \(\ge v\) 的个数就只能用分块做了,于是分块维护即可。时间复杂度 \(O(q\sqrt q)\)

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 100005, M = 1005;
int n, q;
ll a[N], oria[N], ans[N];
struct Operation{ll x, y;
};
vector<Operation> Lines[N], Queries[N];
struct Decompose{int B, Btot, L[M], R[M], bl[N];ll val[N], Tag[M];void rebuild(int p){for(int i = L[p]; i <= R[p]; i++){a[i] = a[i] + Tag[p];val[i] = a[i];}Tag[p] = 0;sort(val + L[p], val + R[p] + 1);}void build(){B = sqrt(q + 1);Btot = (q + 1 + B - 1) / B;for(int i = 1; i <= Btot; i++){L[i] = (i - 1) * B + 1;R[i] = min(q + 1, i * B);for(int j = L[i]; j <= R[i]; j++)bl[j] = i;rebuild(i);}}void update(int l, int r, ll v){if(bl[l] == bl[r]){for(int i = l; i <= r; i++) a[i] += v;rebuild(bl[l]);return;}for(int i = l; i <= R[bl[l]]; i++) a[i] += v;rebuild(bl[l]);for(int i = L[bl[r]]; i <= r; i++) a[i] += v;rebuild(bl[r]);for(int i = bl[l] + 1; i < bl[r]; i++) Tag[i] += v;}int query(int l, int r, ll v){int res = 0;if(bl[l] == bl[r]){for(int i = l; i <= r; i++)res += (a[i] + Tag[bl[l]] >= v);return res;}for(int i = l; i <= R[bl[l]]; i++)res += (a[i] + Tag[bl[l]] >= v);for(int i = L[bl[r]]; i <= r; i++)res += (a[i] + Tag[bl[r]] >= v);for(int i = bl[l] + 1; i < bl[r]; i++){if(val[R[i]] + Tag[i] < v) continue;res += R[i] - (lower_bound(val + L[i], val + R[i] + 1, v - Tag[i]) - val) + 1;}return res;}
}dc;
int main()
{// freopen("P3863.in", "r", stdin);// freopen("P3863.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> q;for(int i = 1; i <= n; i++)cin >> oria[i];dc.build();memset(ans, -1, sizeof(ans));for(int i = 1; i <= q; i++){ll op, x, y, z;cin >> op;if(op == 1){cin >> x >> y >> z;Lines[x].push_back({z, i + 1});Lines[y + 1].push_back({-z, i + 1});}else{cin >> x >> y;Queries[x].push_back({y, i + 1});}}for(int i = 1; i <= n; i++){dc.update(1, q + 1, -oria[i - 1]);dc.update(1, q + 1, oria[i]);for(auto ln : Lines[i])dc.update(ln.y, q + 1, ln.x);for(auto qs : Queries[i])ans[qs.y] = dc.query(1, qs.y - 1, qs.x);}for(int i = 2; i <= q + 1; i++)if(ans[i] != -1)cout << ans[i] << "\n";return 0;
}
http://www.hskmm.com/?act=detail&tid=21774

相关文章:

  • [HCTF 2018]WarmUp
  • Day2:Linux文件目录移到拷贝与vim编辑器使用指南
  • 【半导体物理 | 笔记】第八章 半导体表面与MIS结构
  • 【半导体物理 | 笔记】第七章 金属和半导体的接触
  • 【半导体物理 | 笔记】第四章 半导体的导电性
  • 【半导体物理 | 笔记】第五章 非平衡载流子
  • 【AHK】暗黑3助手,加强版鼠标宏
  • 【当前赛季】第36赛季:地狱魔王9月12日开启
  • 第36赛季:地狱魔王9月12日开启
  • 2025年9月 增值税进项税额,不可抵扣VS可抵扣全解析
  • 【Rust GUI开发入门】编写一个本地音乐播放器(14. 应用打包-制作安装程序) - Jordan
  • 【黑马python】2.Python基础语法-注释 数据类型 运算符 字符串等
  • Visual Studio Code + Clangd 设置语法检查针对 C++的版本。
  • 示波器地、大地、电源地!地线着火?
  • 【黑马python】2.Python基础知识-注释 数据类型 运算符 字符串等
  • Educational Codeforces Round 135 (Rated for Div. 2)
  • 【Rust GUI开发入门】编写一个本地音乐播放器(13. 实现按键绑定) - Jordan
  • mem reduct 没有托盘图标
  • C++ GUI 选型记
  • TypeScript 泛型 T 详细解释
  • day007
  • 【Rust GUI开发入门】编写一个本地音乐播放器(12. 国际化应用-多语言支持) - Jordan
  • 2025秋_6
  • 程序语言杂谈:C/C++
  • 2025秋_7
  • PEP8 规范
  • print() 函数
  • 第九天
  • Pycharm 设置
  • [NOIP 2016 提高组] 组合数问题