HDU5286 wyh2000 and sequence【分块 均摊复杂度】

HDU5286 wyh2000 and sequence

题意：

给出长为\(N\)的序列\(A_1,A_2,A_3,\cdots,A_n\)，\(q\)次询问，每次询问给出区间\([L,R]\)，假设区间内出现过的数为\(C_1,C_2,\cdots,C_k\)，出现的次数分别为\(B_1,B_2,\cdots,B_k\)，输出\(\sum_{i=1}^{k}C_i^{B_i} % 1000000007\)，要求在线

题解：

如果不要求在线，直接用莫队很快就能解决，现在要求在线，还是考虑把序列分块，预处理出所有连续的块的答案，和到第\(i\)块为止，各个数出现的次数的前缀和

对于每次查询，如果在一个块内，就直接暴力查询

否则对于在两端非整块的元素，记录元素大小和出现次数，将这些元素带来的贡献计算一下即可

有点卡常

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MOD = 1e9+7;

const int MAXN = 5e4+7;

const int SQT = 240;

int n,q,m,sqt,A[MAXN],pre[SQT][MAXN],pos[MAXN],belong[MAXN],l[SQT],r[SQT],la;

int ans[SQT][SQT],num[MAXN];

vector<int> vec,cnt,pw[MAXN];

void divide(){

    sqt = pow(n,0.5);

    m = n / sqt + (n%sqt?1:0);

    for(int i = 1; i <= n; i++) belong[i] = (i-1) / sqt + 1;

    for(int i = 1; i <= m; i++) l[i] = (i-1) * sqt + 1, r[i] = i * sqt;

    r[m] = n;

}

void gao(){

    int L, R;

    scanf("%d %d",&L,&R);

    L = (L^la)%n+1; R = (R^la)%n+1;

    if(L>R) L ^= R ^= L ^= R;

    int lp = belong[L], rp = belong[R];

    if(lp==rp){

        int ret = 0;

        for(int i = L; i <= R; i++) num[pos[i]] = 0;

        for(int i = L; i <= R; i++){

            ret = ret - pw[pos[i]][num[pos[i]]];

            ret = ret + pw[pos[i]][++num[pos[i]]];

            if(ret<0) ret += MOD;

            if(ret>=MOD) ret -= MOD;

        }

        printf("%d\n",la=ret);

    }

    else{

        vector<int> arr;

        for(int i = L; i <= r[lp]; i++){

            num[pos[i]] = 0;

            arr.push_back(pos[i]);

        }

        for(int i = l[rp]; i <= R; i++){

            num[pos[i]] = 0;

            arr.push_back(pos[i]);

        }

        sort(arr.begin(),arr.end()); arr.erase(unique(arr.begin(),arr.end()),arr.end());

        for(int i = L; i <= r[lp]; i++) num[pos[i]]++;

        for(int i = l[rp]; i <= R; i++) num[pos[i]]++;

        lp++, rp--;

        int ret = ans[lp][rp];

        for(int i = 0; i < (int)arr.size(); i++){

            ret = ret - pw[arr[i]][pre[rp][arr[i]]-pre[lp-1][arr[i]]];

            ret = ret + pw[arr[i]][pre[rp][arr[i]]-pre[lp-1][arr[i]]+num[arr[i]]];

            if(ret<0) ret += MOD;

            if(ret>=MOD) ret -= MOD;

        }

        printf("%d\n",la=ret);

    }

}

void solve(){

    scanf("%d %d",&n,&q);

    vec.clear();

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

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

        vec.push_back(A[i]);

    }

    sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());

    for(int i = 1; i <= n; i++) pos[i] = lower_bound(vec.begin(),vec.end(),A[i]) - vec.begin();

    divide();

    for(int i = 1; i <= m; i++) for(int j = 0; j < (int)vec.size(); j++) pre[i][j] = 0;

    for(int i = 1; i <= n; i++) pre[belong[i]][pos[i]]++;

    for(int i = 1; i <= m; i++) for(int j = 0; j < (int)vec.size(); j++) pre[i][j] += pre[i-1][j];

    cnt.resize(vec.size());

    for(int i = 0; i < (int)vec.size(); i++) cnt[i] = 0;

    for(int i = 1; i <= n; i++) cnt[pos[i]]++;

    for(int i = 0; i < (int)vec.size(); i++){

        pw[i].resize(cnt[i]+1);

        pw[i][0] = 1; for(int j = 1; j <= cnt[i]; j++) pw[i][j] = 1ll * pw[i][j-1] * vec[i] % MOD;

        pw[i][0] = 0;

    }

    for(int i = 1; i <= m; i++){

        memset(num,0,sizeof(num));

        int p = l[i] - 1, ret = 0;

        for(int j = i; j <= m; j++){

            while(p<r[j]){

                p++;

                ret -= pw[pos[p]][num[pos[p]]];

                ret += pw[pos[p]][++num[pos[p]]];

                if(ret<0) ret += MOD;

                if(ret>=MOD) ret -= MOD;

            }

            ans[i][j] = ret;

        }

    }

    la = 0;

    while(q--) gao();

    for(int i = 0; i < (int)vec.size(); i++) pw[i].clear();

}

int main(){

    int T;

    for(scanf("%d",&T); T; T--) solve();

    return 0;

}