题解 | G-Gentle Jena II

$x, y$ 绕原点逆时针旋转，可以通过矩阵变换描述

$\begin{pmatrix} \cos t & -\sin t \\ \sin t & \cos t \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$

如果绕特定的点 $(X, Y)$ 旋转角度 $t$ ，可以写成
先平移 $(-a, -b)$ ，再绕原点旋转，最后再平移 $(a, b)$ ，构造仿射变换如下

$\begin{pmatrix} 1 & 0 & X \\ 0 & 1 & Y \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} \cos t & - \sin t & 0 \\ \sin t & \cos t & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & -X \\ 0 & 1 & -Y \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$

另外注意矩阵变换是满足分配律的，比如对于当前星星 $\textbf{A}_i = \displaystyle \binom{x_i}{y_i}$ ，对于变换 $\textbf{P}$

$\textbf{P}(\textbf{A}_1 + \textbf{A}_2 + \cdots \textbf{A}_n) = \textbf{PA}_1 + \textbf{PA}_2 + \cdots \textbf{PA}_n = \textbf{A}'_1 + \textbf{A}'_2 + \cdots \textbf{A}'_n$

所以只需要用线段树维护 $sx = \sum x, \ sy = \sum y$ ，分别表示区间中所有星星 $x, y$ 坐标的和

构造仿射变换 $\textbf{P}$

初始化，对于每一个星星 $i$ ， $sx = x_i, sy = y_i$ ，建立线段树
对于操作 $1$ ，即执行仿射变换 $\textbf{P}$ ，只需要 $\textbf{P}\cdot (sx, sy)^{T}$ ，难点在于 $\text{push}$ 和 $\text{pull}$ 怎么写，以及懒标记处理

$(sx', sy')^{T} \leftarrow \textbf{P}\cdot (sx, sy)^{T}$
每次修改，难点在于 $\text{lazy}$ 如何处理 $\textbf{lazy}$ 初始化为单位矩阵 $\textbf{I}$ ，每一次对线段树节点 $p$ 执行变换 $\textbf{C}$ 时 $\textbf{C} \cdot (t_p.sx, t_p.sy)^{T}$ 执行矩阵乘法，并且下传延迟标记
递归到的每一个子区间都被修改了，后面的修改是基于前面修改基础上的
对于子区间，执行 $t(p \ll 1).\textbf{lazy} \leftarrow \textbf{C} \cdot t(p \ll 1).\textbf{lazy}$ ，右子树同理 $\text{pull}$ 操作只需要执行， $t(p).sx = t(p \ll 1).sx + t(p\ll 1 \mid 1).sx$
对于操作 $2$ 的问询，只需要注意每次递归查询时候，下传延迟标记，最后找到表示区间 $[li, ri]$ 的节点 $u$
$t(u).sx, t(u).sy$ 就是答案，注意在修改操作中更新 $sx, sy$ 需要取 $\text{mod}$

坑点提示

$\sum \left(\textbf{PA}_i \right) = \textbf{P} \left(\sum \textbf{A}_i \right)$

所以维护的矩阵变换应该是

$\textbf{P} \cdot \begin{pmatrix} sx \\ sy \\ \text{len}(p) \end{pmatrix}$

其中 $\text{len}(p)$ 表示线段树 $p$ 节点的区间长度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class t>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class t>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class t>
bool lexSmaller(vector<t> a, vector<t> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1e5 + 500;
const int mod = 998244353;
int n, m;
typedef vector<vector<ll> > Matrix;
Matrix I(3, vector<ll>(3, 0));

void init() {
    for (int i = 0; i < 3; i++) I[i][i] = 1;
}

struct Point {
    int x, y;
} a[maxn];


Matrix trans(const Matrix &A, const Matrix &B) {
    int _n = A.size(), _m = B[0].size();
    Matrix res(_n, vector<ll> (_m, 0));

    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < _m; j++)
            for (int k = 0; k < (int)A[0].size(); k++)
                res[i][j] = res[i][j] + A[i][k] * B[k][j];
    }
    return res;
}

Matrix mul(const Matrix &A, const Matrix &B) {
    int _n = A.size(), _m = B[0].size();
    Matrix res(_n, vector<ll> (_m, 0));

    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < _m; j++)
            for (int k = 0; k < (int)A[0].size(); k++)
                res[i][j] = (res[i][j] + A[i][k] * B[k][j] + mod) % mod;
    }
    return res;
}

Matrix get_matrix(int X, int Y) {
    Matrix A(3, vector<ll>(3, 0));
    for (int i = 0; i < 3; i++) A[i][i] = 1;
    A[0][2] = X, A[1][2] = Y;

    Matrix B(3, vector<ll>(3, 0));
    B[0][1] = -1, B[1][0] = 1, B[2][2] = 1;

    Matrix C(3, vector<ll>(3, 0));
    for (int i = 0; i < 3; i++) C[i][i] = 1;
    C[0][2] = -X, C[1][2] = -Y;

    Matrix res = A;
    res = trans(res, B);
    res = trans(res, C);
    return res;
}


namespace segTree {
    struct node {
        int l, r, tag;
        ll sx, sy;
        Matrix lazy;
    } t[maxn << 2];

    void pull(int p) {
        t[p].sx = (t[p<<1].sx + t[p<<1|1].sx + mod) % mod;
        t[p].sy = (t[p<<1].sy + t[p<<1|1].sy + mod) % mod;
    }

    void apply(int p, const Matrix& C) {
        Matrix cur(3, vector<ll>(1, 0));
        cur[0][0] = t[p].sx, cur[1][0] = t[p].sy, cur[2][0] = t[p].r-t[p].l+1;
        Matrix nxt = trans(C, cur);

        t[p].sx = nxt[0][0], t[p].sy = nxt[1][0];
    }

    void push(int p) {
        if (!t[p].tag) return;
        if (t[p].l == t[p].r) return;

        t[p].tag = 0;
        t[p<<1].tag = t[p<<1|1].tag = 1;

        Matrix C = t[p].lazy;
        t[p<<1].lazy = trans(C, t[p<<1].lazy);
        t[p<<1|1].lazy = trans(C, t[p<<1|1].lazy);
        t[p].lazy = I;

        apply(p<<1, C), apply(p<<1|1, C);
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        t[p].lazy = I;
        if (l >= r) {
            t[p].sx = a[l].x, t[p].sy = a[l].y;
            return;
        }
        int mid = (l+r) >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);

        pull(p);
    }

    void change(int p, const int l, const int r, const Matrix &P) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].tag = 1;
            apply(p, P);
            t[p].lazy = trans(P, t[p].lazy);
            return;
        }

        push(p);
        t[p].sx = t[p].sy = 0;
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p<<1, l, r, P);
        if (r > mid) change(p<<1|1, l, r, P);

        pull(p);
    }

    ll query(int p, const int l, const int r, bool fl) {
        if (l <= t[p].l && t[p].r <= r) {
            if (fl == 0) return (t[p].sx + mod) % mod;
            else return (t[p].sy + mod) % mod;
        }
        if (fl == 0) push(p);

        ll ans = 0;
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) ans = (ans + query(p<<1, l, r, fl) + mod) % mod;
        if (r > mid) ans = (ans + query(p<<1|1, l, r, fl) + mod) % mod;

        return ans;
    }
}


int main() {
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    init();

    using namespace segTree;
    // get data
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    build(1, 1, n);

    // get change
    while (m--) {
        int op, li, ri;
        scanf("%d%d%d", &op, &li, &ri);
        //debug(op), debug(li), debug(ri);
        if (op == 1) {
            int X, Y;
            scanf("%d%d", &X, &Y);
            Matrix P = get_matrix(X, Y);
            //dbg(P);

            change(1, li, ri, P);
        }
        if (op == 2) {
            ll sumx = query(1, li, ri, 0);
            ll sumy = query(1, li, ri, 1);
            //debug(sumy);
            sumx = (sumx + mod) % mod, sumy = (sumy + mod) % mod;
            ll ans = (sumx * sumy + mod) % mod;
            printf("%lld\n", ans);
        }
    }
}