记录编号	614834	评测结果	AAAAAAAAAA
题目名称	[HSOI 2019] HS的新题	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	3.954 s
提交时间	2026-04-17 13:57:23	内存使用	8.88 MiB

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, mod = 998244353;
struct node {
    mutable ll v;
    int l, r;
    node(int a, int b, ll c) {
        l = a;
        r = b;
        v = c;
    }
    bool operator<(const node& y) const { return l < y.l; }
};
set<node> s;
auto split(int x) {
    auto it = s.lower_bound(node(x, 0, 0));
    if (it != s.end() && it->l == x) return it;
    it--;
    int l = it->l, r = it->r, v = it->v;
    s.erase(it);
    s.insert(node(l, x - 1, v));
    return s.insert(node(x, r, v)).first;
}
void assign(int l, int r, ll x) {
    auto itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, x));
}
int a[N];
ll ksm(ll x, int y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
void s2(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        itl->v = ksm(itl->v, mod - 2);
    }
}
void s3(int l, int r, ll x) {
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        itl->v = itl->v * x % mod;
    }
}
int s4(int l, int r, int x, int y) {
    auto itr = split(r + 1), itl = split(l);
    int ans = 0;
    for (; itl != itr; itl++) {
        ll* v = &itl->v;
        if (x <= *v && *v <= y) {
            ans += itl->r - itl->l + 1;
        }
    }
    return ans;
}
void s5(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    ll sum = 0;
    for (; itl != itr; itl++) {
        sum += itl->v * (itl->r - itl->l + 1) % mod;
        sum %= mod;
    }
    assign(l, r, sum * ksm(r - l + 1, mod - 2) % mod);
}
int s6(int l, int r) {
    map<int, int> mp;
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        mp[itl->v] += itl->r - itl->l + 1;
    }
    int now = 0, cnt = 0;
    for (auto i = mp.begin(); i != mp.end(); i = next(i)) {
        if (i->second > cnt) {
            now = i->first;
            cnt = i->second;
        }
    }
    return now;
}
int s7(int l, int r) {
    set<int> st;
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        st.insert(itl->v);
    }
    return st.size();
}
int s8(int l, int r) {
    // return -1;
    int p[40] = {0};
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl++) {
        // for (int _ = itl->l; _ <= itl->r; _++) {
        int x = itl->v;
        for (int i = 31; i >= 0; i--) {
            if (x >> i & 1) {
                if (p[i] == 0) {
                    p[i] = x;
                    break;
                }
                x ^= p[i];
            }
        }
        // }
    }
    int ans = 0;
    for (int i = 31; i >= 0; i--) {
        ans = max(ans, ans ^ p[i]);
    }
    return ans % mod;
}
int main() {
    int n, m;
    cin >> n >> m;
    s.insert(node(1, n, 0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        assign(i, i, a[i]);
    }
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (l > r) swap(l, r);
        if (op == 1) {
            int x;
            cin >> x;
            assign(l, r, x);
        }
        if (op == 2) {
            s2(l, r);
        }
        if (op == 3) {
            int x;
            cin >> x;
            s3(l, r, x);
        }
        if (op == 4) {
            int x, y;
            cin >> x >> y;
            cout << s4(l, r, x, y) << endl;
        }
        if (op == 5) {
            s5(l, r);
        }
        if (op == 6) {
            cout << s6(l, r) << endl;
        }
        if (op == 7) {
            cout << s7(l, r) << endl;
        }
        if (op == 8) {
            cout << s8(l, r) << endl;
        }
    }
    return 0;
}