附加题2

(第一篇题解)
询问区间内出现K次的数字有多少个，比赛的时候看到这个题想起主席树 (然而我主席树并不熟),比完赛才知道这个题是可以用莫队解的，所以去学了莫队。

莫队是一种优雅的暴力算法，结合分块降低时间复杂度
本题我转移区间内信息的方法为:
1、vis[]数组：vis[i]保存区间内股票i出现多少次
2、res[]数组：res[i]保存区间内出现i次的股票有多少张
3、有这两个数组接下来考虑问题区间左端点小于枚举的l的情况，此时需要向左枚举并用vis[]数组记录票出现次数，将此时股票新增的出现次数记录到res[]数组里面，并将更新vis[]数组之前的res[]数组中记录的旧影响减掉。
4、问题区间右端点大于枚举的r时同理
5、考虑区间左端点大于枚举的l的情况，此时需要向右减掉所有多余的影响,将此时股票的出现次数减小并记录到res[]数组里面，并将更新vis[]数组之前的res[]数组中记录的旧影响减掉。(注意两次的旧影响不一样，因为一次是vis[]++,一次是vis[]--)
6、问题区间右端点小于枚举的r时同理

代码部分:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e4  + 5;
inline int read() {
    int x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
int pos[maxn],nums[maxn],vis[maxn],res[maxn];//vis数组用来保存股票出现的次数
struct node {
    int start,endd,k,idx,ans;
} sakura[maxn];
inline bool cmp1(node a,node b) {return pos[a.start] == pos[b.start] ? a.endd < b.endd : pos[a.start] < pos[b.start];}
inline bool cmp2(node a,node b) {return a.idx < b.idx; }
inline void add(int n) {vis[nums[n]]++, res[vis[nums[n]] - 1]--, res[vis[nums[n]]]++; }
inline void sub(int n) {vis[nums[n]]--, res[vis[nums[n]]]++, res[vis[nums[n]] + 1]--; }
int main() {
    int n = read(), m = read();
    int base = sqrt(n);
    for(int i = 1; i <= n; i++) nums[i] = read(), pos[i] = i / base;
    for(int i = 1; i <= m; i++) sakura[i].start = read(), sakura[i].endd = read(),sakura[i].k = read(),sakura[i].idx = i;
    sort(sakura + 1,sakura + 1 + m,cmp1);
    int l = 1,r = 0;
    for(int i = 1; i <= m; i++) {
        while(sakura[i].start < l) add(--l);
        while(sakura[i].endd  > r) add(++r);
        while(sakura[i].start > l) sub(l++);
        while(sakura[i].endd  < r) sub(r--);
        sakura[i].ans = res[sakura[i].k];
// debug 可以不管
//        cout << "=============================" << endl;
//        cout << i << "   " << sakura[i].start << "   " << sakura[i].endd << endl;
//        for(int i = 0; i <= 5; i++) printf("%d%c",res[i],i == 5 ? '\n' : ' ');
//        cout << "=============================" << endl;
    }
    sort(sakura + 1,sakura + 1 + m,cmp2);
    for(int i = 1; i <= m; i++) printf("%d\n",sakura[i].ans);
}