推荐企业手机网站建设,建设网站哪好,在线股票交易网站开发,视频教程网站模板正题
题目链接:https://www.luogu.com.cn/problem/CF438D 题目大意
一个序列要求支持
区间求和区间取模单点修改 解题思路
对于一个数取模会有结果x%p{x≤⌊x2⌋xx\% p\{\begin{matrix}x\leq \lfloor\frac{x}{2}\rfloor\\x\end{matrix}x%p{x≤⌊2x⌋x
也就是一个数最多…正题
题目链接:https://www.luogu.com.cn/problem/CF438D 题目大意
一个序列要求支持
区间求和区间取模单点修改 解题思路
对于一个数取模会有结果x%p{x≤⌊x2⌋xx\% p\{\begin{matrix}x\leq \lfloor\frac{x}{2}\rfloor\\x\end{matrix}x%p{x≤⌊2x⌋x
也就是一个数最多会被取模而修改logloglog次所以我们只要每次查询区间最大值如果≥p\geq p≥p那么就修改最大值即可这样每个数最多修改logloglog次。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510;
ll n,q,w[N],mx[N],z[N];
void PushUp(ll x){w[x]w[x*2]w[x*21];mx[x]max(mx[x*2],mx[x*21]);if(mx[x]mx[x*2])z[x]z[x*2];else z[x]z[x*21];
}
void Change(ll x,ll L,ll R,ll pos,ll val){if(LR){w[x]mx[x]val;z[x]pos;return;}ll mid(LR)1;if(posmid)Change(x*2,L,mid,pos,val);else Change(x*21,mid1,R,pos,val);PushUp(x);return;
}
void Mod(ll x,ll L,ll R,ll l,ll r,ll val){if(LlRr){while(mx[x]val)Change(x,L,R,z[x],mx[x]%val);return;}ll mid(LR)1;if(rmid)Mod(x*2,L,mid,l,r,val);else if(lmid)Mod(x*21,mid1,R,l,r,val);else Mod(x*2,L,mid,l,mid,val),Mod(x*21,mid1,R,mid1,r,val);PushUp(x);return;
}
ll Ask(ll x,ll L,ll R,ll l,ll r){if(LlRr)return w[x];ll mid(LR)1;if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return Ask(x*2,L,mid,l,mid)Ask(x*21,mid1,R,mid1,r);
}
int main()
{scanf(%lld%lld,n,q);for(ll i1;in;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(op1)printf(%lld\n,Ask(1,1,n,l,r));else if(op2)scanf(%lld,x),Mod(1,1,n,l,r,x);else Change(1,1,n,l,r);}return 0;
}
