Looksery Cup 2015 F - Yura and Developers 单调栈+启发式合并

F - Yura and Developers

第一次知道单调栈搞出来的区间也能启发式合并。。。

你把它想想成一个树的形式， 可以发现确实可以启发式合并。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 3e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, k, tot, a[N], stk[N], L[N], R[N], sum[N];

vector<int> num[];

void add(int &a, int b) {

    a += b; if(a >= mod) a -= mod;

}

int cal(int x, int l, int r) {

    auto it1 = upper_bound(num[x].begin(), num[x].end(), r);

    auto it2 = lower_bound(num[x].begin(), num[x].end(), l);

    return it1 - it2;

}

int main() {

    scanf("%d%d", &n, &k);

    num[].push_back();

    for(int i = ; i <= n; i++) {

       scanf("%d", &a[i]);

       sum[i] = (sum[i-]+a[i]%k)%k;

       num[sum[i]].push_back(i);

    }

    a[] = a[n+] = inf;

    stk[++tot] = ;

    for(int i = ; i <= n; i++) {

        while(tot && a[stk[tot]] < a[i]) tot--;

        L[i] = stk[tot];

        stk[++tot] = i;

    }

    tot = ;

    stk[++tot] = n+;

    for(int i = n; i >= ; i--) {

        while(tot && a[stk[tot]] <= a[i]) tot--;

        R[i] = stk[tot];

        stk[++tot] = i;

    }

    LL ans = ;

    for(int i = ; i <= n; i++) {

        if(i - L[i] < R[i] - i) {

            for(int j = L[i]; j < i; j++)

                ans += cal((sum[j]+a[i])%k, i, R[i]-);

        } else {

            for(int j = i; j < R[i]; j++) {

                ans += cal((sum[j]-(a[i]%k)+k)%k, L[i], i-);

            }

        }

    }

    printf("%lld\n", ans - n);

    return ;

}

/*

*/