正題

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

---

題目大意

一個序列要求支持

區間開根向下取整

區間求和

---

解題思路

一個數開根約$log$次就會到$1$，所以我們對于每個數記錄一下開根多少次會到$1$，每次修改用并查集找還沒到$1$的暴力修改樹狀數組上的值即可。

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

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define lowbit(x) x&-x using namespace std; const ll N=1e5+10; ll n,m,fa[N],t[N],a[N],w[N]; void Change(ll x,ll val){while(x<=n){t[x]+=val;x+=lowbit(x);} } ll Ask(ll x){ll ans=0;while(x){ans+=t[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 k=sqrt(w[x]);a[x]--;Change(x,-w[x]+k);w[x]=k;if(!a[x]){if(!a[x+1]&&x<n)fa[x]=find(x+1);if(!a[x-1]&&x>1)fa[x-1]=find(x);}return; } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){fa[i]=i;ll x;scanf("%lld",&x);w[i]=x;Change(i,x);while(x>1){a[i]++;x=sqrt(x);}}scanf("%lld",&m);for(ll i=1;i<=m;i++){ll k,l,r;scanf("%lld%lld%lld",&k,&l,&r);if(l>r)swap(l,r);if(k==0){while(l<=r&&l){if(a[l])Move(l);l=find(l)+1;}}else printf("%lld\n",Ask(r)-Ask(l-1));}return 0; }

總結

以上是生活随笔為你收集整理的P4145-上帝造题的七分钟2/花神游历各国【并查集,树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

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