北京网站开发网站建设浩森宇特,6网站建设做网站,有哪些网页游戏网站,wordpress 图加载中正题
题目链接:https://www.luogu.com.cn/problem/P4145 题目大意
一个序列要求支持
区间开根向下取整区间求和 解题思路
一个数开根约logloglog次就会到111#xff0c;所以我们对于每个数记录一下开根多少次会到111#xff0c;每次修改用并查集找还没到111的暴力修改树状…正题
题目链接:https://www.luogu.com.cn/problem/P4145 题目大意
一个序列要求支持
区间开根向下取整区间求和 解题思路
一个数开根约logloglog次就会到111所以我们对于每个数记录一下开根多少次会到111每次修改用并查集找还没到111的暴力修改树状数组上的值即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
#define lowbit(x) x-x
using namespace std;
const ll N1e510;
ll n,m,fa[N],t[N],a[N],w[N];
void Change(ll x,ll val){while(xn){t[x]val;xlowbit(x);}
}
ll Ask(ll x){ll ans0;while(x){anst[x];x-lowbit(x);}return ans;
}
ll find(ll x)
{return (fa[x]x)?(x):(fa[x]find(fa[x]));}
void Move(ll x){ll ksqrt(w[x]);a[x]--;Change(x,-w[x]k);w[x]k;if(!a[x]){if(!a[x1]xn)fa[x]find(x1);if(!a[x-1]x1)fa[x-1]find(x);}return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){fa[i]i;ll x;scanf(%lld,x);w[i]x;Change(i,x);while(x1){a[i];xsqrt(x);}}scanf(%lld,m);for(ll i1;im;i){ll k,l,r;scanf(%lld%lld%lld,k,l,r);if(lr)swap(l,r);if(k0){while(lrl){if(a[l])Move(l);lfind(l)1;}}else printf(%lld\n,Ask(r)-Ask(l-1));}return 0;
}
