算法竞赛模板

H. Incessant Rain

线段树离线

一个经典的问题
然后是线段树区间合并维护区间最大子段和
记录从前缀连续最大，后缀连续最大，区间连续最大
然后合并的时候维护即可

对于某个数x的k-majority,可以把原数组转化为 等于x转化为1，否则-1，然后最大k-majority就是这一段的最大连续子段和➗2
可以离线后对不同的数分别处理

#include <bits/stdc++.h>
using namespace std;

struct node {
    int pre, suf, mx, sum;
    node(int x = 0): pre(x), suf(x), mx(x), sum(x) {}
    node operator+ (const node& b) const {
        node tmp;
        tmp.mx = max({mx, b.mx, suf + b.pre});
        tmp.sum = sum + b.sum;
        tmp.pre = max(pre, sum + b.pre);
        tmp.suf = max(b.suf, suf + b.sum);
        return tmp;
    }
};

struct seg {
    int n;
    vector<node> tree;
    void up(int p) { tree[p] = tree[p<<1] + tree[p<<1|1]; }
    seg(int _n): n(_n) { 
        tree.assign(4*n,node());
        build(1, n, 1);
    }
    void build(int l, int r, int p) {
        if (l == r) {
            tree[p] = node(-1); 
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, p<<1);
        build(mid+1,r,p<<1|1);
        up(p);
    }
    void modify(int loc, int val, int l, int r, int p) {
        if (r < loc || l > loc) return;
        if (l == loc && r == loc) {
            tree[p] = node(val);
            return;
        }
        int mid = l + r >> 1;
        modify(loc,val,l,mid,p<<1);
        modify(loc,val,mid+1,r,p<<1|1);
        up(p);
    }
    void modify(int loc, int v) { modify(loc, v, 1, n, 1); }
    int qr() { return max(tree[1].mx, 0); }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> pos1(n+1), pos2(n+1);
    for (int i = 1; i <= n; i++) pos1[a[i]].push_back(i);
    vector<vector<array<int,3>>> op(n+1);
    for (int i = 1, x, y; i <= q; i++) {
        cin >> x >> y;
        if (a[x] == y) continue;
        op[a[x]].push_back({i, x, -1});
        a[x] = y;
        op[a[x]].push_back({i, x, 1});
  
    }
    for (int i = 1; i <= n; i++) pos2[a[i]].push_back(i);
    seg tree(n);
    vector<int> init(n+1);
    vector<vector<pair<int,int>>> change(q+1);
    for (int i = 1; i <= n; i++) {
        for (auto& j : pos1[i]) tree.modify(j,1);
        int cur = tree.qr();
        init[i] = cur;
        for (auto& j : op[i]) {
            tree.modify(j[1],j[2]);
            int ncur = tree.qr();
            change[j[0]].push_back({cur,ncur});
            cur = ncur;
        }
        for (auto& j : pos2[i]) tree.modify(j, -1);
    }
    multiset<int> ms;
    for (int i = 1; i <= n; i++) ms.insert(init[i]);
    for (int i = 1; i <= q; i++) {
        for (auto& j : change[i]) {
            ms.erase(ms.find(j.first));
            ms.insert(j.second);
        }
        cout << *(prev(ms.end())) / 2 << " ";
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt;
    while (tt--) solve();
    return 0;
}