2024码蹄杯本科赛道

· · 题解

E.等差数列

简要题意 ：给定一个长度为 n 的数组 a , 询问 q 次每次询问给定俩个整数 l,r 求出区间 [l ,r] 中有多少个子区间是一个等差数列

解决思路 ： (双指针 + 前缀和)

定义 rmx[i] 表示首先为 a[i] 时最长等差数列上界为 rmx[i] 同理 lmx[i] ,S[i]表示贡献前缀和。

双指针处理出 rmx、lmx、S 数组后对于每个询问分类讨论端点情况。

  1. 若 rmx[l] >= r 则答案为 (r - l + 1) * (r - l + 2) / 2

  2. 否则答案为 S[lmx[r] - 1] - S[l - 1] + (r - lmx[r] + 1) * (r - lmx[r] + 2) / 2

#include <bits/stdc++.h>

using namespace std ;
#define int long long

const int N = 1e6 + 10 ;
const int inf = 0x3f3f3f3f ;

int n , q , a[N] , rmx[N] , lmx[N] , S[N] ;

signed main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false) ;

    cin >> n >> q; 
    for(int i = 1 ; i <= n ; ++ i)
    {
        cin >> a[i] ;
        rmx[i] = lmx[i] = i ; 
    }

    if ( n == 1 ) {
        while ( q-- ) {
            int l , r;
            cin >> l >> r;
            cout << 1 << '\n' ;
        }
    } else {
        int l = 1 , r = 2 ;
        a[n + 1] = inf ;
        while ( r <= n ) 
        {
            ++ r ;
            while (r > l && a[r] - a[r - 1] != a[l + 1] - a[l] ) 
            {
                // [l , r) 等差数列以 a[l + 1] - a[l] 为公差
                rmx[l] = max(rmx[l] , r - 1) ;
                l++; 
                // 以a[r] - a[r - 1]为新的公差前进
            }
        }
        r = n , l = n - 1 ;
        while ( l >= 1 )
        {
            -- l ;
            while (r > l && a[r] - a[r - 1] != a[l + 1] - a[l])
            {
                lmx[r] = min(lmx[r] , l + 1) ;
                r--;
            }
        }
        for(int i = 1 ; i <= n ; ++ i)
        {
            S[i] = max(0ll , rmx[i] - i + 1) ;
            S[i] += S[i - 1] ;
        }

        while ( q-- )
        {
            int l , r;
            cin >> l >> r ;
            if ( rmx[l] >= r ) 
            {
                cout << (r - l + 1) * (r - l + 2) / 2 << '\n' ;
            } else {
                int r1 = (r - lmx[r] + 1) * (r - lmx[r] + 2) / 2 ;
                cout << S[lmx[r] - 1] - S[l - 1] + r1 << '\n' ;
            }
        }
    }
    return 0 ;
}