题意：多次求区间众数的出现次数。
解：
这题居然可以莫队......
首先开个桶。然后还要开个数组，cnt[i]表示出现i次的数有多少个。
然后就可以O(1)修改了。
1 #include2 #include 3 #include 4 5 inline void read(int &x) { 6 x = 0; 7 char c = getchar(); 8 while(c < '0' || c > '9') { 9 c = getchar(); 10 } 11 while(c >= '0' && c <= '9') { 12 x = (x << 3) + (x << 1) + c - 48; 13 c = getchar(); 14 } 15 return; 16 } 17 18 const int N = 200010; 19 20 int fr[N], a[N], bin[N], cnt[N], ans, X[N]; 21 22 struct ASK { 23 int l, r, t, ans; 24 inline bool operator <(const ASK &w) const { 25 if(fr[l] != fr[w.l]) { 26 return fr[l] < fr[w.l]; 27 } 28 return r < w.r; 29 } 30 }ask[N]; 31 32 inline bool cmp(const ASK &A, const ASK &B) { 33 return A.t < B.t; 34 } 35 36 inline void add(int p) { 37 cnt[bin[a[p]]]--; 38 bin[a[p]]++; 39 cnt[bin[a[p]]]++; 40 if(bin[a[p]] > ans) { 41 ans = bin[a[p]]; 42 } 43 return; 44 } 45 46 inline void del(int p) { 47 cnt[bin[a[p]]]--; 48 bin[a[p]]--; 49 cnt[bin[a[p]]]++; 50 if(!cnt[bin[a[p]] + 1] && ans == bin[a[p]] + 1) { 51 ans--; 52 } 53 return; 54 } 55 56 int main() { 57 int n, m; 58 read(n); 59 read(m); 60 int T = sqrt(n); 61 for(int i = 1; i <= n; i++) { 62 read(a[i]); 63 X[i] = a[i]; 64 fr[i] = (i - 1) / T + 1; 65 } 66 for(int i = 1; i <= n; i++) { 67 read(ask[i].l); 68 read(ask[i].r); 69 ask[i].t = i; 70 } 71 std::sort(X + 1, X + n + 1); 72 std::sort(ask + 1, ask + m + 1); 73 int temp = std::unique(X + 1, X + n + 1) - X - 1; 74 for(int i = 1; i <= n; i++) { 75 a[i] = std::lower_bound(X + 1, X + temp + 1, a[i]) - X; 76 } 77 78 int l = 1, r = 1; 79 ans = 1; 80 bin[a[1]]++; 81 cnt[1] = 1; 82 for(int i = 1; i <= m; i++) { 83 while(l > ask[i].l) { 84 add(--l); 85 } 86 while(r < ask[i].r) { 87 add(++r); 88 } 89 while(l < ask[i].l) { 90 del(l++); 91 } 92 while(r > ask[i].r) { 93 del(r--); 94 } 95 ask[i].ans = ans; 96 } 97 98 std::sort(ask + 1, ask + m + 1, cmp); 99 for(int i = 1; i <= m; i++) {100 printf("%d\n", -ask[i].ans);101 }102 return 0;103 }