题意

#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}})$ 。。。(已经不会算了 _(:△」∠)_ )

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#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!!