第十三届蓝桥杯省赛第二场真题——K倍区间加强版（AC）

蔚落 2023-09-29 18:40 26阅读 0赞

## 1.K倍区间 ##

### 1.题目描述 ###

一个整数序列 A = ( a 1 , a 2 , ⋯ , a n ) A=(a\_1 ,a\_2,⋯,a\_n) A=(a1,a2,⋯,an)的区间和为 S i , j = a i + a i + 1 + ⋯ + a j 。 S\_\{i,j\} =a\_i +a\_\{i+1\} +⋯+a\_j 。 Si,j=ai\+ai\+1\+⋯\+aj。  
给定整数序列  A A A 和一个正整数  k k k, 请问有多少个区间 \[ i , j \] \[i,j\] \[i,j\]满足  
 1 ≤ i ≤ j ≤ n 1≤i≤j≤n 1≤i≤j≤n且  S i , j S\_\{i,j\} Si,j 是  k k k 非负整数倍。

### 2.输入格式 ###

输入的第一行包含两个整数  n 、 k n、k n、k, 用一个空格分隔。

第二行包含  n n n 个整数  a 1 , a 2 , ⋯ , a n a\_1 ,a\_2 ,⋯,a\_n a1,a2,⋯,an , 相邻的整数之间用一个空格分隔。

### 3.输出格式 ###

输出一行包含一个数表示满足条件的区间数量。

### 4.样例输入 ###

7 3  
1 -1 0 2 2 2 -30

### 5.样例答案 ###

### 6.数据范围 ###

1 ≤ n ≤ 100000 , 1 ≤ k ≤ 1 0 9 , − 1 0 9 ≤ a i ≤ 1 0 9 1≤n≤100000,1≤k≤10^9,−10^9≤ai≤10^9 1≤n≤100000,1≤k≤109,−109≤ai≤109

### 7.原题链接 ###

[k倍区间][k]

## 2.解题思路 ##

本题为原K倍区间的升级版，范围不仅变大且增加了负数，由于需要求得`k`的非负整数倍，我们需要进行分类讨论。

先求得数组  a a a 的前缀和数组  s s s，研究一段区间和是否为  k k k倍区间，其实本质就是求多少对下标  i , j i,j i,j 满足  ( s \[ j \] − s \[ i \] ) % k = = 0 (s\[j\]-s\[i\])\\%k==0 (s\[j\]−s\[i\])%k==0，当然需要满足  0 ≤ i < j ≤ n 0\\leq i <j \\leq n 0≤i<j≤n。

我们从 s \[ i \] s\[i\] s\[i\]和 s \[ j \] s\[j\] s\[j\]的奇偶性去进行分类讨论：

1.  当 s \[ i \] ≥ 0 s\[i\]\\geq0 s\[i\]≥0 且  s \[ j \] ≥ 0 s\[j\] \\geq 0 s\[j\]≥0  
    显然这种情况如果满足 a \[ j \] % k = a \[ i \] % k a\[j\]\\%k=a\[i\]\\%k a\[j\]%k=a\[i\]%k，也就是说两者对  k k k 的余数相同则说明我们找到了一对符合的下标，当然还得满足 s \[ i \] ≤ s \[ j \] s\[i\]\\leq s\[j\] s\[i\]≤s\[j\]。
2.  当 s \[ i \] < 0 s\[i\]<0 s\[i\]<0 且  s \[ j \] ≥ 0 s\[j\] \\geq 0 s\[j\]≥0  
    显然此时 s \[ j \] − s \[ i \] s\[j\]-s\[i\] s\[j\]−s\[i\]一定是一个非负数，是有可能作为答案的，这种一正一负的情况显然不应该满足且不会满足 a \[ j \] % k = a \[ i \] % k a\[j\]\\%k=a\[i\]\\%k a\[j\]%k=a\[i\]%k。那么满足什么条件是合法的呢？显然手推一下可以发现如果满足  
     s \[ j \] % k − k = s \[ i \] % k s\[j\]\\%k-k=s\[i\]\\%k s\[j\]%k−k=s\[i\]%k  
    那么  i , j i,j i,j 也是一对合法区间。
3.  当 s \[ i \] ≥ 0 s\[i\]\\geq0 s\[i\]≥0 且  s \[ j \] < 0 s\[j\]<0 s\[j\]<0  
    显然 s \[ j \] − s \[ i \] s\[j\]-s\[i\] s\[j\]−s\[i\]一定为负数，一定不合法。
4.  当 s \[ i \] ≤ 0 s\[i\]\\leq0 s\[i\]≤0 且  s \[ j \] ≤ 0 s\[j\]\\leq0 s\[j\]≤0  
    如果此时满足 s \[ i \] < s \[ j \] s\[i\]<s\[j\] s\[i\]<s\[j\] 且满足 s \[ j \] % k = s \[ i \] % k s\[j\]\\%k=s\[i\]\\%k s\[j\]%k=s\[i\]%k，那么 i , j i,j i,j符合要求。

经过讨论，显然我们必须做的一件事是需要将数组  s s s 按照对  k k k 的余数来进行分组。对于任意一组数  v v v，无论里面存的是负数还是正数，有多少对数满足 i < j i<j i<j 且  v \[ i \] ≤ v \[ j \] v\[i\]\\leq v\[j\] v\[i\]≤v\[j\] 则有多少答案，这个过程我们可以使用树状数组求解，但由于  v \[ i \] v\[i\] v\[i\] 有可能特别大，每组数我们都需要先进行离散化处理。

分析中比较特殊的是第二种情况，对于每个非负的  s \[ j \] s\[j\] s\[j\]，我们还需要找到在它之前出现过多少个负数 s \[ i \] s\[i\] s\[i\]，满足 s \[ j \] % k − k = s \[ i \] % k s\[j\]\\%k-k=s\[i\]\\%k s\[j\]%k−k=s\[i\]%k。那么我们还需要去分组存下标，然后去对应的组里二分去找一下有多少个  i i i 符合即可。

具体实现见代码。

## 3 Ac\_code ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, int> PII;
    #define pb(s) push_back(s);
    #define SZ(s) ((int)s.size());
    #define ms(s,x) memset(s, x, sizeof(s))
    #define all(s) s.begin(),s.end()
    const int inf = 0x3f3f3f3f;
    const int mod = 1000000007;
    const int N = 200010;
    
    int n, k;
    template <typename T>
    struct BIT {
        
        const int n;
        std::vector<T> a;
        BIT(int n) : n(n), a(n) {
        }
        void add(int x, T v) {
        
            for (int i = x; i <= n; i += i & -i) {
        
                a[i - 1] += v;
            }
        }
        T sum(int x) {
        
            T ans = 0;
            for (int i = x; i > 0; i -= i & -i) {
        
                ans += a[i - 1];
            }
            return ans;
        }
        T rangeSum(int l, int r) {
        
            return sum(r) - sum(l);
        }
    };
    void solve()
    {
        
        cin >> n >> k;
        std::vector<LL> s(n + 1);
        map<int, std::vector<LL>> m;
        map<int, std::vector<int>> e;
        for (int i = 1; i <= n; ++i) {
        
            cin >> s[i];
            s[i] += s[i - 1];
        }
        for (int i = 0; i <= n; ++i) {
        
            m[s[i] % k].push_back(s[i]);
            e[s[i] % k].push_back(i);
        }
        LL ans = 0;
        for (auto [x, y] : m) {
        
            auto arr = y;
            sort(arr.begin(), arr.end());
            arr.erase(unique(arr.begin(), arr.end()), arr.end());
            BIT<int> tr(arr.size() + 1);
            if (x >= 0) {
        
                //正数减去正数
                for (auto v : y) {
        
                    int t = lower_bound(arr.begin(), arr.end(), v) - arr.begin() + 1;
                    ans += tr.sum(t);
                    tr.add(t, 1);
                }
                //正数减去负数
                for (auto v : e[x]) {
        
                    ans += upper_bound(all(e[x - k]), v) - e[x - k].begin();
                }
            } else {
        
                //负数减去负数
                for (auto v : y) {
        
                    int t = lower_bound(arr.begin(), arr.end(), v) - arr.begin() + 1;
                    ans += tr.sum(t);
                    tr.add(t, 1);
                }
            }
        }
        cout << ans << '\n';
    }
    int main()
    {
        
        ios_base :: sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
        int t = 1;
        while (t--)
        {
        
            solve();
        }
        return 0;
    }

[k]: https://www.lanqiao.cn/problems/2387/learning/