文章目录

• • 1. 动态求连续区间和（线段树）
  • 2.数星星（树状数组）
  • 3.数列区间最大值（线段树维护区间最大值）
  • 4.小朋友排队（归并排序/树状数组/冒泡）
  • 5.油漆面积（线段树/扫描线❗）
  • 6.三体攻击（二分+前缀和+三维差分❗）
  • 7.螺旋折线(推规律)❗
  • 8.差分（差分）
  • 9.差分矩阵（二维差分）

1. 动态求连续区间和（线段树）

💡💡💡思路：
典型的线段树点修改与区间和

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] a = new int[N];static node[] t = new node[N*4];static int n = 0, m = 0;public static void main(String[] args) throws Exception{init();String[]nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}build(1,1,n);for(int i = 1; i <= m; i++) {String[]kab = br.readLine().split(" ");int k = Integer.parseInt(kab[0]);int a = Integer.parseInt(kab[1]);int b = Integer.parseInt(kab[2]);if(k == 0) {System.out.println(query(1,a,b));}else {update(1,a,a,b);}}}private static void update(int p, int l, int r, int d) {if(t[p].l >= l && t[p].r <= r) {t[p].sum += (t[p].r - t[p].l + 1)*d;t[p].add += d;return;}spread(p);int mid = (t[p].l + t[p].r) >> 1;if(l <= mid) {update(p*2, l, r,d);}if(r > mid) {update(p*2+1, l, r,d);}t[p].sum = t[p*2].sum + t[p*2 + 1].sum;}private static void spread(int p) {if(t[p].add == 0) {return;}t[p*2].sum += t[p].add*(t[p*2].r - t[p*2].l + 1);t[p*2 + 1].sum += t[p].add*(t[p*2 + 1].r - t[p*2 + 1].l + 1);t[p*2].add += t[p].add;t[p*2+1].add += t[p].add;t[p].add = 0;}private static long query(int p, int l, int r) {if(t[p].l >= l && t[p].r <= r) {return t[p].sum;}spread(p);long val = 0;int mid = (t[p].l + t[p].r) >> 1;if(l <= mid) {val += query(p*2, l, r);}if(r > mid) {val += query(p*2+1, l, r);}return val;}private static void init() {for(int i = 0; i < N*4; i++) {t[i] = new node();}}private static void build(int p, int l, int r) {t[p].l = l;t[p].r = r;if(l == r) {t[p].sum = a[l];return;}int mid = (t[p].l + t[p].r) >> 1;build(p*2,l,mid);build(p*2+1, mid + 1, r);t[p].sum = t[p*2].sum + t[p*2+1].sum;}
}
class node{int l,r;int add,sum;
}

2.数星星（树状数组）

3.数列区间最大值（线段树维护区间最大值）

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e5 + 10);static int[] a = new int[N];static node[] t = new node[N*4];static int n = 0, m = 0;public static void main(String[] args) throws Exception{init();String[]nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}build(1,1,n);for(int i = 1; i <= m; i++) {String[]ab = br.readLine().split(" ");int a = Integer.parseInt(ab[0]);int b = Integer.parseInt(ab[1]);out.println(query(1,a,b));}out.flush();}private static long query(int p, int l, int r) {if(t[p].l >= l && t[p].r <= r) {return t[p].maxn;}long val = -Integer.MAX_VALUE; //注意初始化int mid = (t[p].l + t[p].r) >> 1;if(l <= mid) {val =Math.max(val, query(p*2, l, r));}if(r > mid) {val = Math.max(val,query(p*2+1, l, r));}return val;}private static void init() {for(int i = 0; i < N*4; i++) {t[i] = new node();}}private static void build(int p, int l, int r) {t[p].l = l;t[p].r = r;if(l == r) {t[p].maxn = a[l];return;}int mid = (t[p].l + t[p].r) >> 1;build(p*2,l,mid);build(p*2+1, mid + 1, r);t[p].maxn = Math.max(t[p*2].maxn , t[p*2+1].maxn);}
}
class node{int l,r;int maxn;
}

4.小朋友排队（归并排序/树状数组/冒泡）

思路：其实就是求每个人前面比它大的，后面比它小的，显然是求逆序对
法1：冒泡排序

显然求解过程符合冒泡排序的原理，每次只允许交换相邻的两个元素，但是这种方法肯定是会T的

#include 
using namespace std;
#define int long long
const int N = 100010;
struct node {int val;int k;
}a[N];
signed main() {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i].val;a[i].k = 0;}for (int i = 1; i <= n - 1; i ++) {for (int j = 1; j <= n - 1; j ++) {if (a[j].val > a[j+1].val) {a[j].k ++;a[j+1].k ++;node t = a[j];a[j] = a[j+1];a[j+1] = t;}}}int sum = 0;for (int i = 1; i <= n; i ++) {// cout << a[i].k << ' ';sum += a[i].k * (a[i].k + 1) / 2;}cout << sum;;
}

法2：归并排序
同平时的归并排序求逆序对有所不同，我们需要求前面比它大的，后面比它小的，因此需要进行两次归并排序，升序排序求前面比它大的个数，降序排序求后面比他小的。
需要注意的是java中深拷贝与浅拷贝（深拷贝中基本数据类型是值传递，但是引用类型的话就是指向同一地址空间，所以在对b进行赋值的时候，不能直接将a赋值给b，会导致他俩的操作互相影响）

#include 
using namespace std;
#define int long long
const int N = 100010;
struct node {int val;int k;
}a[N];
signed main() {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i].val;a[i].k = 0;}for (int i = 1; i <= n - 1; i ++) {for (int j = 1; j <= n - 1; j ++) {if (a[j].val > a[j+1].val) {a[j].k ++;a[j+1].k ++;node t = a[j];a[j] = a[j+1];a[j+1] = t;}}}int sum = 0;for (int i = 1; i <= n; i ++) {// cout << a[i].k << ' ';sum += a[i].k * (a[i].k + 1) / 2;}cout << sum;;
}

5.油漆面积（线段树/扫描线❗）

**
法1：暴力枚举标记（TLE）
需要注意遍历循环的下标范围

比如上图说（1，1）和（4，4）为矩形两个对角点，那么我们可以覆盖的范围显然是绿色部分（所以遍历的时候两边只能取到一边，取哪边都是可以的）

for(int x = x1 + 1; x <= x2; x++) {for(int y = y1 + 1; y <= y2; y++) {if(!vis[x][y]) {vis[x][y] = true;sum++;}}}

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e4 + 10);static boolean vis[][] = new boolean[N][N];static int n = 0, m = 0;static long sum = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());for(int i = 1; i <= n; i++) {String[] xy = br.readLine().split(" ");int x1 = Integer.parseInt(xy[0]);int y1= Integer.parseInt(xy[1]);int x2 = Integer.parseInt(xy[2]);int y2 = Integer.parseInt(xy[3]);for(int x = x1; x < x2; x++) {  //此处不能取等号，否则会导致多算for(int y = y1; y < y2; y++) {  //此处同上if(!vis[x][y]) {vis[x][y] = true;sum++;}}}}out.println(sum);out.flush();}}

法2：线段树+扫面线（有点难😢）

有点难

留坑

6.三体攻击（二分+前缀和+三维差分❗）

感觉看起来像差分，但是并不会，哈哈哈
没想到还有三维差分（✪ ω ✪）
具有单调性，二分答案判定是否可行

s(x,y,z)
b(x,y.x)
首先压缩掉z轴
s(x.y,z) = s(x - 1,y,z) + s(x,y-1,z)-s(x-1,y-1,z)+b(x,y,z)+s(x,y,z-1)-s(x-1,y,z-1)-s(x,y-1,z-1)+s(x-1,y-1,z-1)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
public class Main 
{static final int N = 2000010;static long s[] = new long[N], b[] = new long[N],bp[] = new long[N];static int op[][] = new int[N / 2][7]; static int d[][] = {{0, 0, 0, 1},{0, 0, 1, -1},{0, 1, 0, -1},{0, 1, 1, 1},{1, 0, 0, -1},{1, 0, 1, 1},{1, 1, 0, 1},{1, 1, 1, -1},};static int A, B, C, m;public static void main(String[] args) throws Exception{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String str1[] = br.readLine().split(" ");A = Integer.parseInt(str1[0]);B = Integer.parseInt(str1[1]);C = Integer.parseInt(str1[2]);m = Integer.parseInt(str1[3]);String str2[] = br.readLine().split(" ");for(int i = 1; i <= A; i ++)for(int j = 1; j <= B; j ++)for(int k = 1; k <= C; k ++)s[get(i, j, k)] = Long.parseLong(str2[get(i - 1, j - 1, k - 1)]);//构造差分矩阵b[]for(int i = 1; i <= A; i ++)for(int j = 1; j <= B; j ++)for(int k = 1; k <= C; k ++)for(int u = 0; u < 8; u ++){int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];b[get(i, j, k)] += s[get(x, y, z)] * t;}//操作for(int i = 1; i <= m; i ++){String str3[] = br.readLine().split(" ");for(int j = 0; j < 7; j ++)op[i][j] = Integer.parseInt(str3[j]);}//二分攻击次数int l = 1, r = m;int res = -1;while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) {res = mid;r = mid - 1;}else {l = mid + 1;}}System.out.println(res);}//三维坐标(i, j, k)映射成一维坐标(i * B + j) * C + kpublic static int get(int i, int j, int k){return (i * B + j) * C + k;}//二分答案public static boolean check(int mid){//拷贝一份for(int i = 0; i < N; i ++)bp[i] = b[i];for(int i = 1; i <= mid; i ++){int x1 = op[i][0], x2 = op[i][1];int y1 = op[i][2], y2 = op[i][3];int z1 = op[i][4], z2 = op[i][5];int h = op[i][6];bp[get(    x1,      y1,      z1)] -= h;bp[get(    x1,      y1,  z2 + 1)] += h;bp[get(    x1,  y2 + 1,      z1)] += h;bp[get(    x1,  y2 + 1,  z2 + 1)] -= h;bp[get(x2 + 1,      y1,      z1)] += h;bp[get(x2 + 1,      y1,  z2 + 1)] -= h;bp[get(x2 + 1,  y2 + 1,      z1)] -= h;bp[get(x2 + 1,  y2 + 1,  z2 + 1)] += h;}Arrays.fill(s, 0);for(int i = 1; i <= A; i ++)for(int j = 1; j <= B; j ++)for(int k = 1; k <= C; k ++){s[get(i, j, k)] = bp[get(i, j, k)];for(int u = 1; u < 8; u ++){int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];s[get(i, j, k)] -= s[get(x, y, z)] * t;}if(s[get(i, j, k)] < 0)return true;}return false;}
}

7.螺旋折线(推规律)❗

看大佬的博客，真的很奇妙博客来源
找规律发现每层的右上角所需步数为4k*k,我们可以先通过坐标推出所在的层数，因为我们是顺时针转的，所以当点在
该层的左或上的时候，减去该点到右上角的曼哈顿距离，如果在该层的有或下加上该点到右上角的曼哈顿距离。
注意数据范围

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (2e6 + 10);static int n = 0, m = 0;public static void main(String[] args) throws Exception{String[] xy = br.readLine().split(" ");long x = Long.parseLong(xy[0]);long y = Long.parseLong(xy[1]);long k = Math.max(Math.abs(x),Math.abs(y));long base = 4 * k * k;if(x >= y) {System.out.println(base + Math.abs(x - k) + Math.abs(y - k));}else {System.out.println(base - Math.abs(x - k) - Math.abs(y - k));}}
}

8.差分（差分）

差分模板

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int)(1e5 + 100);static int[] a = new int[N];static int[] d = new int[N];static int n = 0, m = 0;public static void main(String[] args) throws Exception{String[]nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);String[] aa = br.readLine().split(" ");for(int i = 1;i <= n; i++){a[i] = Integer.parseInt(aa[i - 1]);d[i] = a[i] - a[i - 1];}for(int i = 1; i <= m; i++){String[] lrc = br.readLine().split(" ");int l = Integer.parseInt(lrc[0]);int r = Integer.parseInt(lrc[1]);int c = Integer.parseInt(lrc[2]);d[l]+=c; d[r+1]-=c;}for(int i = 1; i <= n; i++){a[i] = d[i] + a[i - 1];}for(int i = 1; i <= n; i++){System.out.print(a[i] + " ");}}
}

9.差分矩阵（二维差分）

画个图，类比一下一维差分就好啦

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e3 + 10);static int[][] d = new int[N][N];static long [][] sum = new long[N][N];static int n = 0, m = 0;public static void main(String[] args) throws Exception{String[] nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);int q = Integer.parseInt(nm[2]);for(int i = 1; i <= n; i++) {String[] aa = br.readLine().split(" ");for(int j = 1; j <= m; j++) {sum[i][j] = Integer.parseInt(aa[j - 1]);insert(i,j,i,j,sum[i][j]);}}for(int i = 1; i <= q; i++) {String[] ops = br.readLine().split(" ");int x1 = Integer.parseInt(ops[0]);int y1 = Integer.parseInt(ops[1]);int x2 = Integer.parseInt(ops[2]);int y2 = Integer.parseInt(ops[3]);long c = Long.parseLong(ops[4]);insert(x1, y1, x2, y2, c);}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + d[i][j];}}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {out.print(sum[i][j] + " ");}out.println();}out.flush();}private static void insert(int x1, int y1, int x2, int y2, long c) {d[x1][y1] += c;d[x1][y2 +1] -= c;d[x2 + 1][y1] -= c;d[x2 + 1][y2 + 1] += c; }
}