Submission #65693330

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 MAXN = 250000;
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;
}
inline ll hilbert(int x, int y, int pow=18, ll rot=0){
    if(pow==0) return 0;
    int h = 1<<(pow-1);
    int seg = ((x<h)?0:1) + ((y<h)?0:2);
    seg = (seg+rot)&3;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 250000;
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;
}

inline ll hilbert(int x, int y, int pow=18, ll rot=0){
    if(pow==0) return 0;
    int h = 1<<(pow-1);
    int seg = ((x<h)?0:1) + ((y<h)?0:2);
    seg = (seg+rot)&3;
    static const ll dr[4]={3,0,0,1};
    int nx = x&(h-1), ny = y&(h-1);
    ll sub = hilbert(nx,ny,pow-1,(rot+dr[seg])&3);
    return seg*(1LL<<(2*pow-2)) + ((seg&1)?sub:((1LL<<(2*pow-2))-sub-1));
}

int N,Q;
int A[MAXN+2], cnt[MAXN+2];
vector<int> pos[MAXN+2];
ll fact[MAXN+2], inv_fact[MAXN+2];
struct Qry{int l,r,x,id; ll ord;} qs[MAXN+2];
ll ans[MAXN+2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        cin>>A[i];
        pos[A[i]].push_back(i);
    }
    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;
    for(int i=0;i<Q;i++){
        cin>>qs[i].l>>qs[i].r>>qs[i].x;
        qs[i].id=i;
        qs[i].ord = hilbert(qs[i].l, qs[i].r);
    }
    sort(qs, qs+Q, [&](auto &a, auto &b){ return a.ord<b.ord; });
    int L=1, R=0, X=1, sz=0;
    ll denom=1;
    auto add = [&](int v){
        int c=cnt[v]++;
        denom = denom * inv_fact[c+1] % MOD * fact[c] % MOD;
        sz++;
    };
    auto rem = [&](int v){
        int c=cnt[v]--;
        denom = denom * inv_fact[c-1] % MOD * fact[c] % MOD;
        sz--;
    };
    for(int i=0;i<Q;i++){
        auto &q=qs[i];
        while(X<q.x){
            for(int p:pos[X]) if(L<=p&&p<=R) add(X);
            X++;
        }
        while(X>q.x){
            X--;
            for(int p:pos[X]) if(L<=p&&p<=R) rem(X);
        }
        while(L>q.l) if(A[--L]<X) add(A[L]);
        while(R<q.r) if(A[++R]<X) add(A[R]);
        while(L<q.l) if(A[L++]<X) rem(A[L-1]);
        while(R>q.r) if(A[R--]<X) rem(A[R+1]);
        ans[q.id] = fact[sz] * denom % MOD;
    }
    for(int i=0;i<Q;i++) cout<<ans[i]<<"\n";
    return 0;
}

Submission Info

Judge Result