51nod 1680区间求和（dp+树状数组/线段树）

不妨考虑已知一个区间[l,r]的k=1、k=2....k=r-l+1这些数的答案ans（只是这一个区间，不包含子区间）

那么如果加入一个新的数字a[i](i = r+1)

则新区间[l, i]的答案为ans + (c+1)*a[i] + s ，c为[l,r]中小于等于a[i]的数的个数，s为大于它的树的和

接下来考虑一个区间组，区间组i表示的是以i为结尾的所有区间

另dp[i]表示[1,i], [2,i] .... [i-1, i],[i, i]这些区间的答案和

那么dp[i+1] = dp[i] + ∑(j*a[j])(if a[j] >= a[i]) + ∑k*a[i](if a[k] < a[i]) + i*a[i]

这样的话，最后只需要把dp[1~n]加起来就构成了答案

上面的值可以使用树状数组或者线段树维护

这里还使用了hashmap来进行离散化

（线段树日常卡常数，优化很久才过）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#include <ext/hash_map>

#define pb push_back

#define fi first

#define se second

#define mp make_pair

using namespace std;

using namespace __gnu_cxx;

const int maxn = 1e6 + ;

typedef long long LL;

typedef pair<int, int> PII;

vector<int> V(maxn, );

const int MOD = (1e9 + ) + 0.5;

hash_map <int, int> H;

PII tree[maxn*];

PII v;

int k, L, R;

inline PII Add(PII a, PII b){

    return {(a.fi + b.fi)%MOD, (a.se + b.se)%MOD};

}

void Insert(int o, int l, int r){

    if(l == r){

        tree[o] = Add(tree[o], {v.fi, (LL)v.fi*v.se%MOD});

        return;

    }

    int mid = (l+r)>>;

    if(k <= mid) Insert(o<<, l, mid);

    else Insert((o<<)+, mid+, r);

    tree[o] = Add(tree[o<<], tree[(o<<)+]);

}

PII Query(int o, int l, int r){

    if(tree[o].fi == ) return mp(, );

    if(L <= l && r <= R){

        return tree[o];

    }

    int mid = (l+r)>>;

    return Add((L <= mid ? Query(o*, l, mid) : mp(, )),

               (R > mid ? Query(o*+, mid+, r) : mp(, )));

}

int a[maxn], A, B, C;

int n;

void I_AM_ANGRY(){

    for(int i = ; i <= n; i++){

        a[i] = ((LL)a[i-]*A + B)%C;

        V[i] = a[i];

    }

    /*

    for(int i = 2; i <= n; i += 2){

        a[i] = ((LL)a[i-1]*A + B)%C;

        a[i+1] = ((LL)a[i]*A + B)%C;

        V[i] = a[i];

        V[i+1] = a[i+1];

    }

    */

    /*

    for(int i = 2; i <= n; i += 4){

        a[i] = ((LL)a[i-1]*A + B)%C;

        a[i+1] = ((LL)a[i]*A + B)%C;

        a[i+2] = ((LL)a[i+1]*A + B)%C;

        a[i+3] = ((LL)a[i+2]*A + B)%C;

        V[i] = a[i];

        V[i+1] = a[i+1];

        V[i+2] = a[i+2];

        V[i+3] = a[i+3];

    }*/

    V[] = a[];

}

int main()

{

    cin>>n>>a[]>>A>>B>>C;

    I_AM_ANGRY();

    sort(V.begin(), V.end());

    int tot = ;

    for(auto x : V) if(!H[x]) H[x] = ++tot;

    LL dp = a[], ans = dp;

    int N = n; n = tot;

    v = {, a[]}; k = H[a[]];

    Insert(, , n);

    for(int i = ; i <= N; i++){

        int t = H[a[i]];

        L = t; R = n;

        PII x = Query(, , n);

        dp = (dp + x.se + (LL)(tree[].fi - x.fi+i)*a[i])%MOD;

        v = {i, a[i]}; k = t;

        Insert(, , n);

        ans += dp;

    }

    cout<<(ans%MOD + MOD)%MOD<<endl;

    return ;

}

巴特西

51nod 1680区间求和（dp+树状数组/线段树）

最新文章

热门文章

巴特西

51nod 1680区间求和 （dp+树状数组/线段树）

最新文章

热门文章

51nod 1680区间求和（dp+树状数组/线段树）