526互联

20231109模拟赛

发布时间 2023-11-10 21:59:22作者: zzxLLL

2023.11.09 模拟赛

T1

给定整数 \(n, m, V\) 以及四个整数列 \(at_{1 \sim n}, hp_{1 \sim n}, At_{1 \sim m}, Hp_{1 \sim m}\)。其中 \(Hp, At\) 均为非降序列，且四个序列中除 \(Hp\) 外元素的值均不超过 \(V\)。

对于 \(1 \leq q \leq m\)，求最小的 \(k \leq n\)，满足 \(\sum\limits_{i = 1} ^ k \left\lceil \frac{hp_i}{At_q} \right\rceil att_i \ge Hp_q\)。如果 \(k\) 不存在则输出 -1.

\(1 \le n, m \le 3 \times 10 ^ 5, 1 \le at_i, hp_i, At_i \le V \le 3 \times 10 ^ 5, 1 \le Hp_i \le 10^9\)。

根据柿子，\(\left\lceil \frac{hp_i}{At_q} \right\rceil att_i\) 的值会不断减小，而 \(Hp_q\) 的值会不断增大。故 \(k\) 不断增大。

考虑维护当前的 \(k\) 以及当前的前缀和。当 \(q \gets q + 1\) 时，会影响到一些 \(\left\lceil \frac{hp_i}{At_q} \right\rceil\)。但是对于每个 \(hp_i\)，\(x\) 为正整数时 \(\left\lceil \frac{hp_i}{x} \right\rceil\) 能取到的值的个数是 \(O(\sqrt{V})\) 的。只有在 \(\left\lceil \frac{hp_i}{At_q} \right\rceil\) 变化时才会造成影响，所以总的影响次数是 \(O(n \sqrt{V})\) 的，暴力修改即可。

对于一个 \(a\) 计算 \(\left\lceil \frac{a}{x} \right\rceil\) 取值个数时，令 \(m = \left\lceil \frac{a}{x} \right\rceil\)，那么有 \(xm \ge a, x(m - 1) < a\)，即 \(\frac{a}{m} \le x < \frac{a}{m - 1}\) 的 \(x\) 都有 \(\left\lceil \frac{a}{x} \right\rceil = m\)。根据整数的离散性，条件等价于 \(\left\lceil \frac{a}{m} \right\rceil \le x \le \left\lfloor \frac{a - 1}{m - 1} \right\rfloor\)。令 \(x \gets \left\lfloor \frac{a - 1}{m - 1} \right\rfloor + 1\) 就可以计算出新的 \(m\)。重复上述过程直到 \(m = 1\) 即可得到 \(\left\lceil \frac{a}{x} \right\rceil\) 的全部取值。

时间复杂度 \(O(n \sqrt{V} + m)\)，期望得分 100，实际得分 35（

实测影响次数超过 \(3 \times 10 ^ 8\)。

\(O(n \log ^ 2 n)\) 的以后补。

Code of T1 
#pragma GCC optimize("Ofast")
#include <ctime>
#include <cstdio>
#include <vector>
#include <iostream>
const int M = 3e5 + 10;

#define CEIL(x, y) (x % y == 0 ? x / y : (x / y + 1))

inline int read() {
    char ch = getchar();
    int x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int n, m, V;
int at[M], hp[M], At[M], Hp[M], lst[M];
std::vector<int> vec[M], qwq[M];
long long val[M];

int main() {
    double st = clock();
    freopen("france.in", "r", stdin);
    freopen("france.out", "w", stdout);
    n = read(), m = read(), V = read();
    for (int i = 1; i <= n; i++) at[i] = read(), hp[i] = read();
    for (int i = 1; i <= m; i++) At[i] = read(), Hp[i] = read();
    At[0] = 1;

    for (int i = 1; i <= n; i++) {
        int x = hp[i], cur = hp[i];
        if (!qwq[x].empty()) {
            for (int t : qwq[x]) vec[t].push_back(i);
            continue;
        }
        while (true) {
            qwq[x].push_back(cur);
            vec[CEIL(x, cur)].push_back(i);
            if (cur == 1) break;
            int tmp = (x - 1) / (cur - 1) + 1;
            cur = CEIL(x, tmp);
        }
    }

    for (int i = 1; i <= n; i++) val[i] = at[i] * 1ll * hp[i], lst[i] = 1;

    int cur = 0;
    long long sum = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = At[i - 1] + 1; j <= At[i]; j++) {
            for (int x : vec[j]) {
                if (x <= cur) sum -= val[x];
                int dlt = CEIL(hp[x], lst[x]) - CEIL(hp[x], j);
                lst[x] = j, val[x] -= 1ll * dlt * at[x];
                if (x <= cur) sum += val[x];
            }
        }
        while (cur < n && sum + val[cur + 1] < Hp[i]) sum += val[++cur];
        if (cur == n) printf("-1\n");
        else printf("%d\n", cur + 1);
    }
    double ed = clock();
    std::cerr << (int)(ed - st) << '\n';
    return 0;
}

T2

一颗深度为 \(n\) 的满二叉树（根节点深度为 \(1\)），第 \(i\) 层大小为 \(2 ^ {i - 1}\)。每次可以标记一个节点，一个节点可以重复被标记。

问标记 \(m\) 次后，每一层都至少存在一个节点被标记的方案数。

对于 \(15\%\) 的数据 \(n \leq 20, m = 1145141919\)。

对于剩余数据 \(n, m \leq 2000\)。

套路地二项式反演。

设 $ f(i) $ 为恰好 \(i\) 层没有放的方案数，$ g(i) $ 为钦定 \(i\) 层没有放的方案数。显然有：

\[g(i) = \sum\limits_{j = i} ^ n \dbinom{j}{i} f(j) \]

二项式反演得到：

\[f(i) = \sum\limits_{j = i} ^ n (-1) ^ {j - i} \dbinom{j}{i} g(j) \]

根据 $ g(i) $ 的意义，有：

\[g(i) = \sum\limits_{|T| = i} (2 ^ n - 1 - T) ^ m \]

答案是 $ f(0) $，即：

\[\operatorname{ans} = \sum\limits_{i = 0} ^ n (-1) ^ i g(i) \]

到此时间复杂度为 $ O(2 ^ n \log m) $，可以解决 \(n \leq 20\) 的测试点。

将 $ g(i) $ 展开：

\[\begin{aligned} \operatorname{ans} &= \sum\limits_{i = 0} ^ n (-1) ^ i \sum\limits_{|T| = i} (2 ^ n - 1 - T) ^ m \\&= \sum\limits_{T = 0} ^ {2 ^ n - 1} (-1) ^ {|T|} (2 ^ n - 1 - T) ^ m \\&= \sum\limits_{S = 0} ^ {2 ^ n - 1} (-1) ^ {n - |S|} S ^ m \\&= (-1) ^ n \sum\limits_{S = 0} ^ {2 ^ n - 1} (-1) ^ {|S|} S ^ m \end{aligned} \]

设 \(f_{i, j} = \sum\limits_{S = 0} ^ {2 ^ i - 1} (-1) ^ S S ^ j\)，\(f_{0, 0} = 1\)，当 \(i > 0\) 时有：

\[\begin{aligned} f_{i, j} &= \sum\limits_{S = 0} ^ {2 ^ i - 1} (-1) ^ {|S|} S ^ j \\&= \sum\limits_{S = 0} ^ {2 ^ {i - 1} - 1} (-1) ^ {|S|} S ^ j + \sum\limits_{S = 0} ^ {2 ^ {i - 1} - 1} (-1) ^ {|S + 2 ^ {i - 1}|} (S + 2 ^ {i - 1}) ^ j \\&= f_{i - 1, j} - \sum\limits_{S = 0} ^ {2 ^ {i - 1} - 1} (-1) ^ {|S|} (S + 2 ^ {i - 1}) ^ j \\&= f_{i - 1, j} - \sum\limits_{S = 0} ^ {2 ^ {i - 1} - 1} (-1) ^ {|S|} \sum\limits_{x = 0} ^ j \dbinom{j}{x} 2 ^ {x (i - 1)} S ^ {j - x} \\&= f_{i - 1, j} - \sum\limits_{x = 0} ^ j \dbinom{j}{x} 2 ^ {x (i - 1)} f_{i - 1, j - x} \end{aligned} \]

到此时间复杂度为 $ O(n m ^ 2) $，可以通过 \(n, m \leq 500\) 的测试点。

$ i \to i + 1 $ 的递推为复杂度贡献了一个 \(n\)。考虑倍增优化掉这个 \(n\)，$ i \to 2i $。有：

\[\begin{aligned} f_{p + q, j} &= \sum\limits_{S = 0} ^ {2 ^ {p + q} - 1} (-1) ^ {|S|} S ^ j \\&= \sum\limits_{S_0 = 0} ^ {2 ^ p - 1} \sum\limits_{S_1 = 0} ^ {2 ^ q - 1} (-1) ^ {|S_0| + |S_1|} (2 ^ {q} S_0 + S_1) ^ j \\&= \sum\limits_{S_0 = 0} ^ {2 ^ p - 1} \sum\limits_{S_1 = 0} ^ {2 ^ q - 1} (-1) ^ {|S_0|} (-1) ^ {|S_1|} \sum\limits_{x = 0} ^ j \dbinom{j}{x} 2^{qx} S_0 ^ x S_1 ^ {j - x} \\&= \sum\limits_{x = 0} ^ j \dbinom{j}{x} 2 ^ {qx} \sum\limits_{S_0 = 0} ^ {2 ^ p - 1} (-1) ^ {|S_0|} S_0 ^ x \sum\limits_{S_1 = 0} ^ {2 ^ q - 1} (-1) ^ {|S_1|} S_1 ^ {j - x} \\&= \sum\limits_{x = 0} ^ j \dbinom{j}{x} 2 ^ {qx} f_{p, x} f_{q, j - x} \end{aligned} \]

一次卷积是 \(O(m ^ 2)\) 的。预处理出 \(f_{2 ^ k}\)，然后合并出 \(f_n\) 即可。时间复杂度 \(O(m ^ 2 \log n)\)。

Code of T2 
#pragma GCC optimize("Ofast")
#include <cstdio>
//#define int long long
const int M = 2333;
const int mod = 1e9 + 7;

int n, m;

inline int qpow(int b, int p) {
    int ans = 1;
    for (; p; p >>= 1) {
        if (p & 1) ans = 1ll * ans * b % mod;
        b = 1ll * b * b % mod;
    }
    return ans;
}

int fac[M], facinv[M], pw2[M * M];
inline void calc() {
    fac[0] = fac[1] = facinv[0] = facinv[1] = 1;
    for (int i = 2; i < M; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    for (int i = 2; i < M; i++) facinv[i] = 1ll * (mod - mod / i) * facinv[mod % i] % mod;
    for (int i = 2; i < M; i++) facinv[i] = 1ll * facinv[i - 1] * facinv[i] % mod;
    pw2[0] = 1;
    for (int i = 1; i < M * M; i++) pw2[i] = pw2[i - 1] * 2ll % mod;
}
inline int C(int x, int y) {
    if (x < y || x < 0 || y < 0) return 0;
    return 1ll * fac[x] * facinv[y] % mod * facinv[x - y] % mod;
}

namespace Sub1 {
    // n <= 20
    const int N = 1 << 20;
    int g[M], popcount[N];
    void main() {
        //m %= (mod - 1);
        popcount[0] = 0;
        for (int i = 1; i < N; i++)
            popcount[i] = popcount[i - (i & -i)] + 1;
        for (int S = 0; S < (1 << n); S++)
            (g[popcount[S]] += qpow((1 << n) - 1 - S, m)) %= mod;
        long long f0 = 0;
        for (int i = 0, f = 1; i <= n; i++, f = -f) {
            (f0 += 1ll * f * g[i] % mod * C(i, 0) % mod) %= mod;
            (f0 += mod) %= mod;
        }
        printf("%lld\n", f0);
    }
}

namespace Sub2 {
    int f[M][M];
    void main() {
        f[0][0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                for (int x = 0; x <= j; x++) {
                    (f[i][j] -= 1ll * pw2[(i - 1) * x] * C(j, x) % mod * f[i - 1][j - x] % mod) %= mod;
                    (f[i][j] += mod) %= mod;
                }
            }
        printf("%d\n", (n & 1) ? (mod - f[n][m]) % mod : f[n][m]);
    }
}

namespace Sub3 {
    int f[20][M], g[M], t0[M], t1[M], t2[M];
    int cur, len;

    void Merge(int* a, int p, int* b, int q, int* c) {
        for (int j = 0; j <= m; j++) t0[j] = a[j], t1[j] = b[j], t2[j] = 0;
        for (int j = 0; j <= m; j++)
            for (int x = 0; x <= j; x++)
                (t2[j] += 1ll * C(j, x) * pw2[q * x] % mod * t0[x] % mod * t1[j - x] % mod) %= mod;
        for (int j = 0; j <= m; j++) c[j] = t2[j];
    }

    void main() {
        int n0 = n;
        f[0][0] = 0, g[0] = 1;
        for (int j = 1; j <= m; j++) f[0][j] = mod - 1;
        for (int k = 1; (1 << k) <= n; k++)
            Merge(f[k - 1], 1 << (k - 1), f[k - 1], 1 << (k - 1), f[k]);
        for (; n; n >>= 1, cur++)
            if (n & 1) Merge(g, len, f[cur], 1 << cur, g), len += (1 << cur);
        printf("%d\n", (n0 & 1) ? (mod - g[m]) : g[m]);
    }
}

int main() {
    calc();
    freopen("glass.in", "r", stdin);
    freopen("glass.out", "w", stdout);
    scanf("%d%d", &n, &m);
    if (m == 1145141919) Sub1::main();
    else if (n <= 500 && m <= 500) Sub2::main();
    else Sub3::main();
    return 0;
}

T3

你有一个初始全为 \(+\infty\) 的实数列 \(a_{1 \sim n}\) 和一个实数 \(c \in \{0, 0.5, 1\}\)。

有 \(q\) 次操作，共四种：

1 l r x y：对所有 \(i \in [l, r]\)，\(a_i \gets \min(a_i, y + (x + i - l) ^ c)\)。

2 l r x y：对所有 \(i \in [l, r]\)，\(a_i \gets \min(a_i, y + (x + r - i) ^ c)\)。

3 t：将数列变成第 \(t\) 次操作后的状态。\(t = 0\) 时变成初始状态。

4 p：输出 \(a_p\)。若 \(a_p = +\infty\) 输出 Shik。

\(n, q \leq 10 ^ 5, c \in \{0, 0.5, 1\}\)。

保证 \(c = 1\) 时没有操作三，\(c = 0\) 时 \(x = 1, y = 0\)。

考场上根本没往李超树那边想，但是 \(c = 1\) 时是裸的李超树。

\(c = 0\) 时，如果点 \(x\) 被修改过那么 \(a_x = 1\)，否则 \(a_x = +\infty\)。用一颗树状数组可以快速维护一个点被操作一、二的区间覆盖了几次。但是有撤销操作，所以建出操作树，一遍 dfs 即可。

\(c = 0.5\) 时，即维护若干个函数图像 \(y = a + \sqrt{kx + b}\)。这类函数与一次函数有类似的性质，即如果两个这样的曲线 \(C_1, C_2\) 相交，那么交点以前 \(C_1\) 在 \(C_2\) 上方，交点以后 \(C_1\) 在 \(C_2\) 下方。只要满足这个性质的函数都可以用李超树维护。

但是有操作三，所以可持久化一下。时空复杂度为 \(O(n \log ^ 2 n)\)。

Code of T3 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
const int M = 1e5 + 10;
const int inf = 1e9 + 7;
const double Inf = 1e18;

bool st;

int n, q;
double c;

namespace _0 {
    struct BIT {
        int c[M];
        void add(int x, int v) {
            for (; x <= n; x += (x & -x)) c[x] += v;
        }
        int qry(int x) {
            int ret = 0;
            for (; x; x -= (x & -x)) ret += c[x];
            return ret;
        }
    }T;
    std::vector<int> g[M];

    struct Query {
        int op, l, r, x, y;
    }Q[M];
    int ans[M];

    void dfs(int u) {
        if (Q[u].op == 1 || Q[u].op == 2) {
            T.add(Q[u].l, 1), T.add(Q[u].r + 1, -1);
        }
        if (Q[u].op == 4) {
            int ret = T.qry(Q[u].x);
            ans[u] = ret ? 1 : inf;
        }
        for (int v : g[u]) dfs(v);
        if (Q[u].op == 1 || Q[u].op == 2) {
            T.add(Q[u].l, -1), T.add(Q[u].r + 1, 1);
        }
    }

    void main() {
        for (int i = 1; i <= q; i++) {
            scanf("%d", &Q[i].op);
            if (Q[i].op == 1 || Q[i].op == 2)
                scanf("%d%d%d%d", &Q[i].l, &Q[i].r, &Q[i].x, &Q[i].y);
            if (Q[i].op == 3)
                scanf("%d", &Q[i].x), g[Q[i].x].push_back(i);
            else
                g[i - 1].push_back(i);
            if (Q[i].op == 4)
                scanf("%d", &Q[i].x);
        }
        dfs(0);
        for (int i = 1; i <= q; i++)
            if (Q[i].op == 4) printf(ans[i] == inf ? "Shik\n" : "1.000000\n");
    }
}

namespace _1 {
    int cntline;
    struct Func { int k, b; }L[M];
    int calc(int id, int x) {
        return L[id].k * x + L[id].b;
    }

    struct node { int l, r, id; } tr[M << 2];
    void Insert(int k, int l, int r, int L, int R, int id) {
        int mid = (l + r) >> 1;
        if (L <= l && r <= R) {
            if (calc(tr[k].id, mid) > calc(id, mid)) std::swap(id, tr[k].id);
            if (l == r) return;
            if (calc(tr[k].id, l) > calc(id, l)) Insert(k << 1, l, mid, L, R, id);
            if (calc(tr[k].id, r) > calc(id, r)) Insert(k << 1 | 1, mid + 1, r, L, R, id);
            return;
        }
        if (L <= mid) Insert(k << 1, l, mid, L, R, id);
        if (R > mid)  Insert(k << 1 | 1, mid + 1, r, L, R, id);
    }
    int Query(int k, int l, int r, int x) {
        if (l == r) return calc(tr[k].id, x);
        int mid = (l + r) >> 1;
        if (x <= mid) return std::min(calc(tr[k].id, x), Query(k << 1, l, mid, x));
        else return std::min(calc(tr[k].id, x), Query(k << 1 | 1, mid + 1, r, x));
    }

    void main() {
        L[0] = { 0, inf };
        for (int op, l, r, x, y; q; q--) {
            scanf("%d", &op);
            if (op == 1) {
                scanf("%d%d%d%d", &l, &r, &x, &y);
                L[++cntline] = { 1, x + y - l };
                Insert(1, 1, n, l, r, cntline);
            }
            if (op == 2) {
                scanf("%d%d%d%d", &l, &r, &x, &y);
                L[++cntline] = { -1, x + y + r };
                Insert(1, 1, n, l, r, cntline);
            }
            if (op == 4) {
                scanf("%d", &x);
                int qwq = Query(1, 1, n, x);
                if (qwq == inf) printf("Shik\n");
                else printf("%d.000000\n", qwq);
            }
        }
    }
}

namespace 零点五 {
    int cntcve;
    struct Func {
        double a, k, b;
        // a + sqrt(kx + b)
    } C[M];
    double calc(int id, int x) {
        return C[id].a + sqrt(C[id].k * x + C[id].b);
    }

    int rt[M], tot;
    struct Node { int lc, rc, id; } tr[M * 18 * 18];
    void Insert(int& k, int p, int l, int r, int L, int R, int id) {
        tr[k = ++tot] = tr[p];
        int mid = (l + r) >> 1;
        if (L <= l && r <= R) {
            if (calc(tr[k].id, mid) > calc(id, mid)) std::swap(tr[k].id, id);
            if (l == r) return;
            if (calc(tr[k].id, l) > calc(id, l)) Insert(tr[k].lc, tr[p].lc, l, mid, L, R, id);
            if (calc(tr[k].id, r) > calc(id, r)) Insert(tr[k].rc, tr[p].rc, mid + 1, r, L, R, id);
            return;
        }
        if (L <= mid) Insert(tr[k].lc, tr[p].lc, l, mid, L, R, id);
        if (R > mid)  Insert(tr[k].rc, tr[p].rc, mid + 1, r, L, R, id);
    }
    double Query(int k, int l, int r, int x) {
        if (!k) return Inf;
        if (l == r) return calc(tr[k].id, x);
        int mid = (l + r) >> 1;
        if (x <= mid) return std::min(calc(tr[k].id, x), Query(tr[k].lc, l, mid, x));
        else return std::min(calc(tr[k].id, x), Query(tr[k].rc, mid + 1, r, x));
    }

    void main() {
        C[0] = { Inf, 0, 0 };
        for (int i = 1, op, l, r, x, y; i <= q; i++) {
            scanf("%d", &op);
            if (op == 1) {
                scanf("%d%d%d%d", &l, &r, &x, &y);
                C[++cntcve] = { 1. * y, 1., 1. * (x - l) };
                Insert(rt[i], rt[i - 1], 1, n, l, r, cntcve);
            }
            if (op == 2) {
                scanf("%d%d%d%d", &l, &r, &x, &y);
                C[++cntcve] = { 1. * y, -1., 1. * (x + r) };
                Insert(rt[i], rt[i - 1], 1, n, l, r, cntcve);
            }
            if (op == 3) {
                scanf("%d", &x);
                rt[i] = rt[x];
            }
            if (op == 4) {
                rt[i] = rt[i - 1];
                scanf("%d", &x);
                double qwq = Query(rt[i], 1, n, x);
                if (qwq == Inf) printf("Shik\n");
                else printf("%.6f\n", qwq);
            }
        }
    }
}

bool ed;

int main() {
    std::cerr << (int)(&st - &ed) / 1024 / 1024 << '\n';
    freopen("snow.in", "r", stdin);
    freopen("snow.out", "w", stdout);
    scanf("%d%lf%d", &n, &c, &q);
    if (c == 0) _0::main();
    if (c == 1) _1::main();
    if (c == 0.5) 零点五::main();
    return 0;
}

T4

给定一个长度为 \(n\) 的正整数排列 \(a_{1 \sim n}\)，初始时满足 \(a_i = i\)。

对这个序列进行 \(m\) 次操作，每次操作形如：

0 l r：将现在的 \(a_{l \sim r}\) 移出 \(a\)，然后插入到 \(a\) 前端。

1 l r：将 \(a_{l \sim r}\) 前后翻转。

称一个正整数串是摇聚的，设其值域为 \([l, r]\)，当且仅当 \(l = 1\) 且 \([l, r]\) 内的正整数都在串中出现。

\(m\) 次操作后，问有多少个摇聚的序列满足其后缀数组为 \(a\)。

\(n \leq 10 ^ 9, m \leq 10 ^ 5\)。

设最终的后缀数组为 \(p\)，后缀 \(i\) 的排名为 \(rk_i\)，有 \(rk_{p_i} = i\)。

一个摇聚的整数串 \(S\) 的后缀数组为 \(p\) 时，必然有 \(S_{p_1} = 1\)，且 \(S_{p_i} < sum_{p_{i + 1}}\)。

考虑什么时候能取等号。当 \(S_{p_i} = S_{p_{i + 1}}\) 时，那么单看这两个字符无法比较出字典序大小，所以必须要满足 \(rk_{p_i + 1} < rk_{p_{i + 1} + 1}\)。当 \(p_i = n\) 或者 \(rk_{p_i + 1} > rk_{p_{i + 1} + 1}\) 时显然只能取小于号。

但是摇聚的整数串还要满足值域连续，所以在 \(S_{p_i}\) 确定的情况下，如果取小于号，有 \(S_{p_i} + 1 = S_{p_{i + 1}}\)。那么能取小于号时，\(S_{p_{i + 1}}\) 就有两种选择。如果只能取等号那么 \(S_{p_{i + 1}}\) 只有一种选择。设有两种选择的位置有 \(t\) 个，答案就是 \(2 ^ t\)。结合上面的结论，\(t\) 就是满足 \(rk_{p_i + 1} < rk_{p_{i + 1} + 1}\) 的 \(i\) 的个数。

然后考虑怎么维护这个序列。当 \(n\) 较小时直接 FHQtreap 维护即可。但是 \(n\) 非常大，如果数据随机可以考虑使用珂朵莉树。但是数据并不随机，所以可以用 FHQtreap 来模拟珂朵莉树的操作。这样数列被分为很多段，每段都是公差为 \(\pm 1\) 的等差数列。对每一段内分类讨论一下：

  • 公差为 \(1\) 时，\(S_{sa_l} \le S_{sa_{l + 1}} \le \cdots \le S_{sa_{r - 2}} \le S_{sa_{r - 1}} \color{red}{<} S_{sa_r}\)。对 \(t\) 的贡献为 \(len - 2\)。

  • 公差为 \(-1\) 时，\(S_{sa_l} \ge S_{sa_{l + 1}} \ge \cdots \ge S_{sa_{r - 2}} \ge S_{sa_{r - 1}} \color{blue}{\ge} S_{sa_r}\)。对 \(t\) 的贡献为 \(len - 1\)。

而对于两段的分界，像上面那样分类讨论即可。时间复杂度 \(O(n \log n)\)。

Code of T4 
#pragma GCC optimize("Ofast")
#include <set>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
const int M = 1e5 + 10;
const int mod = 1e9 + 7;

int n, m;

inline int rng() {
    static unsigned long long zzx = 23333;
    return (zzx *= 2333) % 2147483647;
}

struct Node {
    int lc, rc, len, sum, pri, v, L, R;
    bool rev;
}tr[M << 2];
int rt, tot;

inline int Newnode(int l, int r, int v) {
    if (l > r) return 0;
    int cur = ++tot;
    tr[cur].len = tr[cur].sum = r - l + 1;
    tr[cur].v = v, tr[cur].pri = rng();
    tr[cur].L = l, tr[cur].R = r;
    return cur;
}

inline void Tag(int k) {
    tr[k].rev ^= 1, tr[k].v ^= 1;
    std::swap(tr[k].lc, tr[k].rc);
}
inline void Pushdown(int k) {
    if (tr[k].rev)
        Tag(tr[k].lc), Tag(tr[k].rc), tr[k].rev = false;
}
inline void Pushup(int k) {
    tr[k].sum = tr[tr[k].lc].sum + tr[k].len + tr[tr[k].rc].sum;
}

inline void Split0(int k, int p, int& x, int& y) {
    if (!k) return void(x = y = 0);
    Pushdown(k);
    if (tr[tr[k].lc].sum + tr[k].len < p) {
        x = k;
        Split0(tr[k].rc, p - tr[tr[k].lc].sum - tr[k].len, tr[k].rc, y);
    } else {
        y = k;
        Split0(tr[k].lc, p, x, tr[k].lc);
    }
    Pushup(k);
}
inline void Split1(int k, int p, int& x, int& y) {
    if (!k) return void(x = y = 0);
    Pushdown(k);
    if (tr[tr[k].rc].sum + tr[k].len < p) {
        y = k;
        Split1(tr[k].lc, p - tr[tr[k].rc].sum - tr[k].len, x, tr[k].lc);
    } else {
        x = k;
        Split1(tr[k].rc, p, tr[k].rc, y);
    }
    Pushup(k);
}
inline int Merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].pri > tr[y].pri) {
        Pushdown(x);
        tr[x].rc = Merge(tr[x].rc, y);
        Pushup(x);
        return x;
    } else {
        Pushdown(y);
        tr[y].lc = Merge(x, tr[y].lc);
        Pushup(y);
        return y;
    }
}

inline int getLeft(int x) {
    while (tr[x].lc) Pushdown(x), x = tr[x].lc;
    return x;
}
inline int getRight(int x) {
    while (tr[x].rc) Pushdown(x), x = tr[x].rc;
    return x;
}

int A, B, C;
inline void Split(int l, int r) {
    A = B = C = 0;
    Split0(rt, l, A, B), Split1(B, n - r + 1, B, C);

    int pl = getLeft(B), pr = getRight(B);
    int L = 1 + tr[A].sum, R = n - tr[C].sum;
    int lenL = l - L, lenR = R - r;
    if (pl == pr) {
        if (lenL) {
            if (!tr[B].v)
                A = Merge(A, Newnode(tr[B].L, tr[B].L + lenL - 1, tr[B].v));
            else
                A = Merge(A, Newnode(tr[B].R - lenL + 1, tr[B].R, tr[B].v));
        }
        if (lenR) {
            if (!tr[B].v)
                C = Merge(Newnode(tr[B].R - lenR + 1, tr[B].R, tr[B].v), C);
            else
                C = Merge(Newnode(tr[B].L, tr[B].L + lenR - 1, tr[B].v), C);
        }
        if (!tr[B].v)
            B = Newnode(tr[B].L + lenL, tr[B].R - lenR, tr[B].v);
        else
            B = Newnode(tr[B].L + lenR, tr[B].R - lenL, tr[B].v);
    } else {
        if (lenL) {
            Split0(B, tr[pl].len + 1, pl, B);
            if (!tr[pl].v) {
                A = Merge(A, Newnode(tr[pl].L, tr[pl].L + lenL - 1, tr[pl].v));
                B = Merge(Newnode(tr[pl].L + lenL, tr[pl].R, tr[pl].v), B);
            } else {
                A = Merge(A, Newnode(tr[pl].R - lenL + 1, tr[pl].R, tr[pl].v));
                B = Merge(Newnode(tr[pl].L, tr[pl].R - lenL, tr[pl].v), B);
            }
        }
        if (lenR) {
            Split1(B, tr[pr].len + 1, B, pr);
            if (!tr[pr].v) {
                C = Merge(Newnode(tr[pr].R - lenR + 1, tr[pr].R, tr[pr].v), C);
                B = Merge(B, Newnode(tr[pr].L, tr[pr].R - lenR, tr[pr].v));
            } else {
                C = Merge(Newnode(tr[pr].L, tr[pr].L + lenR - 1, tr[pr].v), C);
                B = Merge(B, Newnode(tr[pr].L + lenR, tr[pr].R, tr[pr].v));
            }
        }
    }
}

inline void Reverse(int l, int r) {
    Split(l, r), Tag(B), rt = Merge(A, Merge(B, C));
}
inline void Move(int l, int r) {
    Split(l, r), rt = Merge(B, Merge(A, C));
}

int sum;
struct Range {
    int l, r, v, pre;
    inline bool operator < (const Range& o) const {
        return r < o.r;
    }
};
std::vector<Range> sa;
inline void dfs(int u) {
    Pushdown(u);
    if (tr[u].lc) dfs(tr[u].lc);
    sa.push_back({ tr[u].L, tr[u].R, tr[u].v, sum });
    sum += tr[u].len;
    if (tr[u].rc) dfs(tr[u].rc);
}

std::set<Range> rg;
inline int getrk(int x) {
    // rank of Suffix(x)
    if (x > n) return 0;
    Range R = *rg.lower_bound({ x, x, 0, 0 });
    if (!R.v) return R.pre + (x - R.l + 1);
    else return R.pre + (R.r - x + 1);
}

int main() {
    freopen("array.in", "r", stdin);
    freopen("array.out", "w", stdout);
    scanf("%d%d", &n, &m);
    rt = Newnode(1, n, 0);
    for (int op, l, r; m; m--) {
        scanf("%d%d%d", &op, &l, &r);
        if (op == 0) Move(l, r);
        if (op == 1) Reverse(l, r);
    }
    dfs(rt);
    for (Range qwq : sa) rg.insert(qwq);

    int tot = 0;
    for (int i = 0; i < sa.size(); i++) {
        tot += std::max(0, sa[i].r - sa[i].l - 2);
        if (sa[i].r - sa[i].l + 1 >= 2) {
            int x = (!sa[i].v) ? sa[i].l : sa[i].r;
            int y = (!sa[i].v) ? (sa[i].l + 1) : (sa[i].r - 1);
            tot += getrk(x + 1) < getrk(y + 1);
        }
        if (sa[i].r - sa[i].l + 1 >= 3) {
            int x = (!sa[i].v) ? (sa[i].r - 1) : (sa[i].l + 1);
            int y = (!sa[i].v) ? sa[i].r : sa[i].l;
            tot += getrk(x + 1) < getrk(y + 1);
        }
        if (i < sa.size() - 1) {
            int x = (!sa[i].v) ? sa[i].r : sa[i].l;
            int y = (!sa[i + 1].v) ? sa[i + 1].l : sa[i + 1].r;
            tot += getrk(x + 1) < getrk(y + 1);
        }
    }

    int ans = 1, base = 2;
    for (; tot; tot >>= 1) {
        if (tot & 1) ans = 1ll * ans * base % mod;
        base = 1ll * base * base % mod;
    }
    printf("%d\n", ans);
    return 0;
}