제출 #239928

#제출 시각아이디문제언어결과실행 시간메모리
239928MvCSterilizing Spray (JOI15_sterilizing)C++11
100 / 100
721 ms71800 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() #define lun(x) (int)x.size() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<60); const int inf=(1<<30); const int nmax=1e5+50; const ll mod=1e9+7; using namespace std; int n,q,l,r,a[nmax],k,lzy[4*nmax],tp,i; ll st[4*nmax],vl[4*nmax][32],fw[nmax]; void push(int nod,int l,int r) { if(!lzy[nod])return; lzy[nod]=min(lzy[nod],30); int i; for(i=0;i+lzy[nod]<=30;i++)vl[nod][i]=vl[nod][i+lzy[nod]]; for(;i<=30;i++)vl[nod][i]=0; ll pw=1; st[nod]=0; for(i=0;i<=30;i++) { st[nod]+=pw*vl[nod][i]; if(pw*1LL*k>=inf)break; pw*=k; } if(l!=r) { lzy[nod*2]+=lzy[nod]; lzy[nod*2+1]+=lzy[nod]; } lzy[nod]=0; } void upd(int nod,int l,int r,int tl,int tr) { push(nod,l,r); if(tl<=l && r<=tr) { lzy[nod]++; push(nod,l,r); return; } int mid=(l+r)/2; if(tl<=mid)upd(nod*2,l,mid,tl,tr); if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr); push(nod*2,l,mid); push(nod*2+1,mid+1,r); for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i]; st[nod]=st[nod*2]+st[nod*2+1]; } void chg(int nod,int l,int r,int p,int v) { push(nod,l,r); if(l==r) { st[nod]=v; int i=0; while(v) { vl[nod][i++]=v%k; v/=k; } for(;i<=30;i++)vl[nod][i]=0; return; } int mid=(l+r)/2; if(p<=mid)chg(nod*2,l,mid,p,v); else chg(nod*2+1,mid+1,r,p,v); push(nod*2,l,mid); push(nod*2+1,mid+1,r); for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i]; st[nod]=st[nod*2]+st[nod*2+1]; } ll qry(int nod,int l,int r,int tl,int tr) { push(nod,l,r); if(l>tr || r<tl)return 0; if(tl<=l && r<=tr)return st[nod]; int mid=(l+r)/2; return qry(nod*2,l,mid,tl,tr)+qry(nod*2+1,mid+1,r,tl,tr); } void ufw(int i,ll v) { for(;i<=n;i+=i&(-i))fw[i]+=v; } ll qfw(int i) { ll ans=0; for(;i>=1;i-=i&(-i))ans+=fw[i]; return ans; } ll query(int l,int r) { ll ans=qfw(r); if(l>1)ans-=qfw(l-1); return ans; } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>q>>k; for(i=1;i<=n;i++) { cin>>a[i]; if(k!=1)chg(1,1,n,i,a[i]); else ufw(i,a[i]); } while(q--) { cin>>tp>>l>>r; if(tp==1) { if(k!=1) { a[l]=r; chg(1,1,n,l,a[l]); } else { ufw(l,-a[l]); a[l]=r; ufw(l,a[l]); } } else if(tp==2 && k!=1)upd(1,1,n,l,r); else if(tp==3) { if(k==1)cout<<query(l,r)<<'\n'; else cout<<qry(1,1,n,l,r)<<'\n'; } } return 0; } /* 5 10 3 1 2 8 1 3 1 2 5 2 3 5 3 2 5 2 1 4 1 3 2 3 3 5 1 2 4 2 1 2 1 1 4 3 1 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...