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) $ 的意义,有:
答案是 $ f(0) $,即:
到此时间复杂度为 $ O(2 ^ n \log m) $,可以解决 \(n \leq 20\) 的测试点。
将 $ g(i) $ 展开:
设 \(f_{i, j} = \sum\limits_{S = 0} ^ {2 ^ i - 1} (-1) ^ S S ^ j\),\(f_{0, 0} = 1\),当 \(i > 0\) 时有:
到此时间复杂度为 $ O(n m ^ 2) $,可以通过 \(n, m \leq 500\) 的测试点。
$ i \to i + 1 $ 的递推为复杂度贡献了一个 \(n\)。考虑倍增优化掉这个 \(n\),$ i \to 2i $。有:
一次卷积是 \(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;
}