Manthan、Codefest 16 H.Fibonacci-sh IIミラクルモザイク線分樹行列

H.Fibonacci-sh II
テーマ接続:
http://codeforces.com/contest/633/problem/H
Description
Yash is finally tired of computting the length of the longest Fibonacci-sh sequence.He now plus around with more complexs such as Fibonanch-sh potentals.
Fibonacci-sh poteal of an array ai is computed as follows:
Remove all elemens j i if there exists i?<8201;jsuch that ai=?aj.Sort the remaning elemens in ascending order，i.a 1?<821;a 2_;;;;;a=828282820;;;;;;;;̵̵;;;̵;＋̵a2・F 2̵＋?…?＋?an・Fn、where Fi is the i-th Fibonacci number.You are given an array ai of length n and q ranges from lj to rj.For each range j you have to compute the Fibonance the Fibonanch-the potent the comprament of compration。
Input
The first line of the input contains integers of n and m(1̵≦?n，?m≦?30?000)-the length of the initial array and the modulo，The perectively.
The next line contains n integers ai（0̵≦?ai̵≦?109）—elemens of the array.
The n followowthe number of ranges q(1̵≦?qq̵≤?30?000)
Last q lines contain pairs of indices li and ri(1̵≦?li̵≦?ri≦?n)-ranges to compute Fibonacci-sh potentals.
Output
Print qライン、i-th of the m must contain the Fibonacci-sh potental of the i-th range modulo m.
Sample Input
5 10 2 1 2 2 2 2 2 2 2 4 5
Sample Output
3
ベント
題意
n個を数えてq回聞いてみます。
毎回お聞きします。l、r区間です。
まずl、rの区間の数を全部取り出して、小さい時から大順に並べてから重いです。
そして答えはans=f[1]*a[1]+f[2]….+f[n]a[n]に等しいです。
f[i]はi番目のfib数である。
答えを求めるmod m
クイズ:
今は出題者が大ニュースが出るのが好きです。
複雑度の謎の問題を出す
この問題は莫隊＋変なものを修理します。
しかし定数が大きすぎて、奇跡の暴力を振るっていません。
腫れていると言っていますか
正解は以下の通りです
莫隊は問い合わせを処理して、線分樹は答えを処理します。
線分樹はどう処理しますか？
ここで面倒なのはプッシュシュです。upする
pushup行列で書いてもいいです。
各点は2つのマトリクスを維持します。[1][2]は答えの行列で、[2][2]はfibの行列です。
a[i][1]=a[i*2][1]+a[i*2+1][1]、[2]*a[i*2]、[2]
a[i][2]=a[i*2][2]*a[i*2+1][2]
乗算記号は行列乗算です。
もちろん、数学でもいいです。
f(k+1)*(a 1*f(i)+a 2*f(i+1)+f(k)*(a 1*(f(i-1)+a 2*f(i)…)=a 1*f(i+k)+a 2*f(i+k+1)….
大暴力コード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e4+5;
pair<int,int> a[maxn];
int ans[maxn],step[maxn],f[maxn],l[maxn],r[maxn],last[maxn];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].first),a[i].second=i;
    sort(a+1,a+1+n);
    f[0]=1,f[1]=1;
    for(int i=2;i<=n;i++)
        f[i]=(f[i-1]+f[i-2])%m;
    int q;scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        last[i]=-1;
    }
    for(int i=1;i<=n;i++)
    {
        int d = a[i].first % m;
        for(int j=1;j<=q;j++)
        {
            if(a[i].second<l[j]||a[i].second>r[j])continue;
            if(a[i].first==last[j])continue;
            ans[j]=(ans[j]+f[step[j]++]*d)%m;
            last[j]=a[i].first;
        }
    }
    for(int i=1;i<=q;i++)
        printf("%d
",ans[i]);
}

莫隊

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e4+5;
int a[maxn],pos[maxn],q,n,m,d[maxn];
int fib[maxn][2];
map<int,int> H;
vector<int> V;
long long Ans[maxn];
int cnt[maxn];
typedef int SgTreeDataType;
struct treenode
{
    int L , R  ;
    SgTreeDataType sum1,sum2,siz;
    void update(SgTreeDataType v)
    {
        siz = v;
        sum1 = sum2 = v*d[L]%m;
    }
};

treenode tree[maxn*4];

inline void push_down(int o)
{

}

inline void push_up(int o)
{
    tree[o].siz = tree[2*o].siz + tree[2*o+1].siz;
    tree[o].sum1 = (tree[2*o].sum1+fib[tree[2*o].siz][0]*tree[o*2+1].sum1+fib[tree[2*o].siz][1]*tree[o*2+1].sum2)%m;
    tree[o].sum2 = (tree[2*o].sum2+fib[tree[2*o].siz+1][0]*tree[o*2+1].sum1+fib[tree[2*o].siz+1][1]*tree[o*2+1].sum2)%m;
}

inline void build_tree(int L , int R , int o)
{
    tree[o].L = L , tree[o].R = R,tree[o].sum1 = tree[o].sum2 = tree[o].siz = 0;
    if (R > L)
    {
        int mid = (L+R) >> 1;
        build_tree(L,mid,o*2);
        build_tree(mid+1,R,o*2+1);
    }
}

inline void update(int QL,int QR,SgTreeDataType v,int o)
{
    int L = tree[o].L , R = tree[o].R;
    if (QL <= L && R <= QR) tree[o].update(v);
    else
    {
        push_down(o);
        int mid = (L+R)>>1;
        if (QL <= mid) update(QL,QR,v,o*2);
        if (QR >  mid) update(QL,QR,v,o*2+1);
        push_up(o);
    }
}
struct query
{
    int l,r,id;
}Q[maxn];
bool cmp(query a,query b)
{
    if(pos[a.l]==pos[b.l])
        return a.r<b.r;
    return pos[a.l]<pos[b.l];
}
void Updata(int x)
{
    int p = H[a[x]];
    cnt[p]++;
    if(cnt[p]==1)
        update(p,p,1,1);
}
void Delete(int x)
{
    int p = H[a[x]];
    cnt[p]--;
    if(cnt[p]==0)
        update(p,p,0,1);
}
int main()
{
    scanf("%d%d",&n,&m);
    int sz =ceil(sqrt(1.0*n));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        V.push_back(a[i]);
        pos[i]=(i-1)/sz;
    }

    sort(V.begin(),V.end());
    V.erase(unique(V.begin(),V.end()),V.end());
    for(int i=0;i<V.size();i++)
    {
        H[V[i]]=i+1;
        d[i+1]=V[i]%m;
    }

    fib[0][0]=1%m,fib[1][1]=1%m;
    for(int i=2;i<=n;i++)
    {
        fib[i][0]=(fib[i-1][0]+fib[i-2][0])%m;
        fib[i][1]=(fib[i-1][1]+fib[i-2][1])%m;
    }
    build_tree(1,n,1);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&Q[i].l,&Q[i].r);
        Q[i].id = i;
    }
    sort(Q+1,Q+1+q,cmp);
    int l = 1,r = 0;
    int ans=0;
    for(int i=1;i<=q;i++)
    {
        int id = Q[i].id;
        while(r<Q[i].r)
        {
            r++;
            Updata(r);
        }
        while(l>Q[i].l)
        {
            l--;
            Updata(l);
        }
        while(r>Q[i].r)
        {
            Delete(r);
            r--;
        }
        while(l<Q[i].l)
        {
            Delete(l);
            l++;
        }
        Ans[id]=tree[1].sum1;
    }
    for(int i=1;i<=q;i++)
        printf("%lld
",Ans[i]);
}