Submission #65690725

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;
}
struct Query {
    int l, r, x, idx;
    int bl, br, bx;
};
int main(){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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;
}

struct Query {
    int l, r, x, idx;
    int bl, br, bx;
};

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<Query> qs(Q);
    int B = pow(N, 2.0/3);
    for(int i=0;i<Q;i++){
        cin>>qs[i].l>>qs[i].r>>qs[i].x;
        qs[i].idx = i;
        qs[i].bl = qs[i].l / B;
        qs[i].br = qs[i].r / B;
        qs[i].bx = qs[i].x;
    }
    sort(qs.begin(), qs.end(), [&](auto &a, auto &b){
        if(a.bl != b.bl) return a.bl < b.bl;
        if(a.br != b.br) return a.br < b.br;
        return a.bx < b.bx;
    });
    vector<vector<int>> pos(N+2);
    for(int i=1;i<=N;i++){
        pos[A[i]].push_back(i);
    }
    vector<ll> inv(N+2);
    for(int i=1;i<=N;i++) inv[i] = modpow(i);
    vector<ll> ans(Q);
    vector<int> cnt(N+2,0);
    int curL=1, curR=0, curX=1;
    ll curAns=1;
    int csz=0;
    auto addFreq = [&](int v){
        ll old = cnt[v];
        curAns = curAns * (csz+1) % MOD * inv[old+1] % MOD;
        cnt[v]++; csz++;
    };
    auto remFreq = [&](int v){
        ll old = cnt[v];
        curAns = curAns * inv[csz] % MOD * old % MOD;
        cnt[v]--; csz--;
    };
    auto addPos = [&](int i){
        if(A[i] < curX) addFreq(A[i]);
    };
    auto remPos = [&](int i){
        if(A[i] < curX) remFreq(A[i]);
    };
    auto incX = [&](){
        for(int p: pos[curX]){
            if(curL <= p && p <= curR) addFreq(curX);
        }
        curX++;
    };
    auto decX = [&](){
        curX--;
        for(int p: pos[curX]){
            if(curL <= p && p <= curR) remFreq(curX);
        }
    };
    for(auto &q: qs){
        while(curX < q.x) incX();
        while(curX > q.x) decX();
        while(curL > q.l) addPos(--curL);
        while(curR < q.r) addPos(++curR);
        while(curL < q.l) remPos(curL++);
        while(curR > q.r) remPos(curR--);
        ans[q.idx] = curAns;
    }
    for(ll v: ans) cout << v << "\n";
    return 0;
}

Submission Info

Judge Result