问题描述

乔帝要规划一次星际旅行，星际空间可以视为一个 $3$ 维坐标系，乔帝有 $n \in [1, 1 0^{9}]$ 个动力装置排成一行（下标从 $1$ 到 $n$ ）。第 $i$ 个动力装置可以让他的飞船 $3$ 个维度的坐标分别增加 $x_{i}, y_{i}, z_{i}$ 。一开始这些动力装置的所有参数都是 $0$ 。在规划过程中，乔帝可能会对动力装置进行调整，也可能会对一些动力装置的动力进行评估。具体来说，乔帝会进行 $m (m \leq 40000)$ 次操作，每次操作可能是以下四种操作之一：

动力增加：指定一个区间 $[L, R]$ 和三个参数 $a, b, c$ ，令区间内所有动力装置的 $3$ 维坐标分别增加 $a, b, c$
动力强化：指定一个区间 $[L, R]$ 和一个参数 $k$ ，令区间内所有动力装置的3维坐标分别乘 $k$
动力转向：指定一个区间 $[L, R]$ ，令区间内所有动力装置的 $x, y, z$ 坐标分别变为原来的 $y$ 坐标， $z$ 坐标， $x$ 坐标
动力查询：指定一个区间 $[L, R]$ ，询问如果使用区间内所有动力装置各一次能将乔帝送到离起点多远的地方（输出距离的平方除以 $1 0^{9} + 7$ 的余数）

输入格式

从标准输入读入数据。
第一行包含两个正整数 $n, m$ 。
接下来 $m$ 行，每行用若干个空格分隔的整数表示一个操作。
每行的第一个整数表示这次进行的是哪一种操作， $1, 2, 3, 4$ 分别表示动力增加、动力强化、动力转向、动力查询。
每行的接下来两个整数表示 $L, R$ ，含义如上面所述。
每行接下来若干个整数，根据操作类型确定，为 $a, b, c$ 或 $k$ 或空。

输出格式

输出到标准输出。
对于每个动力查询操作，输出一行，包含一个整数，表示查询的答案。

样例输入

5 5
1 2 4 5 6 7
3 5 5
2 1 2 4
4 1 3
4 2 5

样例输出

2750
3960

样例解释

一共有 $5$ 个动力装置。
对于第 $1$ 个操作，令第 $2, 3, 4$ 个动力装置的动力变为 $(5, 6, 7)$ 。
对于第 $2$ 个操作，令第 $5$ 个动力装置转向，为 $(0, 0, 0)$ 。
对于第 $3$ 个操作，令第 $1, 2$ 个动力装置变为原来的 $4$ 倍，第一个变为 $(0, 0, 0)$ ，第二个变为 $(20, 24, 28)$ 。
对于第 $4$ 个操作，是查询，送到离起点 $(0 + 20 + 5, 0 + 24 + 6, 0 + 28 + 7)$ ，距离的平方为 $2750$ 。
对于第 $5$ 个操作，也是查询，送到离起点 $(20 + 5 + 5 + 0, 24 + 6 + 6 + 0, 28 + 7 + 7 + 0)$ ，距离的平方为 $3960$ 。

数据范围

对于 $20%$ 的数据， $n, m \leq 1000$ ；
对于另外 $20%$ 的数据， $n \leq 1000000$ ，且只包含第 $1, 4$ 种操作；
对于另外 $20%$ 的数据， $n \leq 1000000$ ，且只包含第 $1, 2, 4$ 种操作；
对于另外 $20%$ 的数据， $n \leq 1000000$ ；
对于另外 $20%$ 的数据，没有特殊性质。
所有输入的数字都在 $[1, 1 0^{9}]$ 范围内。
所有的数据中 $m \in [1, 40000]$ 。
所有的操作满足 $L, R \in [1, n]$ 。

算法分析

暴力模拟：20分
线段树（仅包含加法的 LazyTag）：40分
线段树（包含加法和乘法的 LazyTag）：60分
线段树（包含加法、乘法和旋转的 LazyTag）：80分
线段树（包含加法、乘法和旋转的 LazyTag）+ 离散化：100分

线段树之所以能够显著降低复杂度，是因为它的“不访问，不更新”的特点，而这一点是通过线段树节点的 LazyTag 来实现的。具体来说，就是当一个节点所代表的区间完全被包含在所操作的区间内时，我们无需再向下递归，只需要修改其 LazyTag 值即可。本题最大的难点在于三种 LazyTag 的合并问题。
我们规定三种 LazyTag 的结算顺序为：先做乘法，再做加法，最后做旋转。

乘法和旋转操作并不冲突，因为先乘后旋转和先旋转后乘是没有区别的。
默认顺序是先乘后加，如果遇到先加后乘的情况，就做如下处理：

(x \times t a g_{1} + t a g_{2}) \times t a g^{'} \Rightarrow x \times (t a g_{1} \times t a g^{'}) + (t a g_{2} \times t a g^{'})

默认顺序是先加后旋转，如果遇到先旋转后加的情况，就先将加法 $t a g$ 反向旋转之后再和原来的加法 $t a g$ 合并

AC代码

截屏2021-03-18 下午11.56.52.png

import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] rec = new int[m][];
        for (int i = 0; i < m; ++ i) {
            int typ = scan.nextInt();
            if (typ == 1) {
                rec[i] = new int[6];
                rec[i][0] = typ;
                for (int j = 1; j <= 5; ++ j) rec[i][j] = scan.nextInt();
            } else if (typ == 2) {
                rec[i] = new int[4];
                rec[i][0] = typ;
                for (int j = 1; j <= 3; ++ j) rec[i][j] = scan.nextInt();
            } else {
                rec[i] = new int[3];
                rec[i][0] = typ;
                for (int j = 1; j <= 2; ++ j) rec[i][j] = scan.nextInt();
            }
        }
        LSH.build(n, rec);
        XDTree T = new XDTree(1, LSH.N);
        for (int i = 0; i < m; ++ i) {
            int typ = rec[i][0];
            int L = LSH.Index.get(rec[i][1]);
            int R = LSH.Index.get(rec[i][2]);
            if (typ == 1) {
                int[] ad = new int[3];
                ad[0] = rec[i][3];
                ad[1] = rec[i][4];
                ad[2] = rec[i][5];
                T.addElement(L, R, ad);
            } else if (typ == 2) {
                int k = rec[i][3];
                T.multiplyElement(L, R, k);
            } else if (typ == 3) {
                T.transElement(L, R);
            } else {
                System.out.println(T.query(L, R));
            }
        }
        scan.close();
    }
}

class LSH {
    public static HashMap<Integer, Integer> Index;
    public static ArrayList<Integer> Left;
    public static ArrayList<Integer> Right;
    public static int N;

    public static void build(int n, int[][] rec) {
        TreeSet<Integer> S = new TreeSet<>();
        for (int[] x : rec) {
            for (int i = 1; i <= 2; ++ i) {
                for (int y = Math.max(1, x[i]-1); y <= Math.min(n, x[i]+1); ++ y) {
                    S.add(y);
                }
            }
        }
        ArrayList<Integer> temp = new ArrayList<>();
        if (!S.contains(1)) S.add(1);
        if (!S.contains(n)) S.add(n);
        for (int x : S) temp.add(x);
        temp.add(n+1);
        Left = new ArrayList<>();
        Right = new ArrayList<>();
        Left.add(-1);
        Right.add(-1);
        Index = new HashMap<>();
        N = 0;
        for (int i = 0; i < temp.size()-1; ++ i) {
            Left.add(temp.get(i));
            Right.add(temp.get(i+1)-1);
            N ++;
            Index.put(temp.get(i), N);
        }
    }
}

class XDTree {
    TreeNode root;
    static int MOD = 1000000007;

    public XDTree(int l, int r) {
        root = build(l, r);
    }

    private TreeNode build(int l, int r) {
        if (l > r) return null;
        if (l == r) return new TreeNode(l, r);
        int mid = (l+r) >> 1;
        TreeNode cnt = new TreeNode(l, r);
        cnt.left = build(l, mid);
        cnt.right = build(mid+1, r);
        return cnt;
    }

    private void update(TreeNode cnt) {
        if (cnt.l == cnt.r) return;
        for (int i = 0; i < 3; ++ i) {
            cnt.s[i] = (cnt.left.s[i] + cnt.right.s[i]) % MOD;
        }
    }

    private void passDown(TreeNode cnt) {
        if (cnt.l == cnt.r) return;
        if (cnt.k != 1) {
            multiply(cnt.left, cnt.left.l, cnt.left.r, cnt.k);
            multiply(cnt.right, cnt.right.l, cnt.right.r, cnt.k);
            cnt.k = 1;
        }
        if (cnt.ad[0]>0 || cnt.ad[1]>0 || cnt.ad[2]>0) {
            add(cnt.left, cnt.left.l, cnt.left.r, cnt.ad);
            add(cnt.right, cnt.right.l, cnt.right.r, cnt.ad);
            Arrays.fill(cnt.ad, 0);
        }
        if (cnt.rev != 0) {
            trans(cnt.left, cnt.left.l, cnt.left.r, cnt.rev);
            trans(cnt.right, cnt.right.l, cnt.right.r, cnt.rev);
            cnt.rev = 0;
        }
    }

    private void add(TreeNode cnt, int l, int r, int[] ad) {
        if (cnt.l > r || cnt.r < l) return;
        if (l <= cnt.l && cnt.r <= r) {
            for (int i = 0; i < 3; ++ i) {
                cnt.ad[(i + cnt.rev) % 3] = (cnt.ad[(i + cnt.rev) % 3] + ad[i]) % MOD;
                cnt.s[i] = (cnt.s[i] + cheng(ad[i], LSH.Right.get(cnt.r)-LSH.Left.get(cnt.l)+1)) % MOD;
            }
            return;
        }
        passDown(cnt);
        add(cnt.left, l, r, ad);
        add(cnt.right, l, r, ad);
        update(cnt);
    }

    public void addElement(int l, int r, int[] ad) {
        add(root, l, r, ad);
    }

    private int cheng(int x, int y) {
        long z = ((long)x * (long)y) % (long)MOD;
        return (int)z;
    }

    private void multiply(TreeNode cnt, int l, int r, int k) {
        if (cnt.l > r || cnt.r < l) return;
        if (l <= cnt.l && cnt.r <= r) {
            cnt.k = cheng(cnt.k, k);
            for (int i = 0; i < 3; ++ i) {
                cnt.ad[i] = cheng(cnt.ad[i], k);
                cnt.s[i] = cheng(cnt.s[i], k);
            }
            return;
        }
        passDown(cnt);
        multiply(cnt.left, l, r, k);
        multiply(cnt.right, l, r, k);
        update(cnt);
    }

    public void multiplyElement(int l, int r, int k) {
        multiply(root, l, r, k);
    }

    private void trans(TreeNode cnt, int l, int r, int t) {
        if (cnt.l > r || cnt.r < l) return;
        if (l <= cnt.l && cnt.r <= r) {
            cnt.rev = (cnt.rev + t) % 3;
            for (int i = 0; i < t; ++ i) {
                int key = cnt.s[0];
                cnt.s[0] = cnt.s[1];
                cnt.s[1] = cnt.s[2];
                cnt.s[2] = key;
            }
            return;
        }
        passDown(cnt);
        trans(cnt.left, l, r, t);
        trans(cnt.right, l, r, t);
        update(cnt);
    }

    public void transElement(int l, int r) {
        trans(root, l, r, 1);
    }

    private int[] getSum(TreeNode cnt, int l, int r) {
        if (cnt.l > r || cnt.r < l) return new int[]{0, 0, 0};
        if (l <= cnt.l && cnt.r <= r) return cnt.s;
        passDown(cnt);
        int[] ll = getSum(cnt.left, l, r);
        int[] rr = getSum(cnt.right, l, r);
        int[] ret = new int[3];
        for (int i = 0; i < 3; ++ i) {
            ret[i] = (ll[i] + rr[i]) % MOD;
        }
        return ret;
    }

    public int query(int l, int r) {
        int[] x = getSum(root, l, r);
        int ret = 0;
        for (int i = 0; i < 3; ++ i) {
            ret = (ret + cheng(x[i], x[i])) % MOD;
        }
        return ret;
    }
}

class TreeNode {
    int l, r;
    int[] s;
    int[] ad;
    int k;
    int rev;
    TreeNode left, right;
    
    public TreeNode(int _l, int _r) {
        l = _l;
        r = _r;
        s = new int[3];
        ad = new int[3];
        k = 1;
        rev = 0;
        left = null;
        right = null;
    }
}