线段树离散化、二分搜索、特别修改

699. 掉落的方块 - 力扣（LeetCode）

1.如果直接按照原落点的值构造线段树，空间开辟会过大，所以收集所有出现过的点进行离散化

2.方块a落在1--3点，b落在3--4点，如果直接按照落点修改，查询3时位置会认为两方块重叠，但其实没有累到一起，所以方块落点的区域设置为左闭右开就可以避免这个问题

// 掉落的方块
// 有一个二维平面，x轴是最底的边界
// 给定二维整数数组pos，pos[i] = [ lefti, leni ]
// 表示第i个方块边长为leni，左侧边缘在x = lefti位置，所在高度非常高
// 所有方块都是正方形，依次从高处垂直掉落，也就是左边界顺着x = lefti往下
// 如果掉落的方块碰到已经掉落正方形的顶边或者x轴就停止掉落
// 如果方块掉落时仅仅是擦过已经掉落正方形的左侧边或右侧边，并不会停止掉落
// 一旦停止，它就会固定在那里，无法再移动，俄罗斯方块游戏和本题意思一样
// 返回一个整数数组ans ，其中ans[i]表示在第i块方块掉落后整体的最大高度
// 1 <= pos数组长度 <= 1000，1 <= lefti <= 10^8，1 <= leni <= 10^6
class Solution {
public:static const int maxn=2001;vector<int>arr;int max1[maxn<<2];int change[maxn<<2];bool update[maxn<<2];int rank(int size,int v){int l=1,r=size;int ans=0;while(r>=l){int mid=l+((r-l)>>1);if(arr[mid]>=v){ans=mid;r=mid-1;}else l=mid+1;}return ans;}void up(int i){max1[i]=max(max1[i<<1],max1[i<<1|1]);}void lazy(int i,int v){update[i]=true;change[i]=v;max1[i]=v;}void down(int i){if(update[i]){lazy(i<<1,change[i]);lazy(i<<1|1,change[i]);update[i]=false;}}void build(int l,int r,int i){if(r>l){int mid=l+((r-l)>>1);build(l,mid,i<<1);build(mid+1,r,i<<1|1);}max1[i]=0;change[i]=0;update[i]=false;}void updated(int jobl,int jobr,int jobv,int l,int r,int i){if(jobl<=l&&jobr>=r){lazy(i,jobv);}else{int mid=l+((r-l)>>1);down(i);if(jobl<=mid)updated(jobl,jobr,jobv,l,mid,i<<1);if(mid<jobr)updated(jobl,jobr,jobv,mid+1,r,i<<1|1);up(i);}}int query(int jobl,int jobr,int l,int r,int i){if(jobl<=l&&jobr>=r) return max1[i];else{int mid=l+((r-l)>>1);int ans=INT_MIN;down(i);if(mid>=jobl)ans=max(ans,query(jobl,jobr,l,mid,i<<1));if(mid<jobr)ans=max(ans,query(jobl,jobr,mid+1,r,i<<1|1));return ans;}}vector<int> fallingSquares(vector<vector<int>>& positions) {arr.assign(maxn,0);int n=1;for(auto pos:positions){arr[n++]=pos[0];arr[n++]=pos[1]+pos[0]-1;}sort(arr.begin()+1,arr.begin()+n);int size=1;for(int i=2;i<n;i++){if(arr[i]!=arr[size])arr[++size]=arr[i];}build(1,size,1);vector<int>ans;int l,r,h,rem=0;for(auto pos:positions){l=rank(size,pos[0]);r=rank(size,pos[0]+pos[1]-1);h=query(l,r,1,n,1)+pos[1];rem=max(rem,h);ans.push_back(rem);updated(l,r,h,1,n,1);}return ans;}
};

Problem - 4614 (hdu.edu.cn)

此题难点在于怎么插花：如果我们想要知道一段范围上第几个0点，可以使用二分搜索来查询

// 瓶子里的花朵
// 给定n个瓶子，编号从0~n-1，一开始所有瓶子都是空的
// 每个瓶子最多插入一朵花，实现以下两种类型的操作
// 操作 1 from flower : 一共有flower朵花，从from位置开始依次插入花朵，已经有花的瓶子跳过
//                     如果一直到最后的瓶子，花也没有用完，就丢弃剩下的花朵
//                     返回这次操作插入的首个空瓶的位置 和 最后空瓶的位置
//                     如果从from开始所有瓶子都有花，打印"Can not put any one."
// 操作 2 left right  : 从left位置开始到right位置的瓶子，变回空瓶，返回清理花朵的数量
// 测试链接 : https://acm.hdu.edu.cn/showproblem.php?pid=4614
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Code02_VasesAndFlowers {public static int MAXN = 50001;public static int[] sum = new int[MAXN << 2];public static int[] change = new int[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static int n;public static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];}public static void down(int i, int ln, int rn) {if (update[i]) {lazy(i << 1, change[i], ln);lazy(i << 1 | 1, change[i], rn);update[i] = false;}}public static void lazy(int i, int v, int n) {sum[i] = v * n;change[i] = v;update[i] = true;}public static void build(int l, int r, int i) {if (l < r) {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);}sum[i] = 0;update[i] = false;}public static void update(int jobl, int jobr, int jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv, r - l + 1);} else {int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static int query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);int ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}public static int[] insert(int from, int flowers) {// 题目给的位置从0开始// 线段树下标从1开始from++;int start, end;int zeros = n - from + 1 - query(from, n, 1, n, 1);if (zeros == 0) {start = 0;end = 0;} else {start = findZero(from, 1);end = findZero(from, Math.min(zeros, flowers));update(start, end, 1, 1, n, 1);}// 题目需要从0开始的下标start--;end--;return new int[] { start, end };}// s~n范围上// 返回第k个0的位置public static int findZero(int s, int k) {int l = s, r = n, mid;int ans = 0;while (l <= r) {mid = (l + r) >> 1;if (mid - s + 1 - query(s, mid, 1, n, 1) >= k) {ans = mid;r = mid - 1;} else {l = mid + 1;}}return ans;}// 注意题目给的下标从0开始// 线段树下标从1开始public static int clear(int left, int right) {left++;right++;int ans = query(left, right, 1, n, 1);update(left, right, 0, 1, n, 1);return ans;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int t = (int) in.nval;for (int i = 1; i <= t; i++) {in.nextToken();n = (int) in.nval;in.nextToken();int m = (int) in.nval;build(1, n, 1);for (int j = 1; j <= m; j++) {in.nextToken();int op = (int) in.nval;if (op == 1) {in.nextToken();int from = (int) in.nval;in.nextToken();int flowers = (int) in.nval;int[] ans = insert(from, flowers);if (ans[0] == -1) {out.println("Can not put any one.");} else {out.println(ans[0] + " " + ans[1]);}} else {in.nextToken();int left = (int) in.nval;in.nextToken();int right = (int) in.nval;out.println(clear(left, right));}}out.println();}out.flush();out.close();br.close();}}

P4145 上帝造题的七分钟 2 / 花神游历各国 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.此题的修改操作不能通过O(1)的时间完成，只能暴力求解

2.当一段范围的最大值为1时，此时就不需要执行开平发操作了，所以就可以剪枝了(此处的剪枝不是简单的优化常数时间，他减少了遍历规模)

3.数值的最大值为10^12，最多开6次就到1了；而将一个节点开到1，需要遍历6*树高的规模，所以1-n的线段树总势能为n*6*logn，因为有剪枝，所以这就是遍历到的规模。操作次数为m，均摊的时间复杂度为O(logn)

// 范围上开平方并求累加和
// 给定一个长度为n的数组arr，实现以下两种类型的操作
// 操作 0 l r : 把arr[l..r]范围上的每个数开平方，结果向下取整
// 操作 1 l r : 查询arr[l..r]范围上所有数字的累加和
// 两种操作一共发生m次，数据中有可能l>r，遇到这种情况请交换l和r
// 1 <= n, m <= 10^5，1 <= arr[i] <= 10^12
// 测试链接 : https://www.luogu.com.cn/problem/P4145
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {public static int MAXN = 100001;public static long[] arr = new long[MAXN];public static long[] sum = new long[MAXN << 2];public static long[] max = new long[MAXN << 2];public static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];max[i] = Math.max(max[i << 1], max[i << 1 | 1]);}public static void build(int l, int r, int i) {if (l == r) {sum[i] = arr[l];max[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}}// sqrt方法是最核心的// 注意和常规线段树不一样，这里没有懒更新，也就不需要有down方法// 只有根据范围最大值信息的剪枝// 时间复杂度的分析就是课上讲的势能分析// 不用纠结单次调用的复杂度// 哪怕调用再多次sqrt方法，总的时间复杂度也就是O(n * 6 * logn)public static void sqrt(int jobl, int jobr, int l, int r, int i) {if (l == r) {long sqrt = (long) Math.sqrt(max[i]);sum[i] = sqrt;max[i] = sqrt;} else {int mid = (l + r) >> 1;if (jobl <= mid && max[i << 1] > 1) {sqrt(jobl, jobr, l, mid, i << 1);}if (jobr > mid && max[i << 1 | 1] > 1) {sqrt(jobl, jobr, mid + 1, r, i << 1 | 1);}up(i);}}// 没有懒更新// 不需要调用down方法public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;long ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (long) in.nval;}build(1, n, 1);in.nextToken();int m = (int) in.nval;for (int i = 1, op, jobl, jobr, tmp; i <= m; i++) {in.nextToken();op = (int) in.nval;in.nextToken();jobl = (int) in.nval;in.nextToken();jobr = (int) in.nval;if (jobl > jobr) {tmp = jobl;jobl = jobr;jobr = tmp;}if (op == 0) {sqrt(jobl, jobr, 1, n, 1);} else {out.println(query(jobl, jobr, 1, n, 1));}}out.flush();out.close();br.close();}}

The Child and Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.一个数不停的取模logv次就到1了

2.总势能：

// 包含取模操作的线段树
// 给定一个长度为n的数组arr，实现如下三种操作，一共调用m次
// 操作 1 l r : 查询arr[l..r]的累加和
// 操作 2 l r x : 把arr[l..r]上每个数字对x取模
// 操作 3 k x : 把arr[k]上的数字设置为x
// 1 <= n, m <= 10^5，操作1得到的结果，有可能超过int范围
// 测试链接 : https://www.luogu.com.cn/problem/CF438D
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {public static int MAXN = 100001;public static int[] arr = new int[MAXN];public static long[] sum = new long[MAXN << 2];public static int[] max = new int[MAXN << 2];public static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];max[i] = Math.max(max[i << 1], max[i << 1 | 1]);}public static void build(int l, int r, int i) {if (l == r) {sum[i] = max[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;long ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}public static void mod(int jobl, int jobr, int jobv, int l, int r, int i) {if (jobv > max[i]) {return;}if (l == r) {sum[i] %= jobv;max[i] %= jobv;} else {int mid = (l + r) >> 2;if (jobl <= mid) {mod(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {mod(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static void update(int jobi, int jobv, int l, int r, int i) {if (l == r) {sum[i] = max[i] = jobv;} else {int mid = (l + r) >> 1;if (jobi <= mid) {update(jobi, jobv, l, mid, i << 1);} else {update(jobi, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;in.nextToken();int m = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (int) in.nval;}build(1, n, 1);for (int i = 1, op; i <= m; i++) {in.nextToken();op = (int) in.nval;if (op == 1) {in.nextToken();int jobl = (int) in.nval;in.nextToken();int jobr = (int) in.nval;out.println(query(jobl, jobr, 1, n, 1));} else if (op == 2) {in.nextToken();int jobl = (int) in.nval;in.nextToken();int jobr = (int) in.nval;in.nextToken();int jobv = (int) in.nval;mod(jobl, jobr, jobv, 1, n, 1);} else {in.nextToken();int jobi = (int) in.nval;in.nextToken();int jobv = (int) in.nval;update(jobi, jobv, 1, n, 1);}}out.flush();out.close();br.close();}}

P3740 [HAOI2014] 贴海报 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.不需要up函数：因为up函数是用来随时查询用的，而此题只需要查询一次

// 贴海报
// 有一面墙，有固定高度，长度为n，有m张海报，所有海报的高度都和墙的高度相同
// 从第1张海报开始，一张一张往墙上贴，直到n张海报贴完
// 每张海报都给出张贴位置(xi, yi)，表示第i张海报从墙的左边界xi一直延伸到右边界yi
// 有可能发生后面的海报把前面的海报完全覆盖，导致看不到的情况
// 当所有海报贴完，返回能看到海报的数量，哪怕只漏出一点的海报都算
// 1 <= n、xi、yi <= 10^7，1 <= m <= 10^3
// 测试链接 : https://www.luogu.com.cn/problem/P3740
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main {public static int MAXM = 1001;public static int[] pl = new int[MAXM];public static int[] pr = new int[MAXM];public static int[] num = new int[MAXM*3];// 线段树的某个范围上是否被设置成了统一的海报// 如果poster[i] != 0，poster[i]表示统一海报的编号// 如果poster[i] == 0，表示该范围上没有海报或者海报编号没统一public static int[] poster = new int[MAXM << 4];// 某种海报编号是否已经被统计过了// 只在最后一次查询，最后统计海报数量的阶段时候使用public static boolean[] visited = new boolean[MAXM];public static int collect(int m) {Arrays.sort(num, 1, m + 1);int size = 1;for (int i = 2; i <= m; i++) {if (num[size] != num[i]) {num[++size] = num[i];}}int cnt = size;for (int i = 2; i <= size; i++) {if (num[i - 1] + 1 < num[i]) {num[++cnt] = num[i - 1] + 1;}}Arrays.sort(num, 1, cnt + 1);return cnt;}public static int rank(int l, int r, int v) {int m;int ans = 0;while (l <= r) {m = (l + r) >> 1;if (num[m] >= v) {ans = m;r = m - 1;} else {l = m + 1;}}return ans;}public static void down(int i) {if (poster[i] != 0) {poster[i << 1] = poster[i];poster[i << 1 | 1] = poster[i];poster[i] = 0;}}public static void build(int l, int r, int i) {if (l < r) {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);}poster[i] = 0;}public static void update(int jobl, int jobr, int jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {poster[i] = jobv;} else {down(i);int mid = (l + r) >> 1;if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}}}public static int query(int jobl, int jobr, int l, int r, int i) {if (l == r) {if (poster[i] != 0 && !visited[poster[i]]) {visited[poster[i]] = true;return 1;} else {return 0;}} else {down(i);int mid = (l + r) >> 1;int ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int n = (int) in.nval;int size = 0;num[++size] = n;in.nextToken();int m = (int) in.nval;for (int i = 1; i <= m; i++) {in.nextToken();pl[i] = (int) in.nval;in.nextToken();pr[i] = (int) in.nval;num[++size] = pl[i];num[++size] = pr[i];}size = collect(size);build(1, size, 1);for (int i = 1, jobl, jobr; i <= m; i++) {jobl = rank(1, size, pl[i]);jobr = rank(1, size, pr[i]);update(jobl, jobr, i, 1, size, 1);}out.println(query(1, rank(1, size, n), 1, size, 1));out.flush();out.close();br.close();}}