Subtask ~1~

Duyệt ~n^2~ chặn ~2~ cột của hình chữ nhật. Khi đó ta có chiều cao nhỏ nhất là ~p / (j - i + 1)~ và lớn nhất là ~\min(h_i, \cdots, h_j)~.

Subtask ~2~

Duyệt cố định ~H = 1, \cdots, \max(h_i)~ — chiều cao của hình chữ nhật. Với cột ~i~ là cột cuối cùng của hình chữ nhật, ta dễ dàng tìm được cột ~j~ gần nhất bên trái mà chiều cao nhỏ hơn ~H~ ~\rightarrow~ đưa về subtask ~1~.

Subtask ~3~

Đưa về bài toán đơn giản hơn là tìm số hình chữ nhật phân biệt được tạo ra từ biểu đồ.

Subtask ~4~

Xét chiều cao ~H~, quản lý được các đoạn ~[l, r]~ là các đoạn cột liên tiếp có chiều cao ~\ge H~ bằng ~DSU~ khi xét ~H~ giảm dần.

• khi ~H \ge p~, ta đưa về subtaskk ~3~;

• Khi ~H < p~, với mỗi đoạn ~[L, R]~, xét hình chữ nhật có chiều cao ~H~ và diện tích ~\ge p~, ta thấy chiều rộng nhỏ nhất là ~p / H~ và lớn nhất là ~R - L + 1~. Khi đó số hình chữ nhật thoả mãn là ~(R - L + 1 - p / H + 1)~ ~\times~ ~(R - L + 1 - p / H) / 2~ ~\rightarrow~ Với mỗi độ cao ~H~, duyệt qua tất cả các đoạn ~[L, R]~ để tính kết quả. Có thể sử dụng ~BIT~ để tính được tổng này một cách dễ dàng.

Subtask ~5~

Nhật xét rằng chiều rộng của hình chữ nhật chỉ từ ~1~ đến ~n~ ~\rightarrow~ ta chỉ cần quan tâm tới các chiều cao là ~p / i~. Cuối cùng ta có tối đa ~n \times 2~ độ cao cần quan tâm (~h_i~ và ~p / i~, đây là những độ cao mà công thức tính số hình chữ nhật có thể bị thay đổi). Thực hiện tương tự subtask ~4~.

Độ phức tạp: ~\mathcal{O}(NlogN)~.

#include <bits/stdc++.h>
#define int long long
#define maxn 1000006
#define pii pair<int, int>
#define piii pair<int, pii>
#define fi first
#define se second
#define gb(x, i) ((x>>i)&1)
using namespace std;

int n, p, h[maxn], h1[maxn], ans = 0;
bool ok[maxn];

struct BIT{
    int t[maxn];

    void upd(int x, int val)
    {
        while(x > 0)
        {
            t[x] += val;
            x -= x & (-x);
        }
    }
    int get(int x)
    {
        int kq = 0;
        while(x <= n)
        {
            kq += t[x];
            x += x & (-x);
        }
        return kq;
    }
} BitSum, BitMul, BitCnt;

void era(int x)
{
    BitSum.upd(x, - (x + 2) * (x + 1));
    BitMul.upd(x, + (2 * x + 3));
    BitCnt.upd(x, - 1);
}
void add(int x)
{
    BitSum.upd(x, + (x + 2) * (x + 1));
    BitMul.upd(x, - (2 * x + 3));
    BitCnt.upd(x, + 1);
}
int par[maxn], sz[maxn], val[maxn];
vector<int> pos[maxn];
struct heightPoint {
    int F, S;
    bool operator < (const heightPoint &x) const {
        if (F == x.F) return S < x.S;
        return F > x.F;
    }
};
vector <heightPoint> height;

int f(int u)
{
    if(par[u] == 0)return u;
    return par[u] = f(par[u]);
}
void uni(int u, int v)
{
    u = f(u);
    v = f(v);

    if(u != v)
    {
        era(sz[u]);
        era(sz[v]);
        sz[v] += sz[u];
        par[u] = v;
        add(sz[v]);
    }
}
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK "CHART"
    if (fopen(TASK".INP", "r")) {
            freopen(TASK".INP", "r", stdin);
            freopen(TASK".OUT", "w", stdout);
    }

    cin >> n >> p;
    for(int i = 1; i <= n; i ++)cin >> h[i];
    int sum = 0, x;

    // H >= p
    for(int i = 1; i <= n; i ++)
    {
        h1[i] = max(h[i] - p + 1, 0LL);
    }
    stack<int> s;
    s.push(0);
    h1[0] = -1;
    for(int i = 1; i <= n; i ++)
    {
        while(s.size() && h1[s.top()] > h1[i])
        {
            x = s.top();
            s.pop();
            sum = sum - h1[x] * (x - s.top());
        }
        sum = sum + h1[i] * (i - s.top());
        ans += sum;
        s.push(i);
    }

    // H < p

    for(int i = 1; i <= n; i ++)sz[i] = 1;
    for(int i = 1; i <= n; i ++)
    {
        if(h[i] >= p)
        {
            ok[i] = 1;
            add(1);
            if(ok[i-1] == 1)uni(i, i - 1);
            if(ok[i+1] == 1)uni(i, i + 1);
        }
        else
        {
            // pos[h[i]].push_back(i);
            height.push_back({h[i], i});
        }
    }
    for (int i = 2; i <= n; i++) {
        if (p % i == 0 && p / i - 1 > 0) height.push_back({p / i - 1, (int)1e9});
        else if (p % i && p / i > 0) height.push_back({p / i, (int)1e9});
    }
    // độ cao giảm dần -> chiều rộng tăng dần
    // độ cao cuối cùng mà chiều rộng = 1 -> p
    // độ cao cuối cùng mà chiều rộng = 2 -> p/2
    // -> khoảng độ cao mà x = 2 là (p/2 -> p - 1)
    // độ cao cuối cùng mà chiều rộng = 3 -> p/3
    // độ cao cuối cùng mà chiều rộng = n -> p/n
    sort(height.begin(), height.end());
    long long curHeight = p - 1;
    x = 2;
    for (int i = 0; i < (int)height.size(); i++) {
        auto [H, state] = height[i];
        if ((i == 0 && height[i].F != p - 1) || (height[i].F != height[i - 1].F)) {
            ans = ans + 1ll * (curHeight - H) * (BitSum.get(x) + x * BitMul.get(x) + BitCnt.get(x) * x * x) / 2;
        }
        if (state != (int)1e9) {
            ok[state] = 1;
            add(1);
            if (ok[state - 1] == 1) uni(state, state - 1);
            if (ok[state + 1] == 1) uni(state, state + 1);
        }
        curHeight = H;
        x = (p + H - 1) / H;
    }
    ans = ans + 1ll * curHeight * (BitSum.get(x) + x * BitMul.get(x) + BitCnt.get(x) * x * x) / 2;
    // for(int H = p - 1; H >= 1; H --)
    // {
    //     for(int i : pos[H])
    //     {
    //         ok[i] = 1;
    //         add(1);
    //         if(ok[i-1] == 1)uni(i, i - 1);
    //         if(ok[i+1] == 1)uni(i, i + 1);
    //     }
    //     int x = (p + H - 1) / H;
    //     ans = ans + (BitSum.get(x) + x * BitMul.get(x) + BitCnt.get(x) * x * x) / 2;
    // }
    cout << ans;
}
/*

len >= x

(len - x + 2) * (len - x + 1)
 (len + 2) * (len + 1) + x * x - x * (len + 2 + len + 1)

*/