程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Can you answer these queries?(線段樹之單點更新)

Can you answer these queries?(線段樹之單點更新)

編輯:關於C++

萌萌哒的傳送門


因為一個long long 范圍內的數開方不會超過10次,所以題目就轉化為線段樹的單點更新問題.


#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
const int M = 1e5 + 100;
const int N = 1e7 + 100;
ll sum[M << 2];

void pushup(int u){
    sum[u] = sum[ls] + sum[rs];
}

void build(int l,int r,int u){
    if(l == r){
        scanf("%I64d",sum + u);
    }
    else {
        int mid = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(u);
    }
}

void update(int L,int R,int l,int r,int u){
    if(sum[u] == (r - l + 1)){
        return;
    }
    if(l == r){
        sum[u] = floor(sqrt((double)sum[u]));
    }
    else {
        int mid = (l + r) >> 1;
        if(L <= mid) update(L,R,lson);
        if(R > mid) update(L,R,rson);
        pushup(u);
    }
}

ll query(int L,int R,int l,int r,int u){
    if(L <= l && R >= r){
        return sum[u];
    }
    else {
        int mid = (l + r) >> 1;
        ll res = 0;
        if(L <= mid) res += query(L,R,lson);
        if(R > mid) res += query(L,R,rson);
        return res;
    }
}

int main(){
    //freopen("in","r",stdin);
    int n,m,cnt = 0;
    while(~scanf("%d",&n)){
        build(1,n,1);
        scanf("%d",&m);
        printf("Case #%d:\n",++cnt);
        while(m--){
            int t,l,r;
            scanf("%d %d %d",&t,&l,&r);
            if(l > r) swap(l,r);
            if(!t) update(l,r,1,n,1);
            else {
                printf("%I64d\n",query(l,r,1,n,1));
            }
        }
        puts("");
    }
    return 0;
}




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved