Solutions of Mode

Select solution language

lenhanbo Created at 20 likes

Ta sẽ chia dãy thành

\sqrt{n}

$\sqrt{n}$ block kế nhau. Gọi

m o d e (i, j)

$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

$o(n$

\times

$\times$

\sqrt{n})

$\sqrt{n})$ . Gọi

i d (i)

$id(i)$ là chỉ số block của phần tử

i

$i$ . Ta có 2 nhận xét như sau : 1. "Đáp án sẽ không vượt quá

\sqrt{n}

$\sqrt{n}$

\times

$\times$

2

$2$

+

$+$

m o d e (i d (l) + 1, i d (r) - 1)

$mode(id(l)+1,id(r)-1)$ ". Bạn đọc có thể tự chứng minh. 2. "Đáp án hoặc là

m o d e (i d (l) + 1, i d (r) - 1)

$mode(id(l)+1,id(r)-1)$ hoặc là số lần xuất hiện trong đoạn

l

$l$

\dots

$\dots$

r

$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

m o d e (i, j)

$mode(i,j)$ cho mọi cặp chỉ số block

i, j

$i,j$

(i < j)

$(i<j)$ . Với mỗi truy vấn ta sẽ có 2 dạng : 1.

l

$l$ và

r

$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

$l$ và

r

$r$ có ít nhất 1 block : + Đầu tiên, ta sẽ đánh số cho mỗi phần tử

a (i)

$a(i)$ là thứ tự xuất hiện giá trị

a (i)

$a(i)$ trong mảng. + Tiếp theo, ta đặt

a n s =

$ans =$

m o d e (i d (l) + 1, i d (r) - 1)

$mode(id(l)+1,id(r)-1)$ + Sau đó, với mỗi phần tử

a (i)

$a(i)$ nằm ở phần dư bên phải, ta sẽ nhảy đến phần tử mang giá trị

a (i)

$a(i)$ và xuất hiện thứ

j = i - a n s

$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

$l$

\dots

$\dots$

r

$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 + a n s

$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

$2$

\times

$\times$

\sqrt{n}

$\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)

$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

$2$

\times

$\times$

\sqrt{n}

$\sqrt{n}$ . Vậy độ phức tạp cho bài toán là

O (

$O($

\sqrt{n}

$\sqrt{n}$

\times

$\times$

n)

$n)$ Code mẫu :

c p p # \in c l u d e < b i t \frac{s}{s} t d c + + . h > u \sin g n a m e s p a c e s t d; # d e f \in e l l l o n g l o n g # d e f \in e f i f i r s t # d e f \in e s c \sec o n d # d e f \in e T A S K main # d e f \in e a l l (x) (x) . b e g \in (x), (x) . e n d () # d e f \in e p l l p a i r < l l, l l > c o n s t \int n max = 2 e 5 + 6; c o n s t \int s z = 450; \vec{\to} r < \int > p o s [n max]; \int b [n max]; / t h ứ t ự x u ấ t h i ệ n c ủ a a [i] t r o n g m ả n g . l l a [n max]; \int c [n max]; l l mod e [s z + 6] [s z + 6]; l l B L; \int n, q; \int c n t [n max]; \int f * \div [n max]; \in l \in e v o i (l l & a, l l b) {a = max (a, b);} v o r e p r o c e s s () {f or (\int i = 1; i \leq B L; + + i) {\int m x = 0; m e m s e t (c n t, 0, s i z e o f c n t); f or (\int j = min (n - 1, i \cdot s z - 1); j \geq 0; - - j) {c n t [a [j]] + +; m x = max (m x, c n t [a [j]]); / c o u t 〈 j 〈''; mod e [f * \div [j]] [i] = m x;}} m e m s e t (c n t, 0, s i z e o f c n t);} \int q u e r y (\int l, \int r) {\int l 1 = f * \div [l] + 1; \int r 1 = f * \div [r] - 1; \int a n s = 0; if (l 1 > r 1) {/ T r ư ờ n g h ợ p 1 f or (\int i = l; i \leq r; + + i) {c n t [a [i]] + +; a n s = max (a n s, c n t [a [i]]);} f or (\int i = l; i \leq r; + + i) {c n t [a [i]] = 0;}} e l s e {/ t r ư ờ n g h ợ p 2 a n s = mod e [l 1] [r 1]; f or (\int i = r 1 \cdot s z; i \leq r; + + i) {\int j = b [i] - a n s; w h i \leq (j \geq 0 & & p o s [a [i]] [j] \geq l) {+ + a n s; - - j;}} f or (\int i = l; i < (l 1 - 1) \cdot s z; + + i) {\int j = b [i] + a n s; w h i \leq (j < p o s [a [i]] . s i z e () & & p o s [a [i]] [j] \leq r) {+ + a n s; + + j;}}} r e t u r n a n s;} v o o l v e () {c \in 〉 n 〉 q; f or (\int i = 0; i < n; i + +) {c \in 〉 a [i]; b [i] = p o s [a [i]] . s i z e (); / l ư u t r ữ t ấ t c ả c h ỉ s ố c ủ a c á c p h ầ n t ử c ó c h u n g g i á t r ị p o s [a [i]] . p u s h_{b} a c k (i);} B L = \frac{n}{s} z + (n % s z \neq 0); f or (\int i = 0; i \leq n; + + i) {f * \div [i] = \frac{i}{s} z + 1;} p r e p r o c e s s (); \int l * a n s = 0; w h i \leq (q - -) {\int l, r; c \in 〉 l 〉 r; l = (l * a n s + l) % n + 1; r = (l * a n s + r) % n + 1; - - l, - - r; if (l > r) s w a p (l, r); l * a n s = q u e r y (l, r); c o u t 〈 l * a n s 〈' n';}} \int m a \in () {i o s : : s y n c_{w} i t h_{s} t d i o (f a l s e); c \in . t i e (0); c o u t . t i e (0); if (f o p e n (T A S K .inp, r)) {e o p e n (T A S K .inp, r, s t d \in); e o p e n (T A S K .out, w, s t d o u t);} s o l v e ();}

$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(); }$