Untitled
unknown
c_cpp
a year ago
3.8 kB
10
Indexable
#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], pre[N], L[N], R[N];
vector<int> divs[N];
namespace BRUTE {
void solve() {
int ans = 0;
forlr(i, 1, n) {
int M = INF, S = 0;
forlr(j, i, n) {
M = min(M, a[j]);
S += a[j];
int v = __gcd(M, S);
if(M + S == v * k) ans++;
}
}
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;
int sum = 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;
int sum = 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 <= 100000; j += i) {
divs[j].push_back(i);
}
}
}
inline void show_divisors() {
int mx = 0;
forlr(i, 1, 100000) {
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("A.INP", "r", stdin);
// freopen("A.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();
FULL::solve();
// BRUTE::solve();
return 0;
}Editor is loading...
Leave a Comment