結果
問題 | No.2758 RDQ |
ユーザー |
![]() |
提出日時 | 2024-05-18 06:37:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 714 ms / 2,000 ms |
コード長 | 1,758 bytes |
コンパイル時間 | 2,341 ms |
コンパイル使用メモリ | 209,956 KB |
最終ジャッジ日時 | 2025-02-21 15:38:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; struct Mo { Mo(int _n, int _q):n(_n),q(_q){querys.reserve(_n);} void add(int l, int r){querys.emplace_back(l,r);} template<typename ExL,typename ExR, typename ShL,typename ShR,typename O> void build(const ExL&exl, const ExR&exr, const ShL&shl, const ShR&shr, const O&out) { const int b=n/max(1,min(n,(int)sqrt(q*2.0/3.0))); vector<int>idx(q); for(int i=0;i<q;i++)idx[i]=i; sort(idx.begin(),idx.end(),[&](int i, int j) { auto[li,ri]=querys[i]; auto[lj,rj]=querys[j]; int bi=li/b,bj=lj/b; return bi==bj?bi&1?ri>rj:ri<rj:bi<bj; }); int l=0,r=0; for(int i:idx) { auto[li,ri]=querys[i]; while(l>li)exl(--l); while(r<ri)exr(r++); while(l<li)shl(l++); while(r>ri)shr(--r); out(i); } } private: int n,q; vector<pair<int,int>>querys; }; int N,Q,A[1<<16],K[1<<16],cnt[1<<17]; int ans[1<<16]; vector<int>fac[1<<16]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>Q; for(int i=0;i<N;i++) { cin>>A[i]; for(int a=1;a*a<=A[i];a++)if(A[i]%a==0) { fac[i].push_back(a); if(a*a!=A[i])fac[i].push_back(A[i]/a); } sort(fac[i].begin(),fac[i].end()); } auto ex=[&](int i){for(int a:fac[i])cnt[a]++;}; auto sh=[&](int i){for(int a:fac[i])cnt[a]--;}; auto out=[&](int i){ans[i]=cnt[K[i]];}; Mo mo(N,Q); for(int i=0;i<Q;i++) { int l,r; cin>>l>>r>>K[i]; mo.add(l-1,r); } mo.build(ex,ex,sh,sh,out); for(int i=0;i<Q;i++)cout<<ans[i]<<endl; }