PopHirasawa's Blog 这里可以转到Wiki哦HomeArchivesTagsCategoriesLinksAbout
维护区间众数
|算法
Word count: 985|Reading time: 4 min

这玩意好像方法挺多的，然后今天被一个阴间东西坑了，来说一哈

其实就是给一个数列，然后给一堆询问，问你区间众数是多少吧

首先先把我之前的复制一手啊

绝对众数问题

就是出现个数超过n/2的众数

这个我们可以用一个摩尔投票的方法来写捏

摩尔投票

首先考虑一个序列，里面两两取数，如果一样就留下，不一样就两个数都消掉，那么最后留下的数肯定就是数量超过n/2的数

实现的话，用两个变量cur和cnt，如果当前的数和cur不同且cnt==0 cur变为当前数，否则cnt–

如果相同 cnt++

最后cur就是唯一有可能是绝对众数的数，然后跑一遍确认即可

1
2
3
4
5
6
7
8
9
10
11
12
ll dat[maxn];
ll majorityElement(){
    ll cnt=1,cur=dat[0];
    for(int i=1;i<n;i++){
        if(dat[i]!=cnt)cnt--;
        else cnt++;
        if(cnt<0){
            cut=dat[i];
            cnt=0;
        }
    }
}

如果是n/3以至于n/k 其实就是设置多组cur和cnt就行

然后我们就能用线段树来维护了捏

线段树维护

无论如何产生的绝对众数唯一可能就是左右子区间cur中的一个

如果cur1==cur2 新的区间cur3=cur1 ，cnt3=cnt1+cnt2

如果不同 cur3为两段中cnt较大的一个，且cnt3为两段之差

然后查的时候只要查出来cur然后跑一遍二分查区间内个数就能确定了

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
struct  node
{
    ll num, c;
};
ll n, q, k;
node dat[300001<<2];
ll a[300000 + 5];
ll l, r;
vector<ll> pos[300000 + 5];
node merge(node x, node y) {
    if (x.num == y.num) return(x.num, x.c + y.c);
    else if (x.c < y.c) return{ y.num,y.c - x.c };
    else return { x.num,x.c - y.c };
}
void pushup(ll o) {
    ll ls = o << 1, rs = o << 1 | 1;
    dat[o] = merge(dat[ls], dat[rs]);
}
void build(ll o, ll l, ll r) {
    ll ls = o << 1, rs = o << 1 | 1;
    if (l == r) { dat[o] = { a[l],1 }; return; }
    ll m = l + r >> 1;
    build(ls, l, m);
    build(rs, m + 1, r);
    pushup(o);
}
node ask(ll o, ll l, ll r, ll p, ll q) {
    ll ls = o << 1, rs = o << 1 | 1;
    if (p<= l && q >= r)return dat[o];
    ll m = l + r >> 1;
    if (q <= m)return ask(ls, l, m, p, q);
    if (p > m)return ask(rs, m + 1, r, p, q);
    return merge(ask(ls, l, m, p, q), ask(rs, m + 1, r,p, q));
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n>>q;
    srand(time(NULL));
    ll tmp;
    for (int i = 1; i <=n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    build(1, 1, n);
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        ll tmp=ask(1, 1, n, l, r).num;
        ll ans = upper_bound(pos[tmp].begin(), pos[tmp].end(), r) - lower_bound(pos[tmp].begin(), pos[tmp].end(), l);
    }
}

一般的众数

这玩意方法就可多了，这里讲一个今天把我坑麻了的莫队写法捏

我们开两个数组，cnt[]和num[]，cnt[i]是单纯统计区间里边 i 的出现次数，num[i]统计出现了 i 次的数有多少个。

然后ans就应该是令num[i]不为0的最大的i

考虑到每次更新数的时候，我们其实只会影响一个点的cnt[]和num[]，因此ans只会加1或者减1，因此可以在O(1)的时间内更新捏

那么add和del函数就能这样写了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll cnt[MAXN], num[MAXN];
ll anss = 0;
void add(ll x) {
    ll p = dat[x];
    num[cnt[p]]--;
    cnt[p]++;
    num[cnt[p]]++;
    anss = max(anss, cnt[p]);
}

void del(ll x) {
     ll p = dat[x];
     num[cntt[p]]--;
     if (anss == cntt[p] && !num[anss])anss--;
     --cntt[p];
     num[cntt[p]]++;
}

本废物因为莫队学的太烂了，以至于没有想到可以用

while(l<=r)del(l++)

手动清零，天天用memset()，T到了天荒地老

小朋友们千万不要学哦

莫队线段树