結果
問題 | No.469 区間加算と一致検索の問題 |
ユーザー |
![]() |
提出日時 | 2018-11-04 14:23:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 325 ms / 5,000 ms |
コード長 | 3,694 bytes |
コンパイル時間 | 2,557 ms |
コンパイル使用メモリ | 216,860 KB |
最終ジャッジ日時 | 2025-01-06 15:32:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T,T MOD = 1000000007> struct Mint{ T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(int k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a){return Mint(v)+=a;}; Mint operator-(Mint a){return Mint(v)-=a;}; Mint operator*(Mint a){return Mint(v)*=a;}; Mint operator/(Mint a){return Mint(v)/=a;}; Mint operator-(){return v?MOD-v:v;} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator<(const Mint a)const{return v<a.v;} static vector<Mint> po,op; static void init(int n, T BASE){ if(n+1<=(signed)po.size()) return; po.assign(n+1,1); op.assign(n+1,1); Mint x(BASE); Mint y=Mint(1)/x; for(int i=1;i<=n;i++) po[i]=po[i-1]*x; for(int i=1;i<=n;i++) op[i]=op[i-1]*y; } }; template<typename T,T MOD> vector<Mint<T, MOD> > Mint<T, MOD>::po = vector<Mint<T, MOD> >(); template<typename T,T MOD> vector<Mint<T, MOD> > Mint<T, MOD>::op = vector<Mint<T, MOD> >(); template<typename T,typename M1,typename M2,typename M3> struct PolynomialHash{ using V = tuple<M1, M2, M3>; static const T BASE = 1777771; PolynomialHash(const int n){ M1::init(n, BASE); M2::init(n, BASE); M3::init(n, BASE); } V build(const vector<T> &v){ int n=v.size(); M1 r1;M2 r2;M3 r3; for(int i=0;i<n;i++){ r1+=M1(v[i])*M1::po[i]; r2+=M2(v[i])*M2::po[i]; r3+=M3(v[i])*M3::po[i]; } return V(r1,r2,r3); } V add(const V &a,const V &b){ M1 a1=get<0>(a),b1=get<0>(b); M2 a2=get<1>(a),b2=get<1>(b); M3 a3=get<2>(a),b3=get<2>(b); return V(a1+b1,a2+b2,a3+b3); } V sub(const V &a,const V &b){ M1 a1=get<0>(a),b1=get<0>(b); M2 a2=get<1>(a),b2=get<1>(b); M3 a3=get<2>(a),b3=get<2>(b); return V(a1-b1,a2-b2,a3-b3); } V mul(const V &a,const V &b){ M1 a1=get<0>(a),b1=get<0>(b); M2 a2=get<1>(a),b2=get<1>(b); M3 a3=get<2>(a),b3=get<2>(b); return V(a1*b1,a2*b2,a3*b3); } V inv(const V &a){ M1 a1;M2 a2;M3 a3; tie(a1,a2,a3)=a; return V(a1.inv(),a2.inv(),a3.inv()); } V term(int x,T k){ M1 a1=M1::po[x]*M1(k); M2 a2=M2::po[x]*M2(k); M3 a3=M3::po[x]*M3(k); return V(a1,a2,a3); } }; //INSERT ABOVE HERE signed main(){ int n,q; cin>>n>>q; using M1 = Mint<int, int(1e9+7)>; using M2 = Mint<int, int(1e9+9)>; using M3 = Mint<int, int(1e8+7)>; using V = PolynomialHash<Int, M1, M2, M3>; using T = V::V; V ph(n*2+100); vector<T> vs(n+1); vs[0]=ph.term(0,0); for(int i=0;i<n;i++) vs[i+1]=ph.add(vs[i],ph.term(i,1)); T sum=vs[0]; map<T, int> m; m[sum]=0; for(int i=0;i<q;i++){ char c; cin>>c; if(c=='!'){ int l,r,k; cin>>l>>r>>k; T di=ph.sub(vs[r],vs[l]); T sc=ph.term(0,k); sum=ph.add(sum,ph.mul(di,sc)); } //cout<<get<0>(sum).v<<" "; //cout<<get<1>(sum).v<<" "; //cout<<get<2>(sum).v<<endl; if(!m.count(sum)) m[sum]=i+1; if(c=='?') cout<<m[sum]<<endl; } return 0; }