Submission #65692386

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
ll modpow(ll a, ll e=MOD-2){
    ll r = 1;
    while(e){
        if(e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N+1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

ll modpow(ll a, ll e=MOD-2){
    ll r = 1;
    while(e){
        if(e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N+1);
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    vector<ll> fact(N+1), inv_fact(N+1);
    fact[0] = 1;
    for(int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[N] = modpow(fact[N]);
    for(int i = N; i >= 1; i--) inv_fact[i-1] = inv_fact[i] * i % MOD;

    vector<vector<int>> pos(N+1);
    for(int i = 1; i <= N; i++){
        pos[A[i]].push_back(i);
    }

    struct Query { int l, r, x, id; };
    vector<Query> qs(Q);
    for(int i = 0; i < Q; i++){
        cin >> qs[i].l >> qs[i].r >> qs[i].x;
        qs[i].id = i;
    }

    int B = max(1, (int)pow(N, 2.0/3));
    sort(qs.begin(), qs.end(), [&](auto &a, auto &b){
        int ab = a.l / B, bb = b.l / B;
        if(ab != bb) return ab < bb;
        int ar = a.r / B, br = b.r / B;
        if(ar != br) return ar < br;
        return a.x < b.x;
    });

    vector<ll> ans(Q);
    vector<int> cnt(N+1, 0);
    ll curMul = 1;
    int curSize = 0;
    int L = 1, R = 0, X = 1;

    auto add_val = [&](int v){
        int old = cnt[v], nw = old + 1;
        curMul = curMul * inv_fact[nw] % MOD * fact[old] % MOD;
        cnt[v] = nw;
        curSize++;
    };
    auto rem_val = [&](int v){
        int old = cnt[v], nw = old - 1;
        curMul = curMul * inv_fact[nw] % MOD * fact[old] % MOD;
        cnt[v] = nw;
        curSize--;
    };
    auto add_pos = [&](int i){
        int v = A[i];
        if(v < X) add_val(v);
    };
    auto rem_pos = [&](int i){
        int v = A[i];
        if(v < X) rem_val(v);
    };
    auto incX = [&](){
        for(int p: pos[X]){
            if(L <= p && p <= R) add_val(X);
        }
        X++;
    };
    auto decX = [&](){
        X--;
        for(int p: pos[X]){
            if(L <= p && p <= R) rem_val(X);
        }
    };
    for(auto &q: qs){
        while(X < q.x) incX();
        while(X > q.x) decX();
        while(L > q.l) add_pos(--L);
        while(R < q.r) add_pos(++R);
        while(L < q.l) rem_pos(L++);
        while(R > q.r) rem_pos(R--);
        ans[q.id] = fact[curSize] * curMul % MOD;
    }
    for(ll v: ans){
        cout << v << "\n";
    }
    return 0;
}

Submission Info

Judge Result