前言

如果我真的...不再是妖精兵
能够像普通人一样去追求梦想的话
那时候，我希望依偎在这个人的身旁，和他共同生活，希望一起看同样的东西，走同样的路，吃同样的食物，欣赏同样的风景，如果能像那样，一辈子在一起的话

整体评价

t3有个特别技巧， t4分类讨论，理顺真心太难了，最后用了树状数组+容斥原理。

其中t3有个小技巧，区间单向最值维护(min/max), 感觉有点小用。

1. 找到最近的有相同 X 或 Y 坐标的点

1779. 找到最近的有相同 X 或 Y 坐标的点

Java

class Solution {

    // 曼哈顿距离
    // 直接暴力解，不过这类题，可以用stream，可以写的优雅些
    public int nearestValidPoint(int x, int y, int[][] points) {

        int idx = -1;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; i++) {
            int[] p = points[i];
            if (x == p[0] || y == p[1]) {
                if (ans > Math.abs(p[0] - x) + Math.abs(p[1] - y)) {
                    ans = Math.abs(p[0] - x) + Math.abs(p[1] - y);
                    idx = i;
                }
            }
        }
        return idx;
    }
}

2. 判断一个数字是否可以表示成三的幂的和

1780. 判断一个数字是否可以表示成三的幂的和

本质是一个3进制，同时满足3进制表示下为0/1.

Java

class Solution {
    
    public boolean checkPowersOfThree(int n) {

        while (n > 0) {
            int v = n % 3;
            if (v == 2) return false;
            n /= 3;
        }
        
        return true;
        
    }
    
}

3. 所有子字符串美丽值之和

1781. 所有子字符串美丽值之和

用了26维度的前缀和。

整体框架为枚举起点和终点，区间内最大值和最小值，用前缀和简化，但是单独求最大值和最小值，还是需要 $O (26)$

整体算下来，要 $O (26 n^{2})$ . 这边其实是可以优化的。

Java

class Solution {
        
    public int beautySum(String s) {

        char[] buf = s.toCharArray();
        
        int n = buf.length;
        int[][] presum = new int[26][n + 1];
        
        for (int i = 0; i < buf.length; i++) {
            int p = buf[i] - 'a';
            for (int j = 0; j < 26; j++) {
                presum[j][i + 1] = presum[j][i] + ((p == j) ? 1 : 0);
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                int lmax = 0, lmin = Integer.MAX_VALUE;
                for (int k = 0; k < 26; k++) {
                    int d = presum[k][j + 1] - presum[k][i];
                    if (d > 0) {
                        lmax = Math.max(lmax, d);
                        lmin = Math.min(lmin, d);
                    }
                }
                
                ans = ans + (lmax - lmin);
            }
        }
        
        return ans;
        
    }
    
}

这采用区间，维护最小值和最大值，这样从26-> $O (l o g 32)$

Java

class Solution {
        
    public int beautySum(String s) {

        char[] buf = s.toCharArray();        
        int n = buf.length;
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            
            int[] minArr = new int[32 * 2 + 1];
            Arrays.fill(minArr, Integer.MAX_VALUE);
            int[] maxArr = new int[32 * 2 + 1];
            Arrays.fill(maxArr, Integer.MIN_VALUE);

            for (int j = i; j < n; j++) {
                int p = buf[j] - 'a';
                
                // log(32)的做法维护， min和max
                minArr[p + 32] = (minArr[p + 32] == Integer.MAX_VALUE) ? 1 : minArr[p + 32] + 1;
                maxArr[p + 32] = (maxArr[p + 32] == Integer.MIN_VALUE) ? 1 : maxArr[p + 32] + 1;

                // 相当于构建了一颗满二叉树，然后每个节点为子节点的最小值/最大值
                int x = p + 32;
                while (x > 1) {
                    int y = x / 2;
                    minArr[y] = Math.min(minArr[y * 2], minArr[y * 2 + 1]);
                    maxArr[y] = Math.max(maxArr[y * 2], maxArr[y * 2 + 1]);
                    x = y;
                }

                ans = ans + maxArr[1] - minArr[1];
            }
        }
        
        return ans;
        
    }
    
}

4. 统计点对的数目

1782. 统计点对的数目

这题真的有些绕，同时真心难

这边涉及范围查询，所以采用树状数组来维护。

而pair的覆盖边数统计，就成了难点了，因为 $n^{2} (n \leq 2 e^{4})$ ,必然超时。

所以这边需要转化，或者说加速

这边大概三类pair

pair 中只有一个点贡献
pair 中两个独立，同时贡献边数
pair 中两个非独立，需要去重（容斥定律）

这里的难点，在于pair需要满足 $a < b$ ，使得这题更加难上难。

Java

class Solution {

    // bit模板
    static class BIT {
        int n;
        int[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new int[n + 1];
        }

        int lowbit(int x) {
            return x & -x;
        }

        void update(int p, int v) {
            while (p <= n) {
                this.arr[p] += v;
                p += lowbit(p);
            }
        }

        int query(int p) {
            int res = 0;
            while (p > 0) {
                res += arr[p];
                p -= lowbit(p);
            }
            return res;
        }
    }

    public int[] countPairs(int n, int[][] edges, int[] queries) {

        int[] deg = new int[n + 1];

        List<TreeMap<Integer, Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new TreeMap<>());
        }

        TreeSet<Integer> sets = new TreeSet<>();
        for (int[] e: edges) {
            deg[e[0]]++;
            deg[e[1]]++;

            int a = Math.min(e[0], e[1]);
            int b = Math.max(e[0], e[1]);
            TreeMap<Integer, Integer> cur = adj.get(a);
            cur.put(b, cur.getOrDefault(b, 0) + 1);

            sets.add(e[0]);
            sets.add(e[1]);
        }
        List<Integer> arr = sets.stream().collect(Collectors.toList());

        int m = edges.length;
        BIT bit = new BIT(m);

        // *) 
        TreeMap<Integer, Integer> cntMap= new TreeMap<>();
        for (int i = 0; i < arr.size(); i++) {
            int x = arr.get(i);
            cntMap.put(deg[x], cntMap.getOrDefault(deg[x], 0) + 1);
        }

        for (int i = 0; i < arr.size(); i++) {
            int x = arr.get(i);
            // *) 只有一个点，贡献得分
            bit.update(deg[x], n - arr.size());
            
            // *) 计算两点互相独立，贡献得分
            cntMap.put(deg[x], cntMap.get(deg[x]) - 1);
            if (cntMap.get(deg[x]) == 0) {
                cntMap.remove(deg[x]);
            }
            for (Map.Entry<Integer, Integer> e: cntMap.entrySet()) {
                bit.update(deg[x] + e.getKey(), e.getValue());
            }

            // *) 两个点不独立，有交集， 贡献得分
            TreeMap<Integer, Integer> rel = adj.get(x);
            for (Map.Entry<Integer, Integer> e: rel.entrySet()) {
                int y = e.getKey();
                bit.update(deg[x] + deg[y] - e.getValue(), 1);
                // *) 反做
                bit.update(deg[x] + deg[y], -1);
            }
        }


        int rn = queries.length;
        int[] res = new int[rn];

        for (int i = 0; i < rn; i++) {
            res[i] = bit.query(m) - bit.query(queries[i]);
        }

        return res;

    }

}