蓝桥杯 ：k倍区间-线段树

蓝桥杯 第八届 第十题 标题： k倍区间

线段树

标题： k倍区间

给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出

输出一个整数，代表K倍区间的数目。

例如，
输入：
5 2
1
2
3
4
5

程序应该输出：
6

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

/*
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出
-----
输出一个整数，代表K倍区间的数目。


例如，
输入：
5 2
1
2
3
4
5

程序应该输出：
6
*/

#include<iostream>
#include<cstring>
using namespace std;

const long long maxn = 100000;

void build_tree(long long arr[], long long tree[],int node,int start,int endd)
{
    if(start == endd)
    {
        tree[node] = arr[start];
    }
    else
    {
        long mid = (endd + start) / 2;
        long left_node = 2 * node + 1;
        long right_node = 2 * node + 2;
        build_tree(arr,tree,left_node,start,mid);
        build_tree(arr,tree,right_node,mid+1,endd);
        tree[node] = tree[left_node] + tree[right_node];
    }
}

long long query_LR(long long arr[], long long tree[], int node, int start, int endd, int L, int R)
{

    if(R < start || L > endd)
    {
        return 0;
    }
    else if (L<=start && endd <= R) //已经获取L,R的和就不用继续递归下去了
    {
        return tree[node];
    }
    else if (start == endd)
    {
        return tree[node];
    }
    else
    {
        long mid = (start+endd) / 2;
        long left_node = 2 * node + 1;
        long right_node = 2 * node + 2;

        long sum_left = query_LR(arr,tree,left_node,start,mid,L,R);
        long sum_right = query_LR(arr,tree,right_node,mid+1,endd,L,R);
        return sum_left+sum_right;
    }
}
long long arr[100005];

int main(void)
{
    //int arr[]= {1,3,5,7,9,11};
    long long N,K;
    cin>>N>>K;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }

    //cout<<"1"<<endl;
    long long tree[maxn];
    memset(tree,0,sizeof(tree));
    build_tree(arr,tree,0,0,N-1);


    int countt=0;
    //1-n
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            //cout<<"("<<i<<","<<j<<")";
            int res = query_LR(arr,tree,0,0,N-1,i,j);
            //cout<<" "<<res<<endl;
            if(res%K==0)
                countt++;
        }
    }

    for(int i=0;i<N;i++)
    {
        if(arr[i]%K==0)
            countt++;
    }
    cout<<countt<<endl;


    return 0;
}

本文地址：https://blog.csdn.net/weixin_46014872/article/details/109012193