2015年6月10日 星期三

[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)) ;
}
 

沒有留言:

張貼留言