题解：
坑题搞了三天。
莫队+线段树。
还有一些和斐波那契数列有关的性质。
首先答案是$a_1f_1+a_2f_2+…+a_nf_n$，
考虑插进去一个元素对答案产生的影响。
比如插进去一个$a_0$，插进去之后会排到第$k$位。
那么答案是$a_1f_1+a_2f_2+…+a_0f_k+a_kf_{k+1}+…+a_nf_{n+1}$，
等于$ans0+a_0f_k+a_kf_{k-1}+…+a_nf_{n-1}$。
所以单点插入，区间加斐波那契数？
不可能的。
考虑用矩阵推出斐波那契数列。
其实不需要矩阵快速幂，存当前$a_i*f_i$和前一个数$a_i*f_{i-1}$即可，
比如我们存的是$(a,b)$，那么有
$(a,b)->(a+b,a)->(2a+b,a+b)->(3a+2b,2a+b)->(5a+3b,3a+2b)->……$
系数都是斐波那契数。
向前转移同理
$(a,b)->(b,a-b)->(a-b,-a+2b)->(-a+2b,2a-3b)->……$
这个系数可以和斐波那契数列一起求，转移也很好推。
线段树单点插入时要一起搞事情，取模要少取，不然会$T$的很惨。
代码：
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 30050; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){c=c*10+ch-‘0‘;ch=getchar();} x = f*c; } int n,qq,w[N],to[N],m=0,B=170; int MOD,f[N],g[N],ans[N]; void Mod(int&x){if(x>=MOD)x-=MOD;} void init() { if(MOD==1)return ; f[1]=f[2]=1; for(int i=3;i<=n+1;i++) Mod(f[i]=f[i-1]+f[i-2]); g[1]=1,g[2]=MOD-1; for(int i=3;i<=n+1;i++) Mod(g[i]=g[i-2]-g[i-1]+MOD); } struct Pair { int x,y; Pair(){} Pair(int x,int y):x(x),y(y){} }p[N]; bool cmp(Pair a,Pair b){return a.x<b.x;} struct Q { int l,r,id; Q(){} Q(int l,int r,int i):l(l),r(r),id(i){} }q[N]; bool CMP(Q a,Q b){return (a.l/B)==(b.l/B)?(a.r<b.r):(a.l<b.l);} struct segtree { int siz[N<<2],tag[N<<2]; int c[N<<2][2]; void update(int u) { siz[u] = siz[u<<1]+siz[u<<1|1]; Mod(c[u][0] = c[u<<1][0]+c[u<<1|1][0]); Mod(c[u][1] = c[u<<1][1]+c[u<<1|1][1]); } void add(int u,int k) { tag[u] += k; int a = c[u][0],b = c[u][1]; if(k>0) { (c[u][0] = a*f[k+1]+b*f[k])%=MOD; (c[u][1] = a*f[k]+b*f[k-1])%=MOD; }else if(k<0) { k = -k; (c[u][0] = a*g[k-1]+b*g[k])%=MOD; (c[u][1] = a*g[k]+b*g[k+1])%=MOD; } } void pushdown(int u) { if(tag[u]) { add(u<<1,tag[u]); add(u<<1|1,tag[u]); tag[u] = 0; } } void insert(int l,int r,int u,int qx,int k,int d) { if(l==r) { if(k==-1)c[u][0]=c[u][1]=0,siz[u] = 0; else c[u][0] = f[k]*to[l]%MOD,c[u][1] = f[k-1]*to[l]%MOD,siz[u] = 1; return ; } pushdown(u); int mid = (l+r)>>1; if(qx<=mid)insert(l,mid,u<<1,qx,k,d),add(u<<1|1,d); else insert(mid+1,r,u<<1|1,qx,k+(k!=-1)*siz[u<<1],d); update(u); } }tr; int vis[N]; inline void push(int x) { if(!x)return ; if(!vis[x])tr.insert(1,m,1,x,1,1); vis[x]++; } inline void pull(int x) { if(!x)return ; vis[x]--; if(!vis[x])tr.insert(1,m,1,x,-1,-1); } int main() { // freopen("tt.in","r",stdin); read(n),read(MOD); init(); for(int a,i=1;i<=n;i++) read(a),p[i]=Pair(a,i); sort(p+1,p+1+n,cmp); for(int las = 0x3f3f3f3f,i=1;i<=n;i++) { if(las != p[i].x) { las = p[i].x; to[++m] = las%MOD; } w[p[i].y] = m; } read(qq); for(int l,r,i=1;i<=qq;i++) { read(l),read(r); q[i]=Q(l,r,i); } sort(q+1,q+1+qq,CMP); int L = 0,R = 0; for(int i=1;i<=qq;i++) { while(R<q[i].r)push(w[++R]); while(R>q[i].r)pull(w[R--]); while(L<q[i].l)pull(w[L++]); while(L>q[i].l)push(w[--L]); ans[q[i].id]=tr.c[1][0]; } for(int i=1;i<=qq;i++) printf("%d\n",ans[i]); return 0; }
原文：https://www.cnblogs.com/LiGuanlin1124/p/10712874.html