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

Luogu P11660 我终将成为你的倒影 题解 [ 紫 ] [ 分块 ] [ 分类讨论 }

我终将成为你的倒影:考察分块基本功的一道题。

注意到本题强制在线,且这种信息用线段树不是很好维护,所以可以很自然地想到分块

又注意到 \(b \le 500\),所以考虑暴力枚举 \(b\)。发现当 \(b\) 固定的时候,\(a\)\(a, a+b, a+2b\) 等数字答案是一样的,因为可以把分子中的 \(b\) 提出来,不会影响前后两个是否相等。于是可以\(\bm a\) 转化为 $ \bm{a\bmod b}$ 考虑

因为将 \(a\)\(b\) 取模了,所以此时 \(a< b \le 500\),容易想到一个暴力做法:将序列分块,每块维护 \(a, b\) 各自取值时的答案,查询的时候暴力查散块,整块直接加,两个块之间暴力计算,即可做到查询 \(O(\frac{n}{B})\),预处理 \(O(nb^2)\)。显然暴力预处理的部分只要把块数调小一点就不会 MLE,所以只需要优化预处理部分的时间复杂度即可。

继续观察这个函数的性质,因为所有数的 \(b\) 都是相等的,所以当两个数的函数值相差大于等于 \(\bm{2}\) 的时候,这两个数的函数值在任何时候都无法相等。因此枚举 \(b\) 之后,只需要考虑函数值相差 \(\bm1\) 的位置,根据 \(a\bmod b\) 的值分讨即可。具体而言,令 \(x = A_{i - 1} \bmod b, y = A_i \bmod b\)

  • \(A_{i - 1} = A_i\) 时,\(a\in[0, b)\)
  • \(f(A_{i - 1}) = f(A_i)\) 时,\(a\in[0, b - \max\{x, y\})\cup[b - \min\{x, y\}, b)\)
  • \(f(A_{i - 1}) = f(A_i) + 1, x < y\) 时,\(a\in[b - y, b - x)\)
  • \(f(A_{i - 1})+1 = f(A_i) , x > y\) 时,\(a\in[b - x, b - y)\)
  • 其余情况 \(a\in \varnothing\)

这样就可以 \(O(1)\) 计算 \(a\) 的区间了,做一个差分计算贡献即可。

总体时间复杂度 \(O(B+\frac{n}{B}+nb+\frac{n}{B}b^2)\)。当 \(\frac{n}{B} = B\) 时最优,因此 \(B = \sqrt n\)。但是因为此题卡空间,所以块长可能要调大一些。

#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, MV = 105, V = 505;
int n, m, a[N];
struct Decompose{int B, Btot, L[M], R[M], bl[N];int val[MV][V][V];void build(){B = sqrt(n);Btot = (n + B - 1) / B;for(int i = 1; i <= Btot; i++){L[i] = (i - 1) * B + 1;R[i] = min(n, i * B);for(int j = L[i]; j <= R[i]; j++) bl[j] = i;}}void init(){for(int b = 1; b <= 500; b++){for(int i = 1; i <= Btot; i++){for(int j = L[i] + 1; j <= R[i]; j++){if(a[j] == a[j - 1]){val[i][b][0]++;continue;}if(abs(a[j] / b - a[j - 1] / b) >= 2) continue;int x = a[j - 1] % b, y = a[j] % b;if(a[j - 1] / b > a[j] / b){if(y > x){val[i][b][b - y]++;val[i][b][b - x]--;}}else if(a[j - 1] / b < a[j] / b){if(x > y){val[i][b][b - x]++;val[i][b][b - y]--;}}else{val[i][b][0]++;val[i][b][b - max(x, y)]--;val[i][b][b - min(x, y)]++;}}for(int j = 1; j < b; j++) val[i][b][j] += val[i][b][j - 1];}}}int query(int l, int r, int x, int y){int res = 0;if(bl[l] == bl[r]){for(int i = l + 1; i <= r; i++)res += ((a[i - 1] + x) / y == (a[i] + x) / y);return res;}for(int i = l + 1; i <= R[bl[l]]; i++)res += ((a[i - 1] + x) / y == (a[i] + x) / y);for(int i = L[bl[r]]; i <= r; i++)res += ((a[i - 1] + x) / y == (a[i] + x) / y);for(int i = bl[l] + 1; i < bl[r]; i++){res += val[i][y][x % y];res += ((a[L[i] - 1] + x) / y == (a[L[i]] + x) / y);}return res;}
}dc;
int main()
{//freopen("sample.in", "r", stdin);//freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];dc.build();dc.init();int lastans = 0;for(int i = 1; i <= m; i++){int l, r, x, y;cin >> l >> r >> x >> y;l ^= lastans;r ^= lastans;x ^= lastans;y ^= lastans;lastans = dc.query(l, r, x, y);cout << lastans << "\n";}return 0;
}
http://www.hskmm.com/?act=detail&tid=26761

相关文章:

  • 2025 年最新推荐!小程序开发机构排行榜:覆盖定制开发 / 电商 / 预订 / 配送多场景优质服务商成都小程序开发/小程序定制开发/电商小程序开发/预订服务小程序开发公司推荐
  • CF280D k-Maximum Subsequence Sum 题解(线段树+反悔贪心维护k段最大子段和)
  • 2025 西安新房住宅最新推荐榜权威发布:多维度测评 + 选房指南,助你精准置业品质/高端/优质/品牌/刚需新房推荐
  • C# async await 测试一
  • 2025 年快速卷帘门厂家最新推荐排行榜:聚焦智能定制与高效供货,精选实力厂家助您精准选购
  • 实验课1
  • 课后作业1
  • 详细介绍:Windows如何定制键盘按键
  • 深入解析:Oracle、PostgreSQL 与 MySQL 数据库对比分析与实践指南
  • TheHackersLabs Templo writeup
  • PCIe扫盲——链路初始化与训练基础(三)之LTSSM
  • #attrs
  • 国庆比赛总结
  • 记录第一个博客
  • PCIe扫盲——链路初始化与训练基础(二)
  • 2025 年 ppt 素材模板 /ppt 模板 ai 生成 /ppt 模板制作 /ppt 模版 / 课件 PPT 模板工具推荐:iSlide 技术优势与全场景服务能力解析
  • 10.8
  • 课后作业1(01-方法)
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 NVMe 驱动特殊定制版
  • 项目案例作业2
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 H3C 新华三 定制版
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 Inspur 浪潮 定制版
  • 上手 Rokid JSAR:新手也能快速入门的 AR 开发之旅
  • 2025 年氨基酸水溶肥厂家最新推荐榜单:聚焦花芽分化膨果上色需求,精选优质企业助农户科学选购花芽分化/膨果上色/促花稳果/低温酶解氨基酸水溶肥厂家推荐
  • VMware ESXi 8.0U3g macOS Unlocker OEM BIOS 2.7 H3C 新华三 定制版
  • 2025 年最新防火涂料厂家排行榜:钢结构各类防火涂料优质厂家最新推荐,助力建筑安全选型 钢结构/水性/隧道/环保/饰面型防火涂料厂家推荐
  • 嵌入式固件升级框架详解与实战经验
  • 2025 年家用电梯最新推荐排行榜:精选技术领先、服务优质的实力品牌,助您精准选购
  • helm 模板的基础使用
  • 20251008J赛合订本