一道神奇的分块题
题意：
给出长度为n的序列a，和m个询问，每次询问区间[l,r]内出现次数第k大的数的出现次数（注意：是出现次数第k大，不是第k大元素的出现次数），且强制在线。
题解：
可参考官方题解：https://ac.nowcoder.com/acm/problem/blogs/204649
如果是第k大元素的出现次数，那就是主席树的裸题了，开n个权值线段树，第i个维护前i个数信息，然后用前缀和思想处理在线区间询问就行了
但是，本题是无法使用线段树维护住的，因此就需要看别人的AC代码使用 暴力+优化 方法过这道题，具体实现应该是 预处理+分块+莫队的一点点思想（其实我自己还没整明白），但我所了解的莫队基本上都是离线做法。。所以这题还需要提前预处理，也就是需要提前预处理出pre[i][j]数组，代表前i个块中j这个元素的出现次数，这是为了方便分块时对于中间整块的处理
更具体的，本题需要开一个桶统计每个数的出现次数，同时还需要统计某个出现次数的数的个数，通过莫队思想更新，但是仅仅这样似乎复杂度还是不够（因为强制在线，所以无法用莫队的玄学排序），因此还需要预处理一些分块数组的信息，这样对于区间很大的询问的处理速度就加快了（应该吧）
对于每一次[l,r]询问，类似普通分块一样 先定位两端点所在块，如果在同一块中，就暴力更新该区间的数的所有信息，更新完后，再查找k大出现次数，这里需要仔细解释一下如何查找：
本题的分块数组有两个作用，除了记录每个元素所在的块之外，还可以用它来记录不同的出现次数所在的块（类似于权值线段树？或者叫做值域分块），出现次数越多，所在的块就越靠后，那么对于每一次的询问，我们就需要从最后一个块开始往第一块遍历（因为越靠后的块对应的出现次数越多），如果当前块所对应的的出现次数小于k，那么就让k减去当前块的出现次数数，然后继续查找前一块，否则就说明这个k大的出现次数在这个块里面，于是进入该块，暴力查找即可
对于不在同一块中的两端点，左右端点对应的零散块也是同上暴力处理，对于中间的完整快，需要利用之前的预处理，$O(1)$得到完整块内的数的素有信息，然后更新即可
在处理完上述所有信息并完成一次查询后，记得要把这些用到的桶和数组归零，以便下一次查询
另外，代码里有个注意点
- 用emplace_back代替了push_back，否则会TLE（91分）？？具体可以百度这两者的区别
个人感觉本题题的思想和 洛谷 P1903 [国家集训队]数颜色 / 维护队列 这道题有一点类似（不会的可以先看看这题找找自信）
最后，本蒟蒻写得很乱，如果看不懂的话 就看看代码理解理解吧！QAQ
更具体的可以看代码
AC代码：
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| #include <bits/stdc++.h>
typedef long long ll;
using namespace std;
inline char _nc(){
static char buf[100000],*L=buf,*R=buf;
return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;
}
template<class T> void read(T &x) {
x=0;int f=0;char ch=_nc();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=_nc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=_nc();}
x=f?-x:x;
return;
}
inline void write(ll x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,m,type,mx,sz;
int block[100005],L[100005],R[100005],a[100005],cnt[100005],num[100005],sum[405],pre[405][100005];
bool vis[100005];
vector<pair<int,int>> v[340][340];
vector<int> ve;
void add(int x,int number){
int bo=block[x];
num[x]+=number;
sum[bo]+=number;
}
int query(int k){
for (int i=mx;i>=1;i--){
if(k>sum[i]) k-=sum[i];
else{
for (int j=R[i];j>=L[i];j--){
if(k>num[j]) k-=num[j];
else return j;
}
}
}
return 0;
}
int cal(int l,int r,int k){
if(l>r) swap(l, r);
int ans=0;
int bol=block[l],bor=block[r];
if(bol==bor){
for (int i=l;i<=r;i++){
cnt[a[i]]++;
vis[a[i]]=true;
}
for (int i=l;i<=r;i++){
if(vis[a[i]]){
vis[a[i]]=false;
add(cnt[a[i]],1);
}
}
ans=query(k);
for (int i=l;i<=r;i++){
if(!cnt[a[i]]) continue;
add(cnt[a[i]],-1);
cnt[a[i]]=0;
}
}else{
for (auto x:v[bol+1][bor-1]) add(x.first,x.second);
for (int i=l;i<=R[bol];i++){
cnt[a[i]]++;
vis[a[i]]=true;
}
for (int i=L[bor];i<=r;i++){
cnt[a[i]]++;
vis[a[i]]=true;
}
for (int i=l;i<=R[bol];i++){
if(vis[a[i]]){
int res=pre[bor-1][a[i]]-pre[bol][a[i]];
add(res,-1);
add(res+cnt[a[i]],1);
vis[a[i]]=false;
}
}
for (int i=L[bor];i<=r;i++){
if(vis[a[i]]){
int res=pre[bor-1][a[i]]-pre[bol][a[i]];
add(res,-1);
add(res+cnt[a[i]],1);
vis[a[i]]=false;
}
}
ans=query(k);
for (auto x:v[bol+1][bor-1]) add(x.first,-x.second);
for (int i=l;i<=R[bol];i++){
if(cnt[a[i]]){
int res=pre[bor-1][a[i]]-pre[bol][a[i]];
add(res,1);
add(res+cnt[a[i]],-1);
cnt[a[i]]=0;
}
}
for (int i=L[bor];i<=r;i++){
if(cnt[a[i]]){
int res=pre[bor-1][a[i]]-pre[bol][a[i]];
add(res,1);
add(res+cnt[a[i]],-1);
cnt[a[i]]=0;
}
}
}
return ans;
}
int main()
{
read(n),read(m),read(type);
mx=sqrt(n);
for(int i=1;i<=mx;i++){
L[i]=R[i-1]+1;
R[i]=n/mx*i;
}
R[mx]=n;
for(int i=1;i<=mx;i++){
for(int j=L[i];j<=R[i];j++)
block[j]=i;
}
for (int i=1;i<=n;i++) read(a[i]);
for (int l=1;l<=mx;l++){
ve.clear();
for (int i=1;i<=n;i++) pre[l][i]=pre[l-1][i];
for (int i=L[l]; i<=R[l];i++) pre[l][a[i]]++;
for (int r=l; r<=mx;r++){
for (int i=L[r];i<=R[r];i++){
num[cnt[a[i]]]--;
cnt[a[i]]++;
num[cnt[a[i]]]++;
if(num[cnt[a[i]]]==1) ve.emplace_back(cnt[a[i]]);
}
for (auto x:ve) if(num[x]!=0&&!vis[x]) v[l][r].emplace_back(make_pair(x,num[x])),vis[x]=true;
for (auto x:ve) vis[x]=false;
}
memset(cnt,0,sizeof(cnt));
memset(num,0,sizeof(num));
}
int ans=0;
for (int i=1,l,r,k;i<=m;i++){
read(l),read(r),read(k);
if(type==1) l^=ans,r^=ans,k^=ans;
ans=cal(l,r,k);
write(ans);
puts("");
}
return 0;
}
|