Submission #75983534

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
//#define int long long 
typedef long long ll;
typedef __int128 LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

// sum
template<typename T>
struct Fenwick
{
	int n;
	vector<T> tr;

	explicit Fenwick(int x){
		init(x);
	}

	void init(int x){
		n = x;
		tr.resize(x + 1);
	}

	int lowbit(int x){
		return x & -x;
	}

	void add(int x, T k){
		for (int i = x; i <= n; i += lowbit(i))
			tr[i] += k;
	}

	T querysum(int x){
		T res = 0;
		for (int i = x; i; i -= lowbit(i))
			res += tr[i];
		return res;
	}

	void clear_(){
		for(int i = 0; i <= n; i ++) tr[i] = 0;
	}
};


const int mod = 998244353;

// sum
template<typename T>
struct SegmentTree
{
    #define lc p<<1
    #define rc p<<1|1
    
    struct Node
    {
        int l, r;
        T mul;
    };

    vector<Node> tr;
    
    explicit SegmentTree(int l, int r){
        tr.resize(4 * (r + 1));
        build(1, l, r);
    }

    void _pushup(int p){
        tr[p].mul = tr[lc].mul * tr[rc].mul % mod;
    }

    void build(int p, int l, int r)
    {
        tr[p] = {l,r,1};
        if (l == r) return;
        int mid = l + r >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        _pushup(p);
    }

    void update(int p, int x, T v)
    {
        if (tr[p].l == tr[p].r)
        {
            tr[p].mul = tr[p].mul * v % mod;
            return;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        if (x <= mid) update(lc, x, v);
        else update(rc, x, v);
        _pushup(p);
    }

    T query(int p, int l, int r)
    {
        if (l <= tr[p].l && tr[p].r <= r)
            return tr[p].mul;
        int mid = tr[p].l + tr[p].r >> 1;
        T res = 1;
        if (l <= mid) res = res * query(lc, l, r) % mod;
        if (r > mid) res = res * query(rc, l, r) % mod;
        return res;
    }
};
SegmentTree<ll> seg(1, 250000);

ll qpow(ll a, ll b, int p)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}
ll inv[250005];
ll fact[250005];

int bi[250005], bl[1005], br[1005];
ll ans[250005];
int cnt[250005];

struct Query{
    int l, r, x, id;
}qry[250005];
bool cmp(Query a, Query b){
    if(bi[a.l] == bi[b.l]){
        if(bi[a.l] & 1) return a.r < b.r;
        else return a.r > b.r;
    }
    else{
        return bi[a.l] < bi[b.l];
    }
}
Fenwick<int> bit(250001);
void del(int x){
    // cout << "add " << x << "\n";
    bit.add(x, -1);
    seg.update(1, x, inv[cnt[x]]);
    cnt[x] --;
}
void add(int x){
    // cout << "del " << x << "\n";
    bit.add(x, 1);
    cnt[x] ++;
    seg.update(1, x, cnt[x]);
}

int n, q;
int a[250005];

void solve()
{
    cin >> n >> q;
    fact[0] = 1;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        inv[i] = qpow(i, mod - 2, mod);
        fact[i] = fact[i - 1] * i % mod;
    }
    const int blen = sqrt(n);
    const int bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i ++){
        bi[i] = (i - 1) / blen + 1;
    }
    for(int i = 1; i <= bcnt; i ++){
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(n, i * blen);
    }
    for(int i = 1; i <= q; i ++){
        int l, r, x;
        cin >> l >> r >> x;
        qry[i] = {l, r, x, i};
    }
    sort(qry + 1, qry + 1 + q, cmp);
    // cout << "OK\n";
    // return;
    int winl = 1, winr = 0;
    for(int i = 1; i <= q; i ++){
        auto [l, r, x, id] = qry[i];
        // cerr << l << " " << r << " " << x << " " << id << ":\n";
        while(winl > l) add(a[--winl]);
        while(winr < r) add(a[++winr]);
        while(winl < l) del(a[winl++]);
        while(winr > r) del(a[winr--]);
        if(x == 1) ans[id] = 1;
        else ans[id] = fact[bit.querysum(x - 1)] * qpow(seg.query(1, 1, x - 1), mod - 2, mod) % mod;
    }
    for(int i = 1; i <= q; i ++){
        cout << ans[i] << "\n";
    }
}


signed main()
{
//  freopen("in.txt", "rt", stdin);
//  freopen("out.txt", "wt", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    // int T=1; cin>>T; while(T--)
    solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In instantiation of 'void SegmentTree<T>::update(int, int, T) [with T = long long int]':
./Main.cpp:150:15:   required from here
  150 |     seg.update(1, x, inv[cnt[x]]);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
./Main.cpp:97:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
./Main.cpp: In instantiation of 'T SegmentTree<T>::query(int, int, int) [with T = long long int]':
./Main.cpp:198:66:   required from here
  198 |         else ans[id] = fact[bit.querysum(x - 1)] * qpow(seg.query(1, 1, x - 1), mod - 2, mod) % mod;
      |                                                         ~~~~~~~~~^~~~~~~~~~~~~
./Main.cpp:107:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |         int mid = tr[p].l + tr[p].r >> 1;
      |                   ~~~~~~~~^~~~~~~~~
./Main.cpp: In instantiation of 'void SegmentTree<T>::build(int, int, int) [with T = long long int]':
./Main.cpp:73:9:   required from 'SegmentTree<T>::SegmentTree(int, int) [with T = long long int]'
   73 |         build(1, l, r);
      |         ^~~~~
./Main.cpp:114:30:   required from here
  114 | SegmentTree<ll> seg(1, 250000);
      |                              ^
./Main.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~

Judge Result