例题2离散化，下标很大，值很小
我们看这组数据[1,10],[1,3],[6,10],很明显答案是3
但是离散化之后为[1,4],[1,2],[3,4],答案变成了2
为解决这种问题,我们可以在更新线段树的时候将区间从[l,r]变成[l,r-1],就将区间转化成了[1,3],[1,1],[3,3]这样的树
但是当我们遇到这样的数据[1,3],[1,1],[2,2],[3,3],就会导致区间更新时出错,我们可以将初始数据的r都加上1,就排除了li和ri相等的情况,如果没有这种情况,离散化后的区间也都是一样的
其实这道题数据很弱,不管这样的情况也能过(逃
正解https://www.luogu.com.cn/paste/vl2ora2z
卡壳点：
query return时，+号写成，
u<<1|1,写错成u<<1
modify部分
下标用错，用了1，n
modify的值写成了1，应该是有多个值，每张海报的值不一样。
build的时候由于v的下标0的值是无意义的边界，所以build的r要写成v.size()-1;
题解代码
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> #define rep(i, n) for (int i = 1; i <= (n); ++i) using namespace std; typedef long long ll; const int N = 1E5 + 10; bool vis[N]; //标记是否已经出现过第i张海报 struct node { int l, r; int id; //id表示lazy标签, 也表示当前节点值. }t[N << 2]; vector<int> v; vector<pair<int, int> > area; //v为离散化数组, area存放海报区间 int find(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); } 离散化用 void pushdown(node& op, int id) { op.id = id; } void pushdown(int x) { if (!t[x].id) return; pushdown(t[x << 1], t[x].id), pushdown(t[x << 1 | 1], t[x].id); t[x].id = 0; } //因为线段树内部不维护任何数值, 所以也可以省去pushup这一操作. void build(int l, int r, int x = 1) { t[x].l = l,t[x].r = r,t[x].id = 0 ;//id: 特别的, 如果0也是染色的点, 那么应初始化为-1 if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); } void modify(int l, int r, int c, int x = 1) { if (l <= t[x].l && r >= t[x].r) { pushdown(t[x], c); return; } pushdown(x); int mid = t[x].l + t[x].r >> 1; if (l <= mid) modify(l, r, c, x << 1); if (r > mid) modify(l, r, c, x << 1 | 1); } int ask(int x = 1) { if (t[x].id) { //当前子树均为同一值, 没必要再递归下去了 有标记，染过色 if (vis[t[x].id]) return 0; 如果出现过返回0 return vis[t[x].id] = 1; 没出现过直接返回st赋值语句。 } if (t[x].l == t[x].r) return 0; //到叶子结点一定要结束递归 叶子节点返回0. return ask(x << 1) + ask(x << 1 | 1); 返回两个节点相加的值。 } int main() { int T; cin >> T; while (T--) { v.clear(); v.push_back(-0x3f3f3f3f); //这里是为了离散化下标从1开始 area.clear(); int n; scanf("%d", &n); rep(i, n) { vis[i] = 0; //顺带初始化vis int l, r; scanf("%d %d", &l, &r); r++; v.push_back(l), v.push_back(r); area.push_back(make_pair(l,r)); } /* 离散化部分 */ sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); rep(i, n) if (v[i] - v[i - 1] != 1) v.push_back(v[i] - 1); //记为* sort(v.begin(), v.end()); build(1, v.size() - 1); //因为我的v数组有个-INF, 所以实际的建树大小应为v.size()-1 for (int i = 0; i < n; ++i) { int l = area[i].first, r = area[i].second; l = find(l), r = find(r); modify(l, r-1, i + 1); //个人习惯编号从1开始 } printf("%d\n", ask()); } return 0; }
经过模仿得到的acwing代码
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int>PII; const int N = 1e4 + 10; bool st[N<<1]; struct node{ int l,r; int lazy; }tr[N<<3]; vector<int> v; vector<PII > area; int find(int u) { return lower_bound(v.begin(),v.end(),u) - v.begin(); } void pushdown(node &tr,int lazy){ tr.lazy = lazy; } void pushdown(int u){ if(tr[u].lazy){ pushdown(tr[u<<1],tr[u].lazy),pushdown(tr[u<<1|1],tr[u].lazy); tr[u].lazy = 0; } } void build(int u,int l,int r){ tr[u].l = l,tr[u].r = r,tr[u].lazy = 0; if(l == r) return; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void modify(int u,int l,int r,int v){ if(tr[u].l >= l && tr[u].r <= r) { pushdown(tr[u],v); return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u<<1,l,r,v); if(r > mid) modify(u<<1|1,l,r,v); } int query(int u){ if(tr[u].lazy){ if(st[tr[u].lazy])return 0; return st[tr[u].lazy] = 1; } if(tr[u].l == tr[u].r ) return 0; return query(u<<1) + query(u<<1|1); } int main(){ int T; cin >> T; while(T--){ v.clear(); //初始化 v.push_back(-0x3f3f3f3f); vector下标处理， 从1开始，设置-0x3f3f3f3f,可以在离散化二分中当作一个边界。 area.clear(); memset(st,0,sizeof st); //初始化 int n; scanf("%d",&n); for(int i = 1;i <= n;i++){ int l,r; scanf("%d%d",&l,&r); r++; 区间染色离散化处理 v.push_back(l),v.push_back(r); 因为后面会排序，所以直接push_back进离散化vector就行。 area.push_back(make_pair(l,r)); c++98只能用make_pair,不能{l,r}; } // sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end()); 离散化去重 for(int i = 1;i <= n;i++) if(v[i] - v[i-1] != 1) v.push_back(v[i] - 1); 获取离散化后的最大边界，用于建树：如果不相邻的话就要多加一个与v[i]相邻的元素 sort(v.begin(),v.end()); // v离散化。 build(1,1,v.size()-1); for(int i = 0;i < n;i++){ int l = area[i].first,r = area[i].second; l = find(l),r = find(r); find函数，把原始的l，r数据通过二分查找，映射到离散化后的l，r上。 modify(1,l,r-1,i+1); } printf("%d\n",query(1)); } return 0; }
套路：
区间染色query查询：
前提：
区间染色问题的query
应对
如果是查颜色种类的话：
int query(int u){ if(tr[u].lazy){ if(st[tr[u].lazy]) return 0; return st[tr[u].lazy] = 1; } if(tr[u].l == tr[u].r ) return 0; return query(u<<1) + query(u<<1|1); }
如果是查不同颜色和颜色对应的段数：
用cnt数组维护
int cnt[N]; int last = 0; void query(int u){ if(last != tr[u].lazy) cnt[tr[u].lazy]++; if(tr[u].lazy || tr[u].l == tr[u].r) { last = tr[u].lazy; return 0; } // 有标记直接进上面的语句了，不需要pushdown query(u<<1),query(u<<1|1); }
区间染色的l，r离散化
前提：l，r的值特别大以至于没法开出对应的树
应对：
vector<int> v;vector<PII > area; 开两个vector，一个离散化处理，一个存原始 int find(int u){return lower_bound(v.begin(),v.end(),u) - v.begin();} 二分查找函数，找到第一个大于等于u的元素，原始l，r可以通过这个find函数映射为离散l，r v.clear(),area.clear(); v.push_back(-0x3f3f3f3f); 让v下标改为1至n for(int i = 1;i <= n;i++){ int l,r; scanf("%d%d",&l,&r); r++; v.push_back(l),v.push_back(r); area.push_back(make_pair(l,r)); } 读入信息，线段树区间染色离散化的r要先++，操作时再-1抵消影响 sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end()); for(int i = 1;i <= n;i++) if(v[i] - v[i-1] != 1) v.push_back(v[i]-1); sort(v.begin(),v.end()); 离散化操作 for(int i = 0;i < n;i++){ int l = find(area[i].first),r = find(area[i].second); modify(1,l,r-1,i+1); } 操作时通过下标0到n-1拿出存原始l，r的vector里的元素 然后经过find映射成离散化l，r modify操作时r-1
区别
区间等值修改里，
lazy存的是子树中所有节点要修改的值或要修改成的值，根据题意决定初始化的值，如例题1中批量+v操作，初始化为0，例题2批量替换，初始化为v的定义域之外的值。
sum存的是子树所有节点sum的总和 ，一般初始化为0.
是一个修改时给节点打上lazy，遇到lazy时解开lazy的过程。
区间自适应修改里，
lazy作为一个bool变量，存的是当前节点是否能代表子树接受修改，根据题意决定初始化的值
sum只有在lazy为1时有实际意义，
存的是这颗所有节点的值都相同的子树里的这个相同的值
修改值时，直接修改节点的值
树状数组
lowbit证明
树状数组详解 - Xenny - 博客园 (cnblogs.com)
单点修改
例题1求区间内操作数量
题链
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
卡壳点：
看了半天，原来不是求区间前缀和，而是求区间内进行了多少次操作……
怪不得题解看着很怪
套路：
前提：
取区间内操作数量
情景：
学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：
- K=1，读入 l,r 表示在 l 到 r 之间种上一种树，每次操作种的树的种类都不同；
- K=2，读入 l,r 表示询问 l 到 r 之间有多少种树。
应对：
用一个括号序列的思路来求解
比线段树更优，更简单，所以不用线段树。
![[Pasted image 20230413173234.png]]
统计10之前有多少个左括号，再统计3之前以后多少个右括号，3之前的右括号肯定可以和10里面的某些左括号(匹配，且在3之前，说明这对括号对应的操作没有覆盖3到10
所以覆盖了3到10的括号就是10之前有多少个左括号减去3之前的右括号
用两个树状数组，一个维护左括号，一个维护右括号，单点修改就行了。
代码
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 5e4 + 10; int tr1[N],tr2[N]; int lowbit(int x){ return x & -x; } void add(int tr[],int x){ for(int i = x;i <= N;i+=lowbit(i)) tr[i] ++; } int query(int tr[],int x){ int res = 0; for(int i= x;i;i-=lowbit(i)) res += tr[i]; return res; } int main(){ int n,m; cin >> n >> m; for(int i = 1;i <= m;i++){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op == 1)add(tr1,l),add(tr2,r); else printf("%d\n",query(tr1,r)- query(tr2,l-1));//左括号-右括号 } return 0; }
例题2树状数组模拟哈希
题链
22ACM集训队-树状数组与线段树基础 - Virtual Judge (vjudge.net)
卡壳点：
树状数组套路不熟悉，query里res没有初始化为0
没有看出来是树状数组模拟哈希，套路不熟悉。
没有注意到没有给出操作数量的范围，没开long long导致wa。
同类题目
( 树状数组哈希前缀和）小朋友排队
[AcWing 1215. 小朋友排队 - AcWing](https://www.acwing.com/activity/content/problem/content/1722/) #### 我的思路（疯狂踩陷阱） // 1e5,1e6 // ，表示小朋友的不高兴程度和的最小值。 // 开始的时候，所有小朋友的不高兴程度都是 0 // 。 // 如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1 // ，如果第二次要求他交换，则他的不高兴程度增加 2 // （即不高兴程度为 3 // ），依次类推。当要求某个小朋友第 k // 次交换时，他的不高兴程度增加 k // 。 // n = (1 + cnt)*cnt / 2; **// 相邻交换的最优解是冒泡排序，要求排序次数** // 每次交换，一个数前面比他大的数量-1，或在后面比他小的数-1，所以交换次数就是在前面且> x，在后面且< x的数字数量，**哈希后求前缀和**可以实现这个操作，**动态求前缀和适合用树状数组，用树状数组模拟hash求前缀和后缀和**，然后等查数列求和求每一项 *** #### 题解思路 // 先前总结过一个 求数组中有多少个数小于等于的套路 // 变化一下， // 求数组中前面有多少个数小于等于x，只要遍历数组，边哈希边前缀和（l-1，x） // 求数组中后面有多少个数小于等于x，只要逆序遍历数组，边哈希边前缀和（l-1，x） // 求数组中前面有多少个数大于等于x，只要遍历数组，边哈希边前缀和（x-1，r） // 求数组中后面有多少个数大于等于x，只要逆序遍历数组，边哈希边前缀和（x-1，r） // 单纯小于或大于x，则x变为x-1或x+1, // 检查数据范围时要把计算式全部看一遍，看看会不会爆范围。 ***// 检查数据范围时看到数据包含0或负数，取模时要打起十二分精神，看看有没有踩到陷阱*** *** ### 套路： 哈希前缀和 前提条件 序列，元素关系。序列中大于x的数量，小于x的数量，或是前面大于x的数量，后面大于x的元素数量 应对 要一个哈希数组，一个保存结果的数组，可能要一个原数组 求数组中前面有多少个数小于等于x，只要遍历数组，边哈希边前缀和（l-1，x） 求数组中后面有多少个数小于等于x，只要逆序遍历数组，边哈希边前缀和（l-1，x） 求数组中前面有多少个数大于等于x，只要遍历数组，边哈希边前缀和（x-1，r） 求数组中后面有多少个数大于等于x，只要逆序遍历数组，边哈希边前缀和（x-1，r） 严格小于或大于x，则x变为x-1或x+1, 发现要求前面时，顺序遍历数组，后面时，倒序遍历数组 检查数据范围时要把计算式全部看一遍，看看会不会爆数据。 如果序列元素会改变，需要动态维护序列，要用树状数组或线段树来模拟哈希 用树状数组模拟哈希的重点是 重点是要满足边哈希，边求哈希前缀和 贪心策略 前提条件 相邻交换序列元素： 应对 最优策略是冒泡排序，每个元素会被交换的次数等于 在前面且> x，在后面且< x的数字数量之和
（树状数组，线段树）（数组模拟哈希）（解题步骤）acwing数星星
https://www.acwing.com/problem/content/1267/
### 题链 https://www.acwing.com/problem/content/1267/ ~~没买课的点不开，耗子尾汁~~ 文末放图片 ### 解决问题先看本质，找数据范围与输出 >// 输出格式 // N行，每行一个整数，分别是 0级，1级，2级，……，N−1级的星星的数目。 // 数据范围 // 1≤N≤15000 // , // 0≤x,y≤32000 **范围不是很特殊，没有太多信息** ### // 带着疑惑去看题干，轻松抓重点 ==// 级是什么，数量如何统计：== **在题干中发现：** >// 如果一个星星的左下方（包含正左和正下）有 k颗星星，就说这颗星星是 k级的。 **// 因为涉及到坐标以及求和，到这里可以想到大概是用一个二维前缀和，但是二维前缀和要开的数组太大了，用不了，再看有没有其他条件， // 结果发现还真有:** >// **不会有星星重叠。星星按 y坐标增序给出，y坐标相同的按 x坐标增序给出。** // 给出的点的y是不严格递增的，且y相同时，x是递增的这意味着，前面的点永远在后面的点的下方， 由此题目就变成按顺序看星星的话可以只看x坐标来判断前面的星星是否要计入后面的点的数量。 数量的计算就可以变成计算哈希统计x坐标各种情况的出现次数，然后计算1~x的前缀和。 // 因为涉及到了数组单点修改以及求和操作，所以可以用一个树状数组或线段树来模拟哈希维护数据 //观察样例发现星星计数时是不计自身的，所以先求树状数组里统计的前缀和，再修改树状数组里的值 // 统计数量级又要统计各种数量的出现情况，又要一层哈希 // 第一颗星星的左下方不可能有星星，且计数时不计自身，必然有0级的星星最后遍历哈希0到n-1 ### 套路： ###### 树状数组模拟哈希 前提条件 需要动态维护序列元素大小以及前缀和。 应对： 求[l,r] 前缀和，用query(r) - query(l - 1) ###### 哈希前缀和 前提条件 序列，元素关系。序列中大于x的数量，小于x的数量，或是前面大于x的数量，后面大于x的元素数量 应对 求数组中前面有多少个数小于等于x，只要遍历数组，边哈希边前缀和（l-1，x） 求数组中后面有多少个数小于等于x，只要逆序遍历数组，边哈希边前缀和（l-1，x） 求数组中前面有多少个数大于等于x，只要遍历数组，边哈希边前缀和（x-1，r） 求数组中后面有多少个数大于等于x，只要逆序遍历数组，边哈希边前缀和（x-1，r） 严格小于或大于x，则x变为x-1或x+1, 检查数据范围时要把计算式全部看一遍，看看会不会爆数据。 如果序列元素会改变，需要动态维护序列，要用树状数组或线段树来模拟哈希 --- ### 代码： ```cpp #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 4e4; using namespace std; int tr[N],w[N],f[N]; int lowbit(int x){ return x & -x; } void add(int x,int v){ for(int i = x;i <= N;i+=lowbit(i)) tr[i] += v; } int query(int x){ int res = 0; for(int i = x;i ;i -=lowbit(i)) res += tr[i]; return res; } int main(){ int n; int x,y; cin >> n; for(int i = 0;i < n;i++){ scanf("%d%d",&x,&y); x++; f[query(x)] ++; add(x,1); } for(int i = 0;i < n;i++){ printf("%d\n",f[i]); } return 0; }
题3树状数组区间修改，用不到，暂时不管
`则A[1]+A[2]+…+A[n]
``= (D[1]) + (D[1]+D[2]) + … + (D[1]+D[2]+…+D[n])
``= n*D[1] + (n-1)*D[2] +… +D[n]
``= n * (D[1]+D[2]+…+D[n]) - (0D[1]+1D[2]+…+(n-1)*D[n])
`1到n的前缀和等于= n * (D[1]+D[2]+…+D[n]) - (0D[1]+1D[2]+…+(n-1)*D[n])
`所以上式可以变为∑ni = 1A[i] = n∑ni = 1D[i] - ∑ni = 1( D[i](i-1) );
`所以是需要维护tr1[i] = iD[i]，tr2[i] = D[i](i-1);
1 int n,m; 2 int a[50005] = {0},c[50005]; //对应原数组和树状数组 3 4 int lowbit(int x){ 5 return x&(-x); 6 } 7 8 void updata(int i,int k){ //在i位置加上k 9 while(i <= n){ 10 c[i] += k; 11 i += lowbit(i); 12 } 13 } 14 15 int getsum(int i){ //求D[1 - i]的和，即A[i]值 16 int res = 0; 17 while(i > 0){ 18 res += c[i]; 19 i -= lowbit(i); 20 } 21 return res; 22 } 23 24 int main(){ 25 cin>>n;27 for(int i = 1; i <= n; i++){ 28 cin>>a[i]; 29 updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值 31 } 32 33 //[x,y]区间内加上k 34 updata(x,k); //A[x] - A[x-1]增加k 35 updata(y+1,-k); //A[y+1] - A[y]减少k 36 37 //查询i位置的值 38 int sum = getsum(i); 39 40 return 0; 41 }
模仿
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 1e4 + 10; int f[N],tr1[N],tr2[N]; int lowbit(int x){ return x & -x; } void add(int x,int v){ for(int i = x;i <= N;i+=lowbit(i)){ tr1[i] += v; tr2[i] += v * (x - 1); } } int query(int x){ int res = 0; for(int i = x;i;i-=lowbit(i)) res += x * tr1[i] - tr2[i]; return res; } int main(){ int n,m; cin >> n >> m; for(int i = 1;i <= m;i++){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op == 1) add(l,1),add(r + 1,-1); else printf("%d\n",query(r) - query(l-1)); } return 0; }
