題意：

? ? ? 給你n個數（n <= 100000）,然后兩種操作，0 x y ：把x-y的數全都sqrt ,1 x y:輸出 x-y的和。

思路：

? ? ? 直接線段樹更新就行了，對于當前的這個區間，如果里面只有0或者1，那么就把他mark上，以后不用在更新了，10^18 更新不了多少次就會變成0或者1的，所以時間復雜度也沒多少，每次更新能返回就返回，不能返回就一定要精確到點，然后sqrt,然后查詢的話就是一個簡單的段詢問。

#include<stdio.h>
#include<string.h>
#include<math.h>


#define lson l ,mid ,t << 1
#define rson mid + 1 ,r ,t << 1 | 1


long long ?sum[440000];
long long mark[440000];


void Pushup(int t)
{
? ?sum[t] = sum[t<<1] + sum[t<<1|1];
? ?mark[t] = (mark[t<<1] & mark[t<<1|1]);
}


void BuidTree(int l ,int r ,int t)
{
? ?mark[t] = sum[t] = 0;
? ?if(l == r)
? ?{
? ? ? scanf("%lld" ,&sum[t]);
? ? ? if(sum[t] == 0 || sum[t] == 1)
? ? ? mark[t] = 1;
? ? ? return;
? ?}
? ?int mid = (l + r) >> 1;
? ?BuidTree(lson);
? ?BuidTree(rson);
? ?Pushup(t);
? ?return;
}
?
void Update(int l ,int r ,int t ,int a ,int b)
{
? ?if(mark[t]) return;
? ?if(l == r)
? ?{
? ? ? sum[t] = (long long)sqrt(sum[t]*1.0);
? ? ? if(sum[t] == 1 || sum[t] == 0) mark[t] = 1;
? ? ? return;
? ?}
? ?int mid = (l + r) >> 1;
? ?if(a <= mid) Update(lson ,a ,b);
? ?if(b > mid) ?Update(rson ,a ,b);
? ?Pushup(t);
}


long long Query(int l ,int r ,int t ,int a ,int b)
{
? ?if(a <= l && b >= r) return sum[t];
? ?int mid = (l + r) >> 1;
? ?long long Ans = 0;
? ?if(a <= mid) Ans = Query(lson ,a ,b);
? ?if(b > mid) Ans += Query(rson ,a ,b);
? ?return Ans;
}


int main ()
{
? ?int i ,n ,m ,cas = 1;
? ?int key ,a ,b;
? ?while(~scanf("%d" ,&n))
? ?{
? ? ? BuidTree(1 ,n ,1);
? ? ? scanf("%d" ,&m);
? ? ? printf("Case #%d:\n" ,cas ++);
? ? ? while(m--)
? ? ? {
? ? ? ? ?scanf("%d %d %d" ,&key ,&a ,&b);
? ? ? ? ?int t;
? ? ? ? ?if(a > b)?
? ? ? ? ?{
? ? ? ? ? ? t = a ,a = b ,b = t;
? ? ? ? ?}?
? ? ? ? ?if(!key)
? ? ? ? ?{
? ? ? ? ? ? Update(1 ,n ,1 ,a ,b);
? ? ? ? ?}
? ? ? ? ?else
? ? ? ? ?{
? ? ? ? ? ? printf("%lld\n" ,Query(1 ,n ,1 ,a ,b));
? ? ? ? ?}
? ? ? }
? ? ? printf("\n");
? ?}
? ?return 0;
}

總結

以上是生活随笔為你收集整理的SPOJ 2713 线段树（sqrt）的全部內容，希望文章能夠幫你解決所遇到的問題。

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