Codeforces 549F Yura and Developers

青旅半醒 2022-03-27 04:26 98阅读 0赞

[probelm][]

## 题意 ##

给定一个序列和一个mod值，定义`[l,r]`合法当`l`到`r`的全部元素和减去当中的最大值的结果能够整除mod。问共同拥有多少区间合法。

## 思路 ##

一開始想的分治。

对于一个`[l,r]`我们能够把这之中最大的求出来，然后以这个数作为分界，把这个区间分成两部分，对于分布在两个区间中的答案，我们能够通过lowerbound和upperbunder在O(log(n))的时间下求出，然后递归求解。

然而对于这题，这样的做法的下界会达到O(n2)。所以这样做不行。

。

*  看了题解，题讲解能够直接枚举那个最大值，然后把满足的区间找出来然后求出来。豁然开朗。这样我们仅仅须要把原数组进行排序，并记录每一个数的左右界。
    
    从最小的開始。在计算答案的同一时候去更新这个左右界。
    
    这样能够在O(nlog(n))的复杂度下求出答案。
 *  一道不错的题。希望以后能够坚持把每次做的比赛的题目补完。

## AC代码 ##

/*************************************************************************
        > File Name: pf.cpp
        > Author: znl1087
        > Mail: loveCJNforever@gmail.com 
        > Created Time: 四  6/11 16:36:14 2015
     ************************************************************************/
    
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <string>
    #include <cstdlib>
    #include <vector>
    #include <set>
    #include <map>
    #define LL long long
    using namespace std;
    int n,k;
    LL s[300005];
    vector<int> f[1000005];
    LL num[300005];
    int pre[300005],nxt[300005];
    LL ask(int l,int r,LL in){
        return upper_bound(f[in].begin(),f[in].end(),r)-lower_bound(f[in].begin(),f[in].end(),l);
    }
    LL cal(int m){
        int l = pre[m]+1,r = nxt[m]-1;
        LL maxn = num[m];
        LL ans = 0;
        if( r - m < m - l){
            for(int i=m+1;i<=r;i++)
                ans+=(ask(l-1,m-1,(s[i]-maxn%k+k)%k));
            ans+=(ask(l-1,m-2,(s[m]-maxn%k+k)%k));
        }else{
            for(int i=l;i<m;i++)
                ans+=(ask(m,r,(s[i-1]+maxn)%k));
            ans+=(ask(m+1,r,(s[m-1]+maxn)%k));
        }
        pre[nxt[m]] = pre[m];
        nxt[pre[m]] = nxt[m];
        return ans;
    }
    int ord[300005];
    int cmp(int a,int b){
        return num[a]<num[b];
    }
    int main(){
        cin>>n>>k;
        s[0] = 0;
        for(int i=1;i<=n;i++){
            cin>>num[i],s[i] = (s[i-1]+num[i])%k,ord[i] = i;
            pre[i] = i-1;
            nxt[i] = i+1;
        }
        nxt[0] = 1;
        nxt[n] = n+1;
        pre[n+1] = n;
        for(int i=0;i<=n;i++)f[s[i]].push_back(i);
        sort(ord+1,ord+n+1,cmp);
        LL ans = 0;
        for(int i=1;i<=n;i++){
            int pos = ord[i];
            ans+=cal(pos);
        }
        cout<<ans<<endl;
        return 0;
    }

[probelm]: http://codeforces.com/problemset/problem/549/F