差分的两种用法

用法一：同时改变区间中的数的大小

AC.100增减序列

import java.util.Scanner;

public class Main {
    static int N = (int) (1e5+10);
    static int[] a = new int[N];
    public static void main(String agrs[]) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        for(int i=1;i<=n;i++) {
            a[i] = reader.nextInt();
        }
        for(int i=n;i>=2;i--)a[i]-=a[i-1];
        long zheng = 0,fu = 0;
        for(int i=2;i<=n;i++) {
            if(a[i]>0)zheng+=a[i];
            else fu-=a[i];
        }
        System.out.println(Math.min(zheng, fu)+Math.abs(fu-zheng));
        System.out.println(Math.abs(fu-zheng)+1);

    }
}

用法二：用差分数组中的每个数表示相邻两个数之间的差

AC.101

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static int N = 10010;
    static int[] c = new int[N];
    static int[] d = new int[N];
    static int n,p,h,m;
    static Set<PI> st = new HashSet<PI>(); //对自定义类的判重需要重写hashCode()与equals()函数
    // static boolean[][] st = new boolean[N][N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String args[]) throws IOException {
        String[] s = in.readLine().split(" ");
        n =Integer.parseInt(s[0]);
        p =Integer.parseInt(s[1]);
        h =Integer.parseInt(s[2]);
        m =Integer.parseInt(s[3]);
        int a,b;
        for(int i=1;i<=m;i++) {
            s = in.readLine().split(" ");
            a = Integer.parseInt(s[0]);
            b = Integer.parseInt(s[1]);
            if(a>b) {
                a = a^b;
                b = a^b;
                a = a^b;
            }
            PI t = new PI(a,b);
            if(!st.contains(t)) {
                st.add(t);
                d[a+1]--;d[b]++;
            }
            // if(!st[a][b]){
            //     st[a][b] = true;
            //     d[a+1]--;d[b]++;
            // }
        }
        for(int i=1;i<=n;i++) {
            c[i] = c[i-1]+d[i];
            System.out.println(h+c[i]);
        }
    }
}
class PI{
    int x;
    int y;
    public PI(int x,int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public int hashCode() {
        return this.x;
    }
    @Override
    public boolean equals(Object o) {
        PI t = (PI)o;
        if(x == t.x&&y==t.y)return true;
        else return false;
    }
}