正題

題目鏈接:https://www.luogu.com.cn/problem/CF438D

---

題目大意

一個序列要求支持

區間求和

區間取模

單點修改

---

解題思路

對于一個數取模會有結果$$x\%p=\{\begin{array}{c}x\le ?\frac{x}{2}?\\ x\end{array}$$

也就是一個數最多會被取模而修改$log$次，所以我們只要每次查詢區間最大值如果$\ge p$那么就修改最大值即可，這樣每個數最多修改$log$次。

時間復雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=4e5+10; ll n,q,w[N],mx[N],z[N]; void PushUp(ll x){w[x]=w[x*2]+w[x*2+1];mx[x]=max(mx[x*2],mx[x*2+1]);if(mx[x]==mx[x*2])z[x]=z[x*2];else z[x]=z[x*2+1]; } void Change(ll x,ll L,ll R,ll pos,ll val){if(L==R){w[x]=mx[x]=val;z[x]=pos;return;}ll mid=(L+R)>>1;if(pos<=mid)Change(x*2,L,mid,pos,val);else Change(x*2+1,mid+1,R,pos,val);PushUp(x);return; } void Mod(ll x,ll L,ll R,ll l,ll r,ll val){if(L==l&&R==r){while(mx[x]>=val)Change(x,L,R,z[x],mx[x]%val);return;}ll mid=(L+R)>>1;if(r<=mid)Mod(x*2,L,mid,l,r,val);else if(l>mid)Mod(x*2+1,mid+1,R,l,r,val);else Mod(x*2,L,mid,l,mid,val),Mod(x*2+1,mid+1,R,mid+1,r,val);PushUp(x);return; } ll Ask(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r)return w[x];ll mid=(L+R)>>1;if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r); } int main() {scanf("%lld%lld",&n,&q);for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);Change(1,1,n,i,x);}while(q--){ll op,l,r,x;scanf("%lld%lld%lld",&op,&l,&r);if(op==1)printf("%lld\n",Ask(1,1,n,l,r));else if(op==2)scanf("%lld",&x),Mod(1,1,n,l,r,x);else Change(1,1,n,l,r);}return 0; }

總結

以上是生活随笔為你收集整理的CF438D-The Child and Sequence【线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。