標題：Log大俠

    atm參加了速算訓練班，經過刻苦修煉，對以2為底的對數算得飛快，人稱Log大俠。

    一天，Log大俠的好友 drd 有一些整數序列需要變換，Log大俠正好施展法力...

    變換的規則是： 對其某個子序列的每個整數變為: [log_2 (x) + 1]  其中 [] 表示向下取整，就是對每個數字求以2為底的對數，然後取下整。
    例如對序列 3 4 2 操作一次後，這個序列會變成 2 3 2。
    
    drd需要知道，每次這樣操作後，序列的和是多少。

【輸入格式】
第一行兩個正整數 n m 。
第二行 n 個數，表示整數序列，都是正數。
接下來 m 行，每行兩個數 L R 表示 atm 這次操作的是區間 [L, R]，數列序號從1開始。

【輸出格式】
輸出 m 行，依次表示 atm 每做完一個操作後，整個序列的和。

例如，輸入：
3 3
5 6 4
1 2
2 3
1 3

程序應該輸出：
10
8
6


【數據範圍】
對於 30% 的數據， n, m <= 10^3
對於 100% 的數據， n, m <= 10^5


資源約定：
峰值內存消耗 < 256M
CPU消耗  < 1000ms


請嚴格按要求輸出，不要畫蛇添足地列印類似：「請您輸入...」 的多餘內容。

所有代碼放在同一個源文件中，調試通過後，拷貝提交該源碼。

注意: main函數需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴於編譯環境或作業系統的特殊函數。
注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

log2對數表：https://zh.arslanbar.net/post.php?t=24047
【代碼】
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define log2(x) (log10((double)x) / log10(2.0))

int main(void)
{
    int m, n;
    int i, j;
    int *nums;
    int *L, *R;
    int sum;

    scanf("%d%d", &n, &m);
    nums = (int *)malloc(n * sizeof(int));
    L = (int *)malloc(m * sizeof(int));
    R = (int *)malloc(m * sizeof(int));
    for (i = 0; i < n; i++)
        scanf("%d", nums + i);

    for (i = 0; i < m; i++)
        scanf("%d%d", L + i, R + i);

    for (i = 0; i < m; i++)
    {
        for (j = L[i]; j <= R[i]; j++)
            nums[j - 1] = (int)floor(log2((double)nums[j - 1]) + 1.0);
        sum = 0;
        for (j = 0; j < n; j++)
            sum += nums[j];
        printf("%d\n", sum);
    }

    free(nums);
    free(L);
    free(R);
    return 0;
}

這代碼從第三個測評數據開始就超時了，所以只能得20分。。。

【稍微好一點的算法】
#include <stdio.h>

// 用位運算快速計算log2(n)+1
int fun(int n)
{
    int t = 0;
    while (n)
    {
        n >>= 1;
        t++;
    }
    return t;
}

int main(void)
{
    int a[100010];
    int b[100010];
    int m, n, L, R, i, j;
    int temp;
    int sum = 0;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        sum += a[i];
    }
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d", &L, &R);
        for (j = L; j <= R; j++)
        {
            temp = a[j];
            a[j] = fun(a[j]);
            sum -= temp - a[j];
        }
        b[i] = sum;
    }
    for (i = 1; i <= m; i++)
        printf("%d\n", b[i]);
    return 0;
}

http://blog.csdn.net/crz_cc/article/details/51422600

但是第三組數據還是超時了