[CF 549F] Yura and Developers

作法：

通常這種需要考慮區間最大值的題目，可以先令整個數列的最大值的位置為$x$，那麼所有包含了$x$的區間的最大值都會是$x$，這樣問題就變成要如何找有幾個包含$x$的區間，滿足他裡面的總和模$k$是給定的一個數。處理完這個之後就可以拆成$x$左邊和$x$右邊遞迴下去解了。考慮樸素的作法，就是直接枚舉包含了$x$的區間，這樣複雜度會高達$O(n^2)$，不過仔細想想可以發現，假設現在固定了所求區間的右端點，我們想要知道有幾個左端點可以讓這個區間滿足條件，而把一個區間的數的總和改寫成前綴和相減後就可以得到，這個問題就等價於「在前綴和陣列的某一個區間中有幾個數模$k$是某個特定的數」。這可以透過建立模$k$的餘數的所有出現的位置加上二分搜得到答案。於是現在處理上述問題的複雜度變成了其中一邊的長度再乘上$logn$，不過最差狀況下這樣還是會退化到$O(n^2logn)$，而事實上只要每次都取短的那邊去枚舉就好了，這樣複雜度就會是好的。因為當一個點被枚舉到一次時，他所在的區間就至少縮短了兩倍，因此每個點至多被枚舉到$logn$次，所以總複雜度就會是$O(nlog^2n)$。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=300000+10,maxk=1000000,LOG=int(log2(maxn)+1) ;
 
vector<int> v[maxk] ;
inline int query(int l,int r,int x)
{
    int ret=upper_bound(v[x].begin(),v[x].end(),r)-
            lower_bound(v[x].begin(),v[x].end(),l) ;
    return upper_bound(v[x].begin(),v[x].end(),r)-
            lower_bound(v[x].begin(),v[x].end(),l) ;
}
 
int n,a[maxn] ;
int G[LOG][maxn] ;
inline void build()
{
    for(int i=0;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++)
        G[i][j]=(i ?
            (a[G[i-1][j]]>a[G[i-1][j+(1<<(i-1))]] ?
            G[i-1][j] : G[i-1][j+(1<<(i-1))])
        : j) ;
}
 
int getpos(int l,int r)
{
    int len=floor(log2(r-l+1+0.5)) ;
    int x=G[len][l] , y=G[len][r-(1<<len)+1] ;
    return a[x]>a[y] ? x : y ;
}
 
int sum[maxn],k ;
LL solve(int l,int r)
{
    if(l>=r) return 0 ;
    int mid=getpos(l,r) ;
    LL ret=solve(l,mid-1)+solve(mid+1,r) ;
    if(mid<=(r+l)/2) for(int i=l-1;i<mid;i++)
    {
        int val=(sum[i]+a[mid])%k ;
        ret+=query(mid,r,val) ;
    }
    else for(int i=mid;i<=r;i++)
    {
        int val=(sum[i]-a[mid])%k ;
        if(val<0) val+=k ;
        ret+=query(l-1,mid-1,val) ;
    }
    return ret-1 ;
}
 
main()
{
    scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , sum[i]=(sum[i-1]+a[i])%k ;
    for(int i=0;i<=n;i++) v[sum[i]].push_back(i) ;
    build() ;
    printf("%lld\n",solve(1,n)) ;
}