CCF 除法

曾经终败给现在 2021-09-14 09:34 441阅读 0赞

## **一、试题** ##

问题描述  
　　小葱喜欢除法，所以他给了你N个数a1, a2, ⋯, aN，并且希望你执行M次操作，每次操作可能有以下两种：  
　　给你三个数l, r, v，你需要将al, al+1, ⋯, ar之间所有v的倍数除以v。  
　　给你两个数l, r，你需要回答al + al+1 + ⋯ + ar的值是多少。  
输入格式  
　　第一行两个整数N, M，代表数的个数和操作的次数。  
　　接下来一行N个整数，代表N个数一开始的值。  
　　接下来M行，每行代表依次操作。每行开始有一个整数opt。如果opt=1，那么接下来有三个数l, r, v，代表这次操作需要将第l个数到第r个数中v的倍数除以v；如果opt = 2，那么接下来有两个数l, r，代表你需要回答第l个数到第r个数的和。  
输出格式  
　　对于每一次的第二种操作，输出一行代表这次操作所询问的值。  
样例输入  
5 3  
1 2 3 4 5  
2 1 5  
1 1 3 2  
2 1 5  
样例输出  
15  
14  
评测用例规模与约定  
　　对于30%的评测用例，1 ≤ N, M ≤ 1000；  
　　对于另外20%的评测用例，第一种操作中一定有l = r；  
　　对于另外20%的评测用例，第一种操作中一定有l = 1 , r = N；  
　　对于100%的评测用例，1 ≤ N, M ≤ 105，0 ≤ a1, a2, ⋯, aN ≤ 106, 1 ≤ v ≤ 106, 1 ≤ l ≤ r ≤ N。

## **二、代码** ##

[树状数组基础知识][Link 1]  
如果使用常规算法只能30分就超时，感谢这位老兄算法  
[原版][Link 2]

#include<iostream>
    #include<math.h>
    #include<cstring>
    
    using namespace std;
    
    typedef long long LL;
    
    int N,M;
    int type,l,r,v;
    int A[100000+10];
    LL TreeArr[100000+10];
    
    //求解i二进制最后一个1后面有多少个0 
    int lowbit(int i)  
    {  
        return i&(-i);  
    } 
    
    
    void toValue(int i,int num)
    {   
    //每次读入一个数时都将树状数组的对应节点更新一下，当所有数都读取完毕后，整个树状数组也就建成。 
        while(i<=N)  
        {  
            TreeArr[i] += num;  
            i += lowbit(i);  
        }  
    }  
    
    //使用树状数组求解和 
    LL sum(int i)  
    {  
        LL total = 0;  
        while(i != 0)  
        {  
            total += TreeArr[i];  
            i -= lowbit(i);  
        }  
        return total;  
    } 
    
    int main(){
    
        cin>>N>>M;
    // 为啥 A[10^5+10]本地可以，CCF运行出错 
    // long long *out = new long long[M];
    // long long *head = out;
    // memset(out, 0, sizeof(long long)*M);
        memset(TreeArr,0,sizeof(TreeArr));
        for(int j=1; j<=N; j++){
            cin>>A[j];
    
    // 逐步更新树状数组的值，每次只是更新A[j]产生的父节点 
            toValue(j, A[j]);
        }
        while(M--){
            cin>>type;
            if(type==1){
                cin>>l>>r>>v;
                if(v==1) continue;
                for(int i=l; i<=r; i++){
                    if(A[i]>=v && A[i]%v==0){
    // v&(v-1)==0表示v是2的n次幂 
                        if(v>0 && v&(v-1)==0){
                            int n2 = log(v)/log(2);
                            toValue(i, A[i]>>n2-A[i]);
                            A[i]>>n2;
                        }else{
        // 当A[i]值变化时，树状数组对于受影响的节点都需要更新 
                            toValue(i, A[i]/v-A[i]);
                            A[i] /= v;
        // if(v==2){ 
        // A[i]>>1;
        // }else{ 
        // A[i] /= v;
        // } 
                        }
                    }
                }
            }else if(type==2){
                cin>>l>>r;
                cout<< sum(r) - sum(l-1)<<endl; 
    // int total=0;
    // for(int i=l; i<=r; i++){ 
    // total += A[i];
    // }
    // *out = total;
    // out++;
    // cout<<total<<endl;
            }
        }
    
    // out = head;
    // while(*out){ 
    // cout<<*out<<endl;
    // out++;
    // }
    
    // delete[] head;
        return 0;
    }

[Link 1]: http://blog.csdn.net/qq_16234613/article/details/78534769
[Link 2]: http://blog.csdn.net/wl16wzl/article/details/78289408?locationNum=2&fps=1