一开始，你有序列[1,n][1, n]的一棵线段树，有mm次操作/询问

  • 1 l r：在操作队列里加上l, r这个操作。
  • 2：询问当前操作队列，每个操作是否执行，总共2k2^{k}（kk为操作数）种方案中， 线段树上tag为11 的节点个数的总和。答案对998244353998244353取模

在线段树上的一次操作[l,r][l, r]，就是把线段树上所有被[l,r][l, r]完全覆盖的极大区间的tag设为11

n,m≤105n, m\le 10^5

LOJ 3043

Solution

4.5UPD

一个更妙，更简洁的概率做法：这里

考虑在线段树上模拟这个过程，统计每个节点在2k2^k种方案中，tag为11的次数分别是多少

显然每次只需要考虑新加进来一个操作后，对当前节点答案产生的影响

不难注意到，对于第kk个操作[x,y][x, y]，造成不同影响的节点[l,r][l, r]一共有44类：

19-4-2-1

  1. x≤l,r≤yx\le l, r\le y，且该结点被访问过

    也就是线段树访问到的最底层的那一类节点

    无论之前的操作是什么样，这一次它的tag一定为11，即答案加上2k−12^{k-1}

  2. 除第11类之外，剩下被访问过的节点

    这些节点的tag都会在这一次操作中被下放，即答案没变

  3. 第22类节点除了第11类节点之外的儿子

    这些节点不会被访问，但是标记会被下放到这里。那么这些点的答案会加上从根节点到该点的路径上，存在tag=1的节点的方案数，设它为fif_i，先不管怎么求

  4. 剩下的所有节点

    无论当前操作执不执行都对它们没影响。所以它们的答案要乘22

123类节点可以通过线段树上遍历打标记去维护，但显然第44类节点的答案不能直接遍历去算

可以先把答案减掉当前操作123类节点之前对答案的贡献，把答案乘22，再加上当前操作123类节点对答案的贡献

然后考虑如何求 ，依旧分类讨论

  • 所有满足x≤l,r≤yx\le l, r\le y的节点（不要求被访问）。也就是11类节点以及它们的所有后代

    显然这些节点当前到根的路径上存在tag=1的节点

    这些点的ff 加上2k−12^{k-1}

  • 上面的第 类节点

    显然所有根到它路径上的tag在这一次之后都被下放，ff值不变

  • 其他所有节点

    这次操作对它们没有影响，ff值乘

求 的部分依旧是线段树上打加法乘法标记来维护

代码也许(?)比较清晰

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 998244353;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }
inline void Mul (int &a, int b) { a = (LL) a * b % Mod; }

int N, M, ans;

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls root << 1
#define rs root << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r

	struct info
	{
		int val, val_mul;
		int f, f_add, f_mul;
	} node[Maxn << 2];

	inline void build (int root, int l, int r)
	{
		node[root].val_mul = node[root].f_mul = 1;
		if (l == r) return ;
		else build (lson), build (rson);
	}

	inline void push_val_mul (int root, int x)
	{
		Mul (node[root].val, x);
		Mul (node[root].val_mul, x);
	}

	inline void push_f_add (int root, int x)
	{
		Add (node[root].f, x);
		Add (node[root].f_add, x);
	}

	inline void push_f_mul (int root, int x)
	{
		Mul (node[root].f, x);
		Mul (node[root].f_mul, x);
		Mul (node[root].f_add, x);
	}

	inline void push_down (int root)
	{
		if (node[root].val_mul != 1)
		{
			push_val_mul (ls, node[root].val_mul),
			push_val_mul (rs, node[root].val_mul);
			node[root].val_mul = 1;
		}

		if (node[root].f_mul != 1)
		{
			push_f_mul (ls, node[root].f_mul),
			push_f_mul (rs, node[root].f_mul);
			node[root].f_mul = 1;
		}

		if (node[root].f_add)
		{
			push_f_add (ls, node[root].f_add),
			push_f_add (rs, node[root].f_add);
			node[root].f_add = 0;
		}
	}

	inline int update (int root, int l, int r, int x, int y, int pow2)
	{
		if (r < x || y < l)
		{
			Add (ans, Mod - node[root].val);
			
			Add (node[root].val, node[root].f);
			push_f_mul (root, 2);
			Mul (node[root].val_mul, 2);

			return node[root].val;
		}

		if (x <= l && r <= y)
		{
			Add (ans, Mod - node[root].val);

			Add (node[root].val, pow2);
			push_f_add (root, pow2);
			Mul (node[root].val_mul, 2);

			return node[root].val;
		}

		push_down (root);
		int sum = node[root].val; Add (ans, Mod - node[root].val);
		
		Add (sum, update (lson, x, y, pow2));
		Add (sum, update (rson, x, y, pow2));
		
		return sum;
	}

#undef mid 
#undef ls 
#undef rs
#undef lson
#undef rson
}

inline void Solve ()
{
	SEG :: build (1, 1, N);
	int sum = 1;
	while (M--)
	{
		int op = read<int>();
		if (op == 1)
		{
			int l = read<int>(), r = read<int>();

			int now_ans = SEG :: update (1, 1, N, l, r, sum);

			ans = (2ll * ans % Mod + now_ans) % Mod;
			sum = (LL) sum * 2 % Mod;
		}
		else printf("%d\n", ans);
	}
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}