【Codeforces 633H】Fibonacci-ish II

  首先要知道斐波那契数列一个很有趣的性质：\[F_n = F_{a+1} * F_b + F_a * F_{b-1}\ (a+b=n)\]对所有的整数n,a,b都是满足的，包括负数。式子用矩阵就可以推了。

  首先为将a的值离散化，建棵权值线段树，维护子树中的当前在a的potential序列中的数对答案的贡献。在权值线段树里进行加点删点操作，就可以快速地求出当前的数组a的potential序列。

  用莫队算法处理询问。接下来我们要在\(O(log(n))\)的时间内处理单步操作。

  每次新加入一个点x，那么所有权值大于x的数对应的斐波那契数列中的项都要右移一位。如果每次暴力修改的话复杂度是\(O(n)\)的，所以要用上lazy_tag。

  一眼看过去这个lazy_tag好像不可加的样子。要注意，斐波那契数列在存储时，存相邻的两位往往有奇效。

\[
\ F(k+1)*(a_{1}*F(i)+a_{2}*F(i+1) \cdots) \\
\ +F(k)*(a_{1}*F(i-1)+a_{2}*F(i)+\cdots) \\
\ =(a_{1}*F(i+k)+a_{2}*F(i+k+1))
\]

  （这个排版太差了...宽度太小了QAQ）

  显然，只要维护两个序列就能在\(O(1)\)的时间内打标记和传标记了。

  时间复杂度是\(O(n \sqrt{n} *log(n)\)的，每次在线段树上的操作尽量一次完成，否则可能因为常数太大而T掉。（明明是你自己代码自带大常数

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=30010;
int p;

int fi[maxn];
inline int f(int x) {if (x>=0) return fi[x];else return ((-x)&1)?fi[-x]:p-fi[-x];}

struct Segment_Tree
{
	int sum1[maxn<<2],sum2[maxn<<2];
	int size[maxn<<2];
	int tag_k[maxn<<2];
	int n;

	#define ls (o<<1)
	#define rs (o<<1|1)
	#define mid ((l+r)>>1)

	void Update(int o) {sum1[o]=(sum1[ls]+sum1[rs])%p;sum2[o]=(sum2[ls]+sum2[rs])%p;size[o]=size[ls]+size[rs];}
	void Mark(int o,int k)
	{
		if (k==1) {int x1=sum1[o];sum1[o]+=sum2[o],sum2[o]=x1;if (sum1[o]>p) sum1[o]-=p;tag_k[o]++;return;}
		int x1=(sum1[o]*f(k+1)+sum2[o]*f(k))%p,x2=(sum1[o]*f(k)+sum2[o]*f(k-1))%p;
		sum1[o]=x1;sum2[o]=x2;tag_k[o]+=k;
	}

	void Push_Down(int o)
	{
		if (tag_k[o])
		{
			Mark(ls,tag_k[o]);
			Mark(rs,tag_k[o]);
			tag_k[o]=0;
		}
	}

	void Change(int o,int l,int r,int x,int v,int w,int c)
	{
		if (l==r)
		{
			if (c==-1) size[o]=sum1[o]=sum2[o]=0;
			else size[o]=1,sum1[o]=v*f(w+1)%p,sum2[o]=v*f(w)%p;
			return;
		}
		Push_Down(o);
		if (x<=mid) Change(ls,l,mid,x,v,w,c),Mark(rs,c);
		else Change(rs,mid+1,r,x,v,w+size[ls],c);
		Update(o);
	}

	void Change(int x,int v,int c) {Change(1,1,n,x,v,0,c);}
	int Result() {return sum1[1];}
}T;

int a[maxn],temp[maxn];
int cnt[maxn];
int ans[maxn];
int n,q,blocksize,ts;

struct Query {int l,r,block,id;bool operator< (const Query &b) const {return block<b.block || block==b.block && r<b.r;}}Q[maxn];

int main()
{
	scanf("%d%d",&n,&p);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(temp,a,sizeof(temp));
	sort(temp+1,temp+1+n);
	ts=unique(temp+1,temp+1+n)-(temp+1);
	for (int i=1;i<=n;i++) a[i]=lower_bound(temp+1,temp+1+ts,a[i])-temp;
	for (int i=1;i<=ts;i++) temp[i]%=p;
	T.n=ts;
	fi[1]=1;fi[2]=1;
	for (int i=3;i<=ts+2;i++) fi[i]=(fi[i-1]+fi[i-2])%p;
	blocksize=sqrt(n);
	scanf("%d",&q);
	for (int i=1;i<=q;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].block=Q[i].l/blocksize,Q[i].id=i;
	sort(Q+1,Q+1+q);
	for (int i=1,l=1,r=0;i<=q;i++)
	{
		while (r<Q[i].r) {r++;cnt[a[r]]++;if (cnt[a[r]]==1) T.Change(a[r],temp[a[r]], 1);}
		while (r>Q[i].r) {cnt[a[r]]--;if (cnt[a[r]]==0) T.Change(a[r],temp[a[r]],-1);r--;}
		while (l>Q[i].l) {l--;cnt[a[l]]++;if (cnt[a[l]]==1) T.Change(a[l],temp[a[l]], 1);}
		while (l<Q[i].l) {cnt[a[l]]--;if (cnt[a[l]]==0) T.Change(a[l],temp[a[l]],-1);l++;}
		ans[Q[i].id]=T.Result();
	}
	for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}