Ta sẽ chia dãy thành $\sqrt{n}$ block kế nhau.
Gọi $mode(i,j)$ là đáp án cho 1 dãy gồm các block liên tiếp từ block i đến block j.
Ta có thể tính được đáp án cho 1 dãy gồm nhiều block riêng tiếp trong $o(n$ $\times$ $\sqrt{n})$.
Gọi $id(i)$ là chỉ số block của phần tử $i$.
Ta có 2 nhận xét như sau :
1. "Đáp án sẽ không vượt quá $\sqrt{n}$ $\times$ $2$ $+$ $mode(id(l)+1,id(r)-1)$". Bạn đọc có thể tự chứng minh.
2. "Đáp án hoặc là $mode(id(l)+1,id(r)-1)$ hoặc là số lần xuất hiện trong đoạn $l$$\dots$$r$ của 1 phần tử nào đấy trong 2 phần dư".
Vậy thì từ nhận xét, ta có thuật toán như sau :
Đầu tiên, ta cần tính trước $mode(i,j)$ cho mọi cặp chỉ số block $i,j$ $(i<j)$.
Với mỗi truy vấn ta sẽ có 2 dạng :
1. $l$ và $r$ thuộc 2 block kề nhau hoặc chung 1 block, ta có thể duyệt trâu từ l đến r rồi dùng 1 mảng đếm để tìm đáp án.
2. Giữa $l$ và $r$ có ít nhất 1 block :
+ Đầu tiên, ta sẽ đánh số cho mỗi phần tử $a(i)$ là thứ tự xuất hiện giá trị $a(i)$ trong mảng.
+ Tiếp theo, ta đặt $ans =$ $mode(id(l)+1,id(r)-1)$
+ Sau đó, với mỗi phần tử $a(i)$ nằm ở phần dư bên phải, ta sẽ nhảy đến phần tử mang giá trị $a(i)$ và xuất hiện thứ $j = i - ans$ trong mảng, sau đấy ta duyệt trâu: nếu chỉ số mảng của phần tử này vẫn thuộc $l$$\dots$$r$ thì ta cập nhật :
+ j-=1, ans++;
+ Tương tự với phần dư bên trái nhưng ta lấy $j = i + ans$ và cập nhật j += 1.
+ sau khi duyệt hết 2 phần dư thì ans sẽ là đáp án của truy vấn.
Độ phức tạp của thuật toán sẽ là :
1. Do ta duyệt trâu nên sẽ tốn tối đa $2$ $\times$ $\sqrt{n}$ lần duyệt cho mỗi truy vấn.
2. Thoạt nhìn, thuật toán có thể lên tới $O(n)$ cho mỗi truy vấn. Nhưng từ nhận xét (1) thì số lần duyệt tăng lên chỉ tối đa là $2$ $\times$ $\sqrt{n}$.
Vậy độ phức tạp cho bài toán là $O($$\sqrt{n}$ $\times$ $n)$
Code mẫu :
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second
#define TASK "main"
#define all(x) (x).begin(x),(x).end()
#define pll pair<ll,ll>
const int nmax = 2e5 + 6;
const int sz = 450;
vector<int> pos[nmax];
int b[nmax]; // thứ tự xuất hiện của a[i] trong mảng.
ll a[nmax];
int c[nmax];
ll mode[sz + 6][sz+6];
ll BL;
int n ,q;
int cnt[nmax];
int fastdiv[nmax];
inline void maxi(ll &a,ll b){
a = max(a,b);
}
void preprocess(){
for(int i =1;i<= BL;++i){
int mx = 0;
memset(cnt,0 ,sizeof cnt);
for(int j = min(n-1,i * sz - 1);j>=0;--j){
cnt[a[j]] ++;
mx = max(mx,cnt[a[j]]);
// cout << j << ' ';
mode[fastdiv[j]][i] = mx;
}
}
memset(cnt,0,sizeof cnt);
}
int query(int l,int r){
int l1 = fastdiv[l] + 1;
int r1 = fastdiv[r] - 1;
int ans = 0 ;
if(l1 > r1){
// Trường hợp 1
for(int i = l;i<=r;++i){
cnt[a[i]] ++;
ans = max(ans,cnt[a[i]]);
}
for(int i = l;i<=r;++i){
cnt[a[i]] = 0;
}
} else {
// trường hợp 2
ans = mode[l1][r1];
for(int i = r1*sz;i<=r;++i){
int j = b[i] - ans;
while(j >= 0 && pos[a[i]][j] >= l){
++ans;
--j;
}
}
for(int i = l;i<(l1-1)*sz;++i){
int j = b[i] + ans;
while(j < pos[a[i]].size() && pos[a[i]][j] <= r) {
++ans;
++j;
}
}
}
return ans;
}
void solve(){
cin >> n >> q;
for(int i = 0;i<n;i++){
cin >> a[i];
b[i] = pos[a[i]].size();
// lưu trữ tất cả chỉ số của các phần tử có chung giá trị
pos[a[i]].push_back(i);
}
BL = n / sz + (n%sz != 0);
for(int i = 0;i<=n;++i){
fastdiv[i] = i / sz + 1;
}
preprocess();
int lastans = 0;
while(q--){
int l,r;
cin >> l >> r;
l = (lastans +l)%n +1;
r = (lastans + r)%n + 1;
--l,--r;
if(l>r) swap(l,r);
lastans = query(l,r);
cout << lastans << '\n';
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
if(fopen(TASK ".inp","r")){
freopen(TASK ".inp","r",stdin);
freopen(TASK ".out","w",stdout);
}
solve();
}
```
lenhanbo
Created at
11 likes