include <bits></bits>

using namespace std;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

int N, K;
cin >> N >> K;
vector<long long> a(N);
for(int i = 0; i < N; i++) cin >> a[i];

unordered_map<long long, vector<int>> pos;
pos.reserve(N * 2);

for(int i = 0; i < N; i++)
    pos[a[i]].push_back(i + 1);

long long ans = 0;

for(auto &p : pos){
    auto &v = p.second;
    int t = v.size();
    if(t < K) continue;

    for(int i = 0; i + K - 1 < t; i++){
        for(int j = i + K - 1; j < t; j++){
            int c = j - i + 1;
            int maxLen = 2 * c - 1;

            int Lmin = v[j] - maxLen + 1;
            int Lmax = v[i];

            int Rmin = v[j];
            int Rmax = v[i] + maxLen - 1;

            Lmin = max(Lmin, 1);
            Lmax = min(Lmax, v[i]);

            Rmin = max(Rmin, v[j]);
            Rmax = min(Rmax, N);

            if(Lmin > Lmax || Rmin > Rmax) continue;

            long long total = 1LL * (Lmax - Lmin + 1) * (Rmax - Rmin + 1);
            ans += total;
        }
    }
}

cout << ans;

}

Cho mảng gồm 𝑁 N số nguyên dương 𝐴 1 , 𝐴 2 , … , 𝐴 𝑁 A 1 ​

,A 2 ​

,…,A N ​

và một số nguyên 𝐾 K.

Một đoạn con liên tiếp [ 𝐿 , 𝑅 ] [L,R] được gọi là K-dominant nếu tồn tại một giá trị 𝑋 X sao cho:

số lần xuất hiện của 𝑋 X trong đoạn lớn hơn tổng số lần xuất hiện của tất cả các giá trị khác trong đoạn (tức là 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) > ( 𝑅 − 𝐿 + 1 ) − 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) freq(X)>(R−L+1)−freq(X))

và đồng thời 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) ≥ 𝐾 freq(X)≥K.

Hãy đếm số lượng đoạn con K-dominant.

Ràng buộc:

1 ≤ 𝑁 ≤ 2 × 10 5 1≤N≤2×10 5

1 ≤ 𝐴 𝑖 ≤ 10 9 1≤A i ​

≤10 9

1 ≤ 𝐾 ≤ 𝑁 1≤K≤N

Input:

N K A1 A2 ... AN

Output: In ra một số nguyên là số đoạn con K-dominant.

Ví dụ:

Input 6 2 1 2 2 2 3 2

Output 7

Mẹo sinh test cực nhanh

Bình thường các bạn làm bài như nào thì cứ làm như thế(tạo project xog add INP và OUT rồi làm)
Khi muốn sinh test và so sánh code trâu và code full thì tạo 1 folder mới
- Tạo file main_trau.cpp và dán code trâu vào
- Tạo file main.cpp và dán code full vào
- Tạo file test.cpp và code sinh test(có thể đọc ở dưới blog của tôi)
Sử dụng lệnh cmd để build file cpp ra exe:
** ĐỂ CHẠY NHANH THÌ CÁC BẠN COPY HẾT CẢ 3 DÒNG VÀ CLICK CHUỘT PHẢI VÀO CMD, KHÔNG PHẢI COPY TỪNG DÒNG 1 VÀ CHẠY TỪNG LỆNH 1

g++ test.cpp -o test
g++ main.cpp -o main
g++ main_trau.cpp -o main_trau

Cuối cùng là chạy test.exe

Quy hoạch động (DP) là một kỹ thuật thuật toán thường dựa trên một công thức truy hồi và một (hoặc một vài) trạng thái khởi đầu. Một lời giải con của bài toán được xây dựng từ các lời giải trước đó. Các thuật toán DP có độ phức tạp đa thức, giúp đảm bảo thời gian chạy nhanh hơn nhiều so với các kỹ thuật khác như quay lui (backtracking) hay brute-force.

I. BÀI TOÁN ĐỔI TIỀN

Cho một danh sách gồm N đồng xu với giá trị V1, V2, ..., VN và một tổng tiền cần đạt được là S. Hãy tìm số lượng đồng xu ít nhất sao cho tổng của chúng bằng S (có thể sử dụng một đồng xu nhiều lần), hoặc kết luận rằng không thể chọn được tập hợp đồng xu thỏa mãn điều kiện.

1. Xác định trạng thái

Ta gọi Min[i] là số lượng đồng xu ít nhất để tạo ra tổng i (với i ≤ S). Trạng thái nhỏ hơn của i là mọi Min[j] với j < i.

1. Khởi tạo

• Min[0] = 0 (tổng 0 không cần đồng xu nào)
• Với mọi i > 0: Min[i] = ∞

1. Công thức truy hồi

Với mỗi i từ 1 đến S:

• Với mỗi đồng xu Vj sao cho Vj ≤ i: Min[i] = min(Min[i], Min[i - Vj] + 1)

1. Ví dụ minh họa

Các đồng xu: 1, 3, 5 Tổng cần đạt: S = 11

Sau khi tính toán theo quy hoạch động, ta có: Min[11] = 3

Tập đồng xu tối ưu là: 5, 5, 1.

II. BÀI TOÁN DÃY CON KHÔNG GIẢM DÀI NHẤT

Cho dãy số A[1], A[2], ..., A[N]. Hãy tìm độ dài lớn nhất của dãy con không giảm.

1. Xác định trạng thái

Gọi S[i] là độ dài của dãy con không giảm dài nhất kết thúc tại phần tử A[i].

1. Khởi tạo

Với mọi i: S[i] = 1

1. Công thức truy hồi

Với mỗi i từ 1 đến N:

• Với mỗi j < i: Nếu A[j] ≤ A[i] thì: S[i] = max(S[i], S[j] + 1)

1. Ví dụ minh họa

Dãy số: 5, 3, 4, 8, 6, 7

Bảng kết quả:

i A[i] S[i] 1 5 1 2 3 1 3 4 2 4 8 3 5 6 3 6 7 4

Kết luận: Độ dài dãy con không giảm dài nhất là 4. Cảm ơn các bạn đã đọc :>

code:

#define cel                 cout<<'\n'
#define dbg(...)            [](auto&&...x) {int i=0; ((ct<<(i++?" " : "")<<x),...),cel;} (__VA_ARGS__)

khi gọi dbg() và thêm các tham số vào dấu ngoặc đồng thời ngăn cách bởi dấu ',' thì hàm sẽ in hết các giá trị ra màn hình cách nhau bởi dấu cách sau đó xuống dòng