【luogu CF633H】Fibonacci-ish II（莫队）（线段树）（矩阵乘法）

Fibonacci-ish II

题目链接：luogu CF633H

题目大意

给你一个序列，每次问你一个区间，把里面的数拿出来去重排序，第 i 个位置乘上斐波那契数列第 i 项之后所有数的和。

思路

这题卡常。
（而且好像能暴力优化草过去但是写的是标算）

---

首先看着数据范围会主观思考 $\sqrt{n}$ 有关的，思考完分块不太行之后。
我们考虑莫队（有人忘了这个东西我不说是谁），因为发现可以离线。

那你就考虑每次插入或者删除一个数，然后因为要去重，我们就只需要考虑新多出这个数和这个数被全部删完的时候。
那以放新的数为例，那就是这个数的贡献出现，然后给后面的数的位置后移一个，那就是斐波那契各自后一位。

那这个可以用什么维护呢，其实就是矩阵乘法（有人又忘了我不说是谁），那就是乘上一个转移矩阵嘛。
那至于去掉一个数，就是把它的贡献弄掉，然后把后面的数乘上一个转移矩阵的逆矩阵。
那这个区间乘矩阵，而且最后你要的是每个乘上的一个系数（就它自己的值），所以我们考虑用线段树来维护，除了矩阵那些再弄一个记录数组记录着系数，这样子我们就可以很快的让你当前位置的数的贡献出现（$=a_i$）或消失（$0$）

然后就是一些卡常说的：
因为你线段树嘛，所以要离散化，你就好离散化好了之后把编号对应一下就直接给权值取模了。
而且过程中也是能先不取模就别取模，而且别开 long long。
然后发现莫队那个奇偶优化真的有快到。（由于是最后加了这个过了心里的想法，说不定没加多少）
然后调调块长，加点 inline 和 register 应该就差不多了。

代码

#include
#include
#include

using namespace std;

const int N = 3e4 + 100;
int n, m, a[N], b[N], bn, dy[N], q, num[N];
int B, bla[N], ans[N];
struct Quest {
	int id, l, r;
}qs[N];

int re, zf; char c;
int read() {
	re = 0; zf = 1; c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') zf = -zf; c = getchar();
	}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re * zf;
}

void writen(int x) {
	if (x > 9) writen(x / 10);
	putchar(x % 10 + '0');
}
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	writen(x);
}

bool cmp(Quest x, Quest y) {
	if (bla[x.l] == bla[y.l]) return bla[x.l] & 1 ? x.r < y.r : x.r > y.r;
	return bla[x.l] < bla[y.l];
}

struct matrix {
	int a[2][2];
	
	matrix() {
		a[0][0] = 1; a[0][1] = 0;
		a[1][0] = 0; a[1][1] = 1;
	}
	
	matrix(int op) {
		if (op == 1) {
			a[0][0] = 1; a[1][0] = 1;
			a[0][1] = 1; a[1][1] = 0;
		}
		if (op == -1) {
			a[0][0] = 0; a[1][0] = 1;
			a[0][1] = 1; a[1][1] = m - 1;
		}
		if (op == 0) {
			a[0][0] = 0; a[1][0] = 0;
			a[0][1] = 0; a[1][1] = 0;
		}
	}
	
	inline int* operator[](int x) {return a[x];}
}E, G, Gv;

inline matrix operator +(matrix x, matrix y) {
	matrix z = matrix(0);
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) 
		z[i][j] = (x[i][j] + y[i][j]) % m;
	return z;
}
inline matrix operator *(matrix x, int y) {
	if (y == 1) return x;
	matrix z = matrix(0);
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			z[i][j] = x[i][j] * y % m;
	return z;
}
inline matrix operator *(matrix x, matrix y) {
	matrix z = matrix(0);
	for (int k = 0; k < 2; k++)
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				z[i][j] += x[i][k] * y[k][j];
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) z[i][j] %= m;
	return z;
}
inline bool operator !=(matrix x, matrix y) {
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++)
		if (x[i][j] != y[i][j]) return 1;
	return 0;
}

struct XD_tree {
	int fb[N << 2];
	matrix lzy[N << 2], val[N << 2];
	
	inline void up(int now) {
		val[now] = (val[now << 1] * fb[now << 1]) + (val[now << 1 | 1] * fb[now << 1 | 1]);
	}
	
	inline void downm(int now, matrix va) {
		val[now] = val[now] * va; lzy[now] = lzy[now] * va;
	}
	
	inline void down(int now) {
		if (lzy[now] != E) {
			downm(now << 1, lzy[now]); downm(now << 1 | 1, lzy[now]);
			lzy[now] = E;
		}
	}
	
	inline void build(int now, int l, int r) {
		if (l == r) {
			val[now] = G;
			return ;
		}
		fb[now] = 1;
		int mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		up(now);
	}
	
	inline void insert(int now, int l, int r, int pl) {
		if (l == r) {
			fb[now] = dy[pl]; return ;
		}
		down(now); int mid = (l + r) >> 1;
		if (pl <= mid) insert(now << 1, l, mid, pl), downm(now << 1 | 1, G);
			else insert(now << 1 | 1, mid + 1, r, pl);
		up(now);
	}
	
	inline void erase(int now, int l, int r, int pl) {
		if (l == r) {
			fb[now] = 0; return ;
		}
		down(now); int mid = (l + r) >> 1;
		if (pl <= mid) erase(now << 1, l, mid, pl), downm(now << 1 | 1, Gv);
			else erase(now << 1 | 1, mid + 1, r, pl);
		up(now);
	}
}T;

inline void add(int x) {
	if (!num[x]++) T.insert(1, 1, bn, x);
}

inline void del(int x) {
	if (!--num[x]) T.erase(1, 1, bn, x);
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] = read();
	}
	
	E = matrix(); G = matrix(1); Gv = matrix(-1);
	
	sort(b + 1, b + n + 1); bn = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= bn; i++) dy[i] = b[i] % m;
	for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + bn + 1, a[i]) - b;
	
	B = 300;
//	B = sqrt(n);
	for (int i = 1; i <= n; i++)
		bla[i] = (i - 1) / B + 1;
	
	q = read();
	for (int i = 1; i <= q; i++) {
		qs[i] = (Quest){i, read(), read()};
	}
	sort(qs + 1, qs + q + 1, cmp);
	
	T.build(1, 1, bn);
	int l = 1, r = 0;
	for (int i = 1; i <= q; i++) {
		while (l < qs[i].l) del(a[l]), l++;
		while (l > qs[i].l) l--, add(a[l]);
		while (r < qs[i].r) r++, add(a[r]);
		while (r > qs[i].r) del(a[r]), r--;
		ans[qs[i].id] = T.val[1][0][1];
	}
	
	for (int i = 1; i <= q; i++) {
		write((ans[i] % m + m) % m); putchar('\n');
	}
	
	return 0;
}
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
181
182
183
184
185
186
187
188
189
190
191
192
193