Fibonacci-ish II

题目链接：luogu CF633H

题目大意

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

思路

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

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

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

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

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

代码

#include<cmath>
#include<cstdio>
#include<algorithm>

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;
}