CF633H-Fibonacci-ish-II

莫队+线段树维护矩乘，复杂度$\Theta(T^3n\sqrt nlogn)$，也可以二次离线达到$\Theta(n\sqrt n)$的复杂度。

挺不错的题，除了卡常和放了暴力过去之外都挺好的，看到没有正解的题解，我就来发一发。

我们考虑加入一个数造成的影响，后面的数的矩阵都全部要乘以一个斐波那契递推的矩阵，我们考虑在权值线段树上维护，然后打上标记维护即可，细节挺多的，然后删除一个数就是后面的数乘一个逆矩阵即可。

因为本题卡常，所以离散化后立即取模，避免用$long long$，减少不必要的取模，尽量精简函数。

#pragma region revive
#include <cstdio>
#include <iostream>
#include <algorithm>
#define inl inline
#define re register int
#define fa(x) fa[x]
#define son(x, y) t[x].child[y]
#define ls(x) child[x][0]
#define rs(x) child[x][1]
#define ll long long
const int inf = 0x3f3f3f3f;
const ll Linf = 0x3f3f3f3f3f3f3f3fLL;
#define lowbit(x) ((x) & (-x))
using namespace std;
#ifndef _DEBUG
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++) = (c))
#define io_eof() (IOB.in.p >= IOB.in.pend)
struct IOBUF {
	struct {
		char buff[1 << 27], *p, *pend;
	} in;
	struct {
		char buff[1 << 27], *p;
	} out;
	IOBUF() {
		in.p = in.buff;
		out.p = out.buff;
		in.pend = in.buff + fread(in.buff, 1, 1 << 27, stdin);
	}
	~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); }
} IOB;
#endif
template <typename IO>
inl void write(IO x) {
	if (x == 0) return (void)putchar('0');
	if (x < 0) putchar('-'), x = -x;
	static char buf[30];
	char *p = buf;
	while (x) {
		*(p++) = x % 10 + '0';
		x /= 10;
	}
	while (p > buf)
		putchar(*(--p));
}
inl void writestr(const char *s) {
	while (*s != 0)
		putchar(*(s++));
}
template <typename IO>
inl void writeln(IO x) { write(x), putchar('\n'); }
template <typename IO>
inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s) {
	char *begin = s, c = getchar();
	while (c < 33 || c > 127) {
		c = getchar();
	}
	while (c >= 33 && c <= 127) {
		*(s++) = c;
		c = getchar();
	}
	*s = 0;
	return s - begin;
}
template <typename IO>
inl IO read() {
	IO x = 0;
	register bool w = 0;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return w ? -x : x;
}
#pragma endregion
int s[30001], n, p, siz, mp[30001], a[30001], b[30001], cnt[30001];
ll ans[30001];
struct quiz {
	int l, r, id;
	bool operator<(const quiz& a)const {
		return s[l] == s[a.l] ? s[l] & 1 ? r<a.r : r>a.r : s[l] < s[a.l];
	}
}q[30001];
struct matrix {
	int a[2][2];
	matrix() { a[0][0] = 1, a[1][0] = a[0][1] = 0, a[1][1] = 1; }
	matrix(int x) {
		if (x == 1)a[0][0] = 1, a[1][0] = 1, a[0][1] = 1, a[1][1] = 0;
		else if (!x)a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
		else a[0][0] = 0, a[0][1] = 1, a[1][0] = 1, a[1][1] = -1;
	}
	inl int* operator[](int x) { return a[x]; }
	inl const int* operator[](int x) const { return a[x]; }
	friend matrix operator*(const matrix &a, const matrix &b) {
		matrix c = matrix(0);
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				for (re k = 0; k < 2; k++) {
					c[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				c[i][j] %= p;
			}
		}
		return c;
	}
	friend matrix operator+(const matrix &a, const matrix &b) {
		matrix c = matrix(0);
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				c[i][j] += a[i][j] + b[i][j];
			}
		}
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				c[i][j] %= p;
			}
		}
		return c;
	}
	matrix operator*(int x) {
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				a[i][j] = a[i][j] * x;
			}
		}
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				a[i][j] %= p;
			}
		}
		return *this;
	}
	friend bool operator==(const matrix &a, const matrix &b) {
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				if (a[i][j] != b[i][j])return 0;
			}
		}
		return 1;
	}
	friend bool operator!=(const matrix &a, const matrix &b) {
		return !(a == b);
	}
}E = matrix(), G = matrix(1), R = matrix(-1);
struct node {
	int w;
	matrix tag, ans;
}t[120001];
inl void upd(int k) {
	matrix a = t[k << 1].ans, b = t[k << 1 | 1].ans;
	if (t[k << 1].w != 1)a = a * t[k << 1].w;
	if (t[k << 1 | 1].w != 1)b = b * t[k << 1 | 1].w;
	t[k].ans = a + b;
}
inl void build(int k, int l, int r) {
	t[k].w = l != r;
	if (l == r)return (void)(t[k].ans = G);
	re mid = l + r >> 1;
	build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
	upd(k);
}
inl void mul(int k, matrix w) {
	t[k].ans = t[k].ans*w, t[k].tag = t[k].tag*w;
}
inl void pushdown(int k) {
	if (t[k].tag != E) {
		mul(k << 1, t[k].tag), mul(k << 1 | 1, t[k].tag);
		t[k].tag = E;
	}
}
inl void insert(int k, int l, int r, int p) {
	if (l == r) return (void)(t[k].w = mp[p]);
	pushdown(k);
	re mid = l + r >> 1;
	if (p <= mid)insert(k << 1, l, mid, p), mul(k << 1 | 1, G);
	else insert(k << 1 | 1, mid + 1, r, p);
	upd(k);
}
inl void erase(int k, int l, int r, int p) {
	if (l == r) return (void)(t[k].w = 0);
	pushdown(k);
	re mid = l + r >> 1;
	if (p <= mid)erase(k << 1, l, mid, p), mul(k << 1 | 1, R);
	else erase(k << 1 | 1, mid + 1, r, p);
	upd(k);
}
inl void add(int x) {
	if (!cnt[x]++) insert(1, 1, siz, x);
}
inl void del(int x) {
	if (!--cnt[x]) erase(1, 1, siz, x);
}
signed main() {
	n = read<int>(), p = read<int>();
	for (re i = 1; i <= n; i++)a[i] = b[i] = read<int>();
	sort(b + 1, b + 1 + n);
	siz = unique(b + 1, b + 1 + n) - b - 1;
	re m = read<int>(), num = sqrt(n);
	for (re i = 1; i <= n; i++) {
		re k = a[i];
		mp[a[i] = lower_bound(b + 1, b + 1 + siz, a[i]) - b] = k % p;
	}
	for (re i = 1; i <= 30000; i++)s[i] = (i - 1) / num + 1;
	for (re i = 1; i <= m; i++) q[i].l = read<int>(), q[i].r = read<int>(), q[i].id = i;
	sort(q + 1, q + 1 + m);
	build(1, 1, siz);
	re l = 1, r = 0;
	for (re i = 1; i <= m; i++) {
		while (l > q[i].l)add(a[--l]);
		while (r < q[i].r)add(a[++r]);
		while (l < q[i].l)del(a[l++]);
		while (r > q[i].r)del(a[r--]);
		ans[q[i].id] = t[1].ans[0][1]%p;
	}
	for (re i = 1; i <= m; i++)writeln((ans[i] % p + p) % p);
}