hihocoder 1553 区间统计

题意

题解

首先预处理所有幂次的结果，$O(NK)$；还有IO时间一定要注意。以下均不讨论。

一看题，无修改区间询问，莫队走起。但是用map复杂度太高了，没算错的话应该是 $O(n^{1.5}logn+m\sqrt{n})$ 。

考虑到A[]的范围不大，可以对A[]计数，不过没什么卵用。但是对A[]计数以后可以发现，我们不仅可以对值计数还可以对次数计数，也就是说has[i]表示有多少数在当前询问中的出现次数等于 i 。

到这里还是比较容易的，但是如果直接扫has[]复杂度并没有降低 $O(n^{1.5}+mn)$ 。。。

仍然是考虑分治思想，一次询问最多是整个区间，整个区间中出现次数大于 $\sqrt{n}$ 的数不会超过 $\sqrt{n}$ 个，还可以进行另外的预处理，我就直接multiset暴力了。。。复杂度大概是 $O(n^{1.5}+m\sqrt{n}+(n+m)log{\sqrt{n}})$ 。。。(已经不会算了 _(:△」∠)_ )

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MO=1000000007;
const int N=100010;
const int M=100010;
int len;
int po[N][105];
int cnt[N],has[N];
int a[N],anss[M];
multiset<int> ss;

namespace fastIO {
    #define BUF_SIZE 100000
    //fread -> read
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if(p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    inline void read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror)
            return;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
    #undef BUF_SIZE
};

struct Query {
    int L, R, k, ID, block;
    Query() {}
    Query(int l, int r, int k, int ID):L(l), R(r), k(k), ID(ID) {
        block = l / len;
    }
    bool operator < (const Query &rhs) const {
        if(block == rhs.block) return R < rhs.R;
        return block < rhs.block;
    }
} queries[M];

inline void insert(int n)
{
    --has[cnt[n]];
    if (cnt[n]>len) {
        ss.erase(ss.find(cnt[n]));
    }
    ++cnt[n];
    ++has[cnt[n]];
    if (cnt[n]>len) {
        ss.insert(cnt[n]);
    }
}

inline void erase(int n)
{
    --has[cnt[n]];
    if (cnt[n]>len) {
        ss.erase(ss.find(cnt[n]));
    }
    --cnt[n];
    ++has[cnt[n]];
    if (cnt[n]>len) {
        ss.insert(cnt[n]);
    }
}

int main()
{
    int T;
    fastIO::read(T);
    for (int i=1;i<=100000;i++) {
        po[i][0]=1;
        for (int j=1;j<=100;j++) {
            po[i][j]=1LL*po[i][j-1]*i%MO;
        }
    }
    while (T--) {
        int n, m;
        fastIO::read(n);
        fastIO::read(m);
        len = sqrt(n);
        for(int i = 1; i <= n; i++) {
            fastIO::read(a[i]);
        }
        for(int i = 1; i <= m; i++) {
            int l,r,k;
            fastIO::read(l);
            fastIO::read(r);
            fastIO::read(k);
            queries[i] = Query(l, r, k, i);
        }
        sort(queries + 1, queries + m + 1);
        int L = 1, R = 1;
        memset(cnt,0,sizeof(cnt));
        memset(has,0,sizeof(has));
        cnt[a[1]]=1;
        has[1]=1;
        ss.clear();
        for(int i = 1; i <= m; i++) {
            Query &qi = queries[i];
            while(R < qi.R) insert(a[++R]);
            while(L > qi.L) insert(a[--L]);
            while(R > qi.R) erase(a[R--]);
            while(L < qi.L) erase(a[L++]);
            ll ans = 0;
            for (int j=1;j<=len;j++) {
                ans+=1LL*has[j]*po[j][qi.k]%MO;
                ans%=MO;
            }
            for (int x:ss) {
                ans+=po[x][qi.k];
                ans%=MO;
            }
            anss[qi.ID]=ans;
        }
        for(int i = 1; i <= m; i++) {
            printf("%d\n",anss[i]);
        }
    }
    return 0;
}

尾巴

特别鸣谢 Claris！！