題目鏈接：點擊查看

題目大意：給定n艘敵軍的艦隊，每艘艦隊都有一定的耐力值，隨后進行m次操作，共包括兩種操作，分別是輸出區間[l,r]中的耐力

值之和，以及將區間[l,r]中的每個的耐力值都開平方

題目分析：這個題第一反應是往數論上想，推了半天也沒推出來一個平方和和平方的和之間的公式，去看了一下題解才恍然大悟

這個題其實正這想，假如讓2開始不斷循環平方，那么不到10次就會爆掉long long，這就意味著只要是long long范圍內的數，被

操作的次數再多也超不過10次，那么我們可以通過判斷區間和和區間長度是否相等來決定還需要繼續遞歸嘛，如果相等可以直接

返回，如果不相等則對區間內繼續遞歸，將其開方后在返回，因為這樣的操作至多為10次，我們可以計算時間復雜度為n*10logn

那么就可以直接進行區間更新以及區間查詢了，對了這個題有個小坑，就是輸入的區間可能l>r，這里需要自己操作一下

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int l,r;LL sum; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){scanf("%lld",&tree[k].sum);return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void update(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r)if(tree[k].sum==tree[k].r-tree[k].l+1)return;if(tree[k].l==tree[k].r){tree[k].sum=(LL)sqrt((double)tree[k].sum);return;}update(k<<1,l,r);update(k<<1|1,l,r);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }LL query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int n;int kase=0;while(scanf("%d",&n)!=EOF){build(1,1,n);int m;scanf("%d",&m);printf("Case #%d:\n",++kase);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(b>c)//這里有個惡心人的小陷阱，記得處理一下swap(b,c);if(a==0)update(1,b,c);elsecout<<query(1,b,c)<<endl;}cout<<endl; /* update(1,1,10);for(int i=1;i<=10;i++)cout<<tree[i].l<<' '<<tree[i].r<<' '<<tree[i].sum<<endl;*/}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4027 Can you answer these queries?(线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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