CodeForces - 633H ：Fibonacci-ish II（正解：莫对+线段树）

Yash is finally tired of computing the length of the longest Fibonacci-ish sequence. He now plays around with more complex things such as Fibonacci-ish potentials.

Fibonacci-ish potential of an array a_i is computed as follows:

Remove all elements j if there exists i < j such that a_i = a_j.
Sort the remaining elements in ascending order, i.e. a₁ < a₂ < ... < a_n.
Compute the potential as P(a) = a₁·F₁ + a₂·F₂ + ... + a_n·F_n, where F_i is the i-th Fibonacci number (see notes for clarification).

You are given an array a_i of length n and q ranges from l_j to r_j. For each range j you have to compute the Fibonacci-ish potential of the array b_i, composed using all elements of a_i from l_j to r_j inclusive. Find these potentials modulo m.

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, respectively.

The next line contains n integers a_i (0 ≤ a_i ≤ 10⁹) — elements of the array.

Then follow the number of ranges q (1 ≤ q ≤ 30 000).

Last q lines contain pairs of indices l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — ranges to compute Fibonacci-ish potentials.

Output

Print q lines, i-th of them must contain the Fibonacci-ish potential of the i-th range modulo m.

Example

Input

Output

3
3

题意：Q次询问，每次询问给一个区间，让你把区间排序，按顺序乘对应的斐波拉契数。

思路： 正解占位，暂时不会。只把暴力的码了。暴力：每次看每个数是否存在于当前区间，然后做乘即可。复杂度O（nq）。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define pii pair<int,int>

#define F first

#define S second

using namespace std;

const int maxn=;

pii a[maxn]; int f[maxn],L[maxn],R[maxn],num[maxn],ans[maxn],lt[maxn];

int main()

{

    int N,M,P;

    scanf("%d%d",&N,&P);

    f[]=; f[]=; rep(i,,N) f[i]=(f[i-]+f[i-])%P;

    rep(i,,N) scanf("%d",&a[i].F),a[i].F,a[i].S=i;

    sort(a+,a+N+);

    scanf("%d",&M);

    rep(i,,M) {

        scanf("%d%d",&L[i],&R[i]);

        lt[i]=-;

    }

    rep(i,,N){

        int d=a[i].F%P;

        rep(j,,M){

            if(a[i].S>R[j]||a[i].S<L[j]) continue;//

            if(a[i].F==lt[j]) continue;

            ans[j]=(ans[j]+f[++num[j]]*d)%P;

            lt[j]=a[i].F;

        }

    }

    rep(i,,M) printf("%d\n",ans[i]);

    return ;

}

巴特西

CodeForces - 633H ：Fibonacci-ish II（正解：莫对+线段树）

最新文章

热门文章