Untitled

 avatar
user_7653193
c_cpp
18 days ago
3.9 kB
4
Indexable
Never
#include <bits/stdc++.h>

#define ll long long
#define II pair<int, int>
#define fs first
#define sc second
#define endl '\n'

#define mp(x, y) make_pair(x, y)
#define sz(x) ((int) (x.size()))
#define forlr(i, l, r) for(int i = l; i <= r; ++i)
#define forrl(i, r, l) for(int i = r; i >= l; --i)
#define show(v) for(auto i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl;
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end());

const long long LINF = 1ll << 60;
const int INF = 1 << 30;
const int N = 2e5 + 5;

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 

int n, k;
int a[N], L[N], R[N];
ll pre[N];
vector<int> divs[N];

namespace BRUTE {
    void solve() {
        int ans = 0;
        forlr(i, 1, n) {
            int M = INF;
            ll S = 0;
            forlr(j, i, n) {
                M = min(M, a[j]);
                S += a[j];
                int v = __gcd(M * 1ll, S);
                if(M + S == 1ll * v * k) {
                    ans++;
                    cout << i << " " << j << " " << M / v << " " << S / v << endl;
                }
            }
        }

        cout << ans << endl;
    }
}

namespace FULL {

    int ans = 0;

    inline void dnc(int l, int r) {
        if(l == r) return;

        int mid = (l + r) >> 1;

        int mn = mid + 1;
        forlr(i, mid + 1, r) {

            if(a[i] < a[mn]) mn = i;
            
            int Left = max(l, L[mn]), Right = mid;

            for(int v : divs[a[mn]]) {
                if(Left > Right) break;


                ll sum = 1ll * a[mn] / v * (k - v);
                int x = lower_bound(pre + Left - 1, pre + Right - 1, pre[i] - sum) - pre;
                
                Right = x;
                if(pre[i] - pre[x] == sum) ans++;
                else Right++;
            }
        }

        mn = mid;

        forrl(i, mid, l) {

            if(a[i] < a[mn]) mn = i;
            
            int Left = mid + 1, Right = min(r, R[mn]);

            for(int v : divs[a[mn]]) {
                if(Left > Right) break;

                ll sum = 1ll * a[mn] / v * (k - v);
                int x = lower_bound(pre + Left, pre + Right, pre[i - 1] + sum) - pre;

                Left = x;
                if(pre[x] - pre[i - 1] == sum) ans++;
            }
        }

        
        dnc(l, mid);
        dnc(mid + 1, r);
    }

    void solve() {
        dnc(1, n);
        cout << ans << endl;
    }
}

inline void create_divisors() {
    forrl(i, k / 3, 1) {
        if(__gcd(i, k - i) != 1) continue;
        for(int j = i; j <= 10000; j += i) {
            divs[j].push_back(i);
        }
    }
}

inline void show_divisors() {
    int mx = 0;
    forlr(i, 1, 10000) {
        if(sz(divs[i]) > mx) {
            mx = sz(divs[i]);
            cout << i << " " << mx << endl;
        }
    }
}

inline void create_monotonic_stacks() {
    stack<int> st;

    forlr(i, 1, n) {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        L[i] = st.empty() ? 1 : st.top() + 1;
        st.push(i);
    }

    while(!st.empty()) st.pop();

    forrl(i, n, 1) {
        while(!st.empty() && a[st.top()] > a[i]) st.pop();
        R[i] = st.empty() ? n : st.top() - 1;
        st.push(i);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    freopen("D.INP", "r", stdin);
    freopen("D.OUT", "w", stdout);

    cin >> n >> k;

    forlr(i, 1, n) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    create_monotonic_stacks();
    create_divisors();
    // show_divisors();
    // return 0;

    FULL::solve();
    // BRUTE::solve();

    return 0;
}
Leave a Comment