CF633H Fibonacci-ish II（莫队+线段树）

温馨提示：本题十分卡常数，我手动开O2才过的。而数据范围不伦不类的n<=30000，常数小的O(n)居然比O(n√nlogn)跑得快……

考虑插进去一个元素对答案产生的影响。原本数列为Σa[i]f[i]，其中1<=i<=n，然后考虑在k位置插入a[0]，答案显然是a[1]f[1]+a[2]f[2]+...+a[0]f[k]+a[k]f[k+1]+...+a[n]f[n+1]，然后直接区间加斐波那契数显然是不可能的。这时候要向后转移斐波那契数列，(a,b)->(a+b,a)->(2a+b,a+b)->(3a+2b,2a+b)->……系数始终是斐波那契数。

删除时向前转移？系数可以和斐波那契数一起直接求。

我是开O2、O3、Ofast优化才过的，如果能正常过可能会换成常数较小的code吧

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#pragma GCC optimize("inline")

#pragma GCC optimize("-fgcse")

#pragma GCC optimize("-fgcse-lm")

#pragma GCC optimize("-fipa-sra")

#pragma GCC optimize("-ftree-pre")

#pragma GCC optimize("-ftree-vrp")

#pragma GCC optimize("-fpeephole2")

#pragma GCC optimize("-ffast-math")

#pragma GCC optimize("-fsched-spec")

#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("-falign-jumps")

#pragma GCC optimize("-falign-loops")

#pragma GCC optimize("-falign-labels")

#pragma GCC optimize("-fdevirtualize")

#pragma GCC optimize("-fcaller-saves")

#pragma GCC optimize("-fcrossjumping")

#pragma GCC optimize("-fthread-jumps")

#pragma GCC optimize("-funroll-loops")

#pragma GCC optimize("-fwhole-program")

#pragma GCC optimize("-freorder-blocks")

#pragma GCC optimize("-fschedule-insns")

#pragma GCC optimize("inline-functions")

#pragma GCC optimize("-ftree-tail-merge")

#pragma GCC optimize("-fschedule-insns2")

#pragma GCC optimize("-fstrict-aliasing")

#pragma GCC optimize("-fstrict-overflow")

#pragma GCC optimize("-falign-functions")

#pragma GCC optimize("-fcse-skip-blocks")

#pragma GCC optimize("-fcse-follow-jumps")

#pragma GCC optimize("-fsched-interblock")

#pragma GCC optimize("-fpartial-inlining")

#pragma GCC optimize("no-stack-protector")

#pragma GCC optimize("-freorder-functions")

#pragma GCC optimize("-findirect-inlining")

#pragma GCC optimize("-frerun-cse-after-loop")

#pragma GCC optimize("inline-small-functions")

#pragma GCC optimize("-finline-small-functions")

#pragma GCC optimize("-ftree-switch-conversion")

#pragma GCC optimize("-foptimize-sibling-calls")

#pragma GCC optimize("-fexpensive-optimizations")

#pragma GCC optimize("-funsafe-loop-optimizations")

#pragma GCC optimize("inline-functions-called-once")

#pragma GCC optimize("-fdelete-null-pointer-checks")

#include<bits/stdc++.h>

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

typedef pair<int,int>pii;

const int N=;

struct node{int l,r,id;}q[N];

int n,m,B,Q,mod,f[N],g[N],vis[N],a[N],w[N],sz[N<<],lazy[N<<],c[N<<][],ans[N];

pii p[N];

bool cmp(node a,node b){return (a.l-)/B==(b.l-)/B?a.r<b.r:a.l<b.l;}

void pushup(int rt)

{

    sz[rt]=sz[rt<<]+sz[rt<<|];

    c[rt][]=(c[rt<<][]+c[rt<<|][])%mod;

    c[rt][]=(c[rt<<][]+c[rt<<|][])%mod;

}

void add(int rt,int k)

{

    lazy[rt]+=k;

    int a=c[rt][],b=c[rt][];

    if(k>)c[rt][]=(1ll*a*f[k+]+1ll*b*f[k])%mod,c[rt][]=(1ll*a*f[k]+1ll*b*f[k-])%mod;

    else k=-k,c[rt][]=(1ll*a*g[k-]+1ll*b*g[k])%mod,c[rt][]=(1ll*a*g[k]+1ll*b*g[k+])%mod;

}

void pushdown(int rt){if(lazy[rt])add(rt<<,lazy[rt]),add(rt<<|,lazy[rt]),lazy[rt]=;}

void update(int k,int v,int d,int l,int r,int rt)

{

    if(l==r)

    {

        if(v==-)c[rt][]=c[rt][]=sz[rt]=;

        else c[rt][]=1ll*f[v]*a[l]%mod,c[rt][]=1ll*f[v-]*a[l]%mod,sz[rt]=;

        return;

    }

    pushdown(rt);

    int mid=l+r>>;

    if(k<=mid)update(k,v,d,lson),add(rt<<|,d);

    else update(k,v+(v!=-)*sz[rt<<],d,rson);

    pushup(rt);

}

void add(int x)

{

    if(!x)return;

    if(!vis[x])update(x,,,,m,);

    vis[x]++;

}

void del(int x)

{

    if(!x)return;

    vis[x]--;

    if(!vis[x])update(x,-,-,,m,);

}

int main()

{

    scanf("%d%d",&n,&mod),B=;

    f[]=f[]=;

    for(int i=;i<=n+;i++)f[i]=(f[i-]+f[i-])%mod;

    g[]=,g[]=mod-;

    for(int i=;i<=n+;i++)g[i]=(g[i-]-g[i-]+mod)%mod;

    for(int i=,x;i<=n;i++)scanf("%d",&x),p[i]=pii(x,i);

    sort(p+,p+n+);

    for(int i=,lst=1e9+;i<=n;i++)

    {

        if(lst!=p[i].first)lst=p[i].first,a[++m]=lst%mod;

        w[p[i].second]=m;

    }

    scanf("%d",&Q);

    if(mod==){while(Q--)puts("");return ;}

    for(int i=;i<=Q;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;

    sort(q+,q+Q+,cmp);

    for(int i=,l=,r=;i<=Q;i++)

    {

        while(r<q[i].r)add(w[++r]);

        while(r>q[i].r)del(w[r--]);

        while(l<q[i].l)del(w[l++]);

        while(l>q[i].l)add(w[--l]);

        ans[q[i].id]=c[][];

    }

    for(int i=;i<=Q;i++)printf("%d\n",ans[i]);

}