2015年7月4日 星期六

2015/07/04 Codeforces 549F. Yura and Developers

/*
    每個任務i
    有他是最大的區間 (L[i], R[i])

    邊界比較近的一邊用枚舉的
    另一邊二分搜
    
    不互相包含的區間
    不會互相重疊 複雜度預估 O(Nlg^2N)
*/
// http://codeforces.com/problemset/problem/549/F
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int N, K;
int A[400000];

int id[400000];
int rk[400000];
bool id_cmp(int a, int b){ return A[a] > A[b]; }

int pre[400000], suf[400000];
int L[400000], R[400000];

vector<int> P[2000000], S[2000000];

int P_cnt(int p, int l, int r)
{
    return lower_bound(P[p].begin(), P[p].end(), r)-
            lower_bound(P[p].begin(), P[p].end(), l);
}

int S_cnt(int p, int l, int r)
{
    return lower_bound(S[p].begin(), S[p].end(), l, greater<int>())-
            lower_bound(S[p].begin(), S[p].end(), r, greater<int>());
}

int main()
{
    scanf("%d %d", &N, &K);

    for(int Ni = 1; Ni <= N; Ni++)
    {
        scanf("%d", &A[Ni]);
        id[Ni] = Ni;
    }

    sort(id+1, id+N+1, id_cmp);
    for(int Ni = 1; Ni <= N; Ni++)
        rk[id[Ni] ] = Ni;

    rk[0] = 0, rk[N+1] = 0;

    P[0].push_back(0); S[0].push_back(N+1);
    for(int Ni = 1; Ni <= N; Ni++) pre[Ni] = (pre[Ni-1]+A[Ni])%K, P[pre[Ni] ].push_back(Ni);
    for(int Ni = N; Ni >= 1; Ni--) suf[Ni] = (suf[Ni+1]+A[Ni])%K, S[suf[Ni] ].push_back(Ni);

    stack<int> stk;

    while( !stk.empty() ) stk.pop();
    stk.push(0);
    for(int Ni = 1; Ni <= N; Ni++)
    {
        while( rk[stk.top() ] > rk[Ni] ) stk.pop();
        L[Ni] = stk.top();
        stk.push(Ni);
    }

    while( !stk.empty() ) stk.pop();
    stk.push(N+1);
    for(int Ni = N; Ni >= 1; Ni--)
    {
        while( rk[stk.top() ] > rk[Ni] ) stk.pop();
        R[Ni] = stk.top();
        stk.push(Ni);
    }

    long long Ans = 0;

    for(int Ni = 1; Ni <= N; Ni++)
    {
        if( R[Ni]-Ni <= Ni-L[Ni] )
        {
            for(int Nj = Ni; Nj < R[Ni]; Nj++)
            {
                int t = (K-(pre[Nj]-pre[Ni]) )%K;
                int p = (pre[Ni-1]-t+K)%K;

                Ans += P_cnt(p, L[Ni], Ni);
            }
        }
        else
        {
            for(int Nj = Ni; Nj > L[Ni]; Nj--)
            {
                int t = (K-(suf[Nj]-suf[Ni]) )%K;
                int p = (suf[Ni+1]-t+K)%K;

                Ans += S_cnt(p, Ni, R[Ni]);
            }
        }

        Ans--;
    }

    cout<<Ans<<endl;
}

沒有留言:

張貼留言