結果
問題 | No.2361 Many String Compare Queries |
ユーザー |
|
提出日時 | 2023-06-23 22:28:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,500 ms |
コード長 | 1,838 bytes |
コンパイル時間 | 1,864 ms |
コンパイル使用メモリ | 105,756 KB |
実行使用メモリ | 43,568 KB |
最終ジャッジ日時 | 2024-07-01 02:12:04 |
合計ジャッジ時間 | 5,531 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cassert>#include<atcoder/string>#include<atcoder/segtree>#include<atcoder/lazysegtree>using namespace std;int opmin(int a,int b){return min(a,b);}int emin(){return(int)1e9;}using dat=pair<long long,int>;dat opsum(dat a,dat b){a.first+=b.first;a.second+=b.second;return a;}dat esum(){return make_pair(0LL,0);}dat mp(int f,dat x){x.first+=(long long)f*x.second;return x;}int cmp(int f,int g){return f+g;}int id(){return 0;}int N,Q;string S;int inv[2<<17];int L[1<<17],R[1<<17];long long ans[1<<17];vector<int>Qid[2<<17];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>Q>>S;vector<int>SA=atcoder::suffix_array(S);vector<int>LCP=atcoder::lcp_array(S,SA);for(int i=0;i<SA.size();i++)inv[SA[i]]=i;atcoder::segtree<int,opmin,emin>lcp_seg(LCP);vector<dat>len_init(N);for(int i=0;i<N;i++)len_init[i]=make_pair(N-SA[i],1);atcoder::lazy_segtree<dat,opsum,esum,int,mp,cmp,id>len_seg(len_init);for(int i=0;i<Q;i++){cin>>L[i]>>R[i];L[i]--;int idx=inv[L[i]];R[i]=R[i]-L[i];//lenint l=lcp_seg.min_left(idx,[&i](int x){return x>=R[i];});L[i]=l;Qid[l].push_back(i);ans[i]=len_seg.prod(0,l).first;}vector<dat>init(N,make_pair(0,1));atcoder::lazy_segtree<dat,opsum,esum,int,mp,cmp,id>seg(init);vector<pair<int,int> >st;for(int i=N;i--;){if(i+1<N){int len=LCP[i];int cnt=0;while(!st.empty()&&st.back().second>=len){int c=st.back().first;seg.apply(len,st.back().second,-c);cnt+=c;st.pop_back();}if(cnt>0){st.push_back(make_pair(cnt,len));}}seg.apply(0,N-SA[i],1);st.push_back(make_pair(1,N-SA[i]));for(int id:Qid[i]){ans[id]+=seg.prod(0,R[id]-1).first;}}for(int i=0;i<Q;i++)cout<<ans[i]<<"\n";}