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;
}
标签:return,matrix,CF633H,int,luogu,矩阵,II,++,bla
From: https://www.cnblogs.com/Sakura-TJH/p/luogu_CF633H.html