//区间的个数是确定的，n的阶加，每个区间的核心数是确定的，找到后在对应数组下标记录
#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
int cnt[N], res[N], bk[N];
int n, a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];

    for (int i = 0; i < n; ++ i) {
        int cnt[N] = {};
        for (int j = i, h = 0; j < n; ++ j) {
            cnt[a[j]]++;
            if (cnt[a[j]] > cnt[h] || cnt[a[j]] == cnt[h] && a[j] < h) h = a[j];
            res[h]++;
        }
    }

    for (int i = 1; i <= n; ++ i)
        cout <<res[i] << ' ';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1E3+10;
int a[N], n;

int main() {
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 2; i <= n-1; ++ i)
        if (a[i] > a[i-1] && a[i] > a[i+1] || 
            a[i] < a[i-1] && a[i] < a[i+1])
            res++;
    cout << res;
    return 0;
}

算法1：双重循环(暴力枚举) $O(n^2)$

#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
    getline(cin, a);
    getline(cin, b);

    a = " " + a + " ";
    b = " " + b + " ";

    //统一格式
    for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
    for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

    int p = -1, cnt = 0;
    for (int i = 0; i < b.size(); ++ i) {
        if (b[i] == a[0]) { //开头相等-进入遍历
            int j = 0;
            while (b[i+j] == a[j]) j++;
            if (j == a.size()) {
                if (p == -1) p = i;
                cnt ++;
            }
            // bool f = 1; //for循环遍历，标记
            // for (int j = 0; j < a.size(); ++ j) 
            //     if (b[i+j] != a[j]) {
            //         f = 0;
            //         break;
            //     }
            // if (f) {
            //     if (p == -1) p = i;
            //     cnt ++;
            // }
        }
    }
    if (cnt) cout << cnt << " " << p;
    else cout << -1;
    return 0;
}

算法2：调用库函数-双重循环() $O(n^2)$

#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
    getline(cin, a);
    getline(cin, b);
    a = " " + a + " ";
    b = " " + b + " ";

    //统一格式
    for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
    for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

    //利用find函数查找 找不到，返回的是2的64次方-1，内存中64位全部是1，就是-1
    int p = b.find(a), cnt = 0, st;

    if (p != -1) {
        st = p; //记录第一次出现的位置
        cnt++;
        while ((p = b.find(a, p+1)) != -1) cnt++;
        cout << cnt << ' ' << st;
    } else {
        cout << -1;
    }
    return 0;
}

算法3：把连续不含空格的单词拼接起来，判断是否相等() $O(n^2)$

#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
    getline(cin, a);
    getline(cin, b);

    //统一格式
    for (int i = 0; i < a.size(); ++ i) a[i] = toupper(a[i]); //tolower()
    for (int i = 0; i < b.size(); ++ i) b[i] = toupper(b[i]);

    b = b + ' ';//确保最后能走到else中 判断是否相等 

    string t = "";
    int p  = -1, cnt = 0;
    for (int i = 0; i < b.size(); ++ i) {
        if (b[i] != ' ') t += b[i]; //连续字符就拼接起来
        else { //是空格
            if (t == a) {
                cnt++;
                if (cnt == 1) p = i - a.size();
            }
            t = "";
        }
    }
    if (p != -1) cout << cnt << ' ' << p;
    else cout << p;
    return 0;
}

算法1：双指针-扫描连续段() $O(n)$

//最大值就是最大平均值， 找最大值连续出现的长度
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int a[N], n, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int mx = -1, res = 0;
        for (int i = 0; i < n; ++ i) {
            scanf("%d", &a[i]);
            mx = max(mx, a[i]);
        } 
        //1. 变量记录的方式
        int len = 0;
        for (int i = 0; i < n; ++ i) {
            if (a[i] == mx) len++; //连续相等就累加
            else len = 0; //最大值中断了，清零，从新计数
            res = max(res, len); 
        }

        //2. 双指针扫描的方式
        // for (int i = 0; i < n; ++ i) 
        //     if (a[i] == mx) { 
        //         int j = i;
        //         while (a[j] == mx && j < n) j++;
        //         res = max(res, j-i);
        //         i = j;
        //     }
        printf("%d\n", res);
    }
    return 0;
}

算法2：变量维护最大值及其连续长度() $O(n)$

#include <bits/stdc++.h>
using namespace std;

int n, T, x;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int res = 1, mx = -1, len = 0; //len记录当前最大值连续长度 mx最大值 res最大长度
        while (n--) {
            scanf("%d,", &x);
            if (x > mx) mx = x, res = len = 1; //值最大优先，值最大的前提下 长度多
            else if (x == mx) len++, res = max(res, len);
            else len = 0;
        }
        printf("%d\n", res);
    }
    return 0;
}

算法1：贪心-区间分组(476ms) $O(nlogN)$

//每个区间必然属于某一个组，对每一个组看是否能加入之前的组，之前组的右端点小于 该区间的左端点可加入
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1E5+10;
PII a[N];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d%d", &a[i].first, &a[i].second);
    sort(a, a+n);

    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; ++ i) 
        if (heap.empty() || heap.top() >= a[i].first) heap.push(a[i].second);
        else {
            heap.pop();
            heap.push(a[i].second); //更新该区间的最靠右的右端点
        }
    printf("%d", (int)heap.size());
    return 0;
}

算法2：离散化-差分(1041ms) $O(nlogN)$

//离散化-差分，求前缀和，被覆盖最多的就是最小组数
#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;
int n, res;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
        int l, r;
        scanf("%d%d", &l, &r);
        mp[l] ++;
        mp[r+1] --;
    }
    int s = 0; //求前缀和，过程中维护出最大值
    for (auto [k, v] : mp) {
        s += v;
        res = max(res, s);
    }
    printf("%d", res);
    return 0;
}

y总题解： https://www.acwing.com/solution/content/1061/
左端点排序操作细节： https://www.acwing.com/solution/content/10615/
画图清晰的： https://www.acwing.com/solution/content/123740/

算法1：贪心-区间选点-排序(结构体存储) $O(nlogN)$

//转换：雷达放那可以覆盖当前小岛，转换到某一个区间；
//问题抽象：给定若干区间，最少选择多少个点，使得每个区间上至少有一个点；
//知识应用：同模板905题，区间选点
//贪心策略：
//1. 将所有区间按右端点排序；时间瓶颈在排序，NlogN，数据范围可以到10万级别
//   按左端点排序也可以，倒着扫描或者维护出右端点的最小值
//2. 依次扫描每个线段，
//   情况1，上次选择的点不在当前区间，则选择当前区间右端点，更有可能覆盖后面的；
//   情况2，上次选择的点在区间内，则当前区间已经被覆盖，直接看下一个区间
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
struct node{
    double l, r;
    bool operator< (const node& t) const{
        return r < t.r; //按照右端点排序
    }
}a[N];
int n, d, res;

int main() {
    cin >> n >> d;
    for (int i = 0, x, y; i < n; ++ i) {
        cin >> x >> y;
        if (y > d) { //y坐标大于了雷达半径 无法覆盖
            cout << -1;
            return 0;
        }
        double len = sqrt(d*d - y*y);
        a[i] = {x - len, x + len};
    }
    sort(a, a+n);
    double last = -2e9; 
    for (int i = 0; i < n; ++ i)
        if (a[i].l > last) {
            last = a[i].r;
            res++;
        }
    cout << res;
    return 0;
}

算法2：贪心-区间选点-排序(pair存储) $O(nlogN)$

#include <bits/stdc++.h>
using namespace std;

typedef pair<double, double> PDD;
const int N = 1010;
PDD a[N];
int n, d;

int main() {
    cin >> n >> d;
    for (int i = 0, x, y; i < n; ++ i) {
        cin >> x >> y;
        if (y > d) {
            cout << -1;
            return 0;
        }
        double len = sqrt(d*d - y*y); //勾股定理计算出长度
        a[i] = {x+len, x-len}; //按照右端点排序，所有右端点放在first位置
    }
    sort(a, a+n);
    int cnt = 0;
    double last = -2e9;
    for (int i = 0; i < n; ++ i)
        if (a[i].second > last) {
            cnt ++;
            last = a[i].first;
        }
    cout << cnt;
    return 0;
}

算法1：数组维护前k个商品编号() $O(NKlogK)$

//只排序前k个商品编号，统计每个商品访问次数，50000 * 10 * 3  操作*排序
#include <bits/stdc++.h>

using namespace std;

const int N = 5E4+10;
int cnt[N], a[14], n, m;

int main() {
    scanf("%d%d", &n, &m);
    int k = 0;
    for (int i = 0, id; i < n; ++ i) {
        scanf("%d", &id);
        if (i) {
            printf("%d: ", id);
            for (int j = 0; j < k; ++ j) printf("%d ", a[j]);
            printf("\n");
        }
        cnt[id]++;
        bool f = 1; //查看一下id是否已经在a数组中, 默认不在，需要加进去
        for (int j = 0; j < k; ++ j) 
            if (a[j] == id) 
                f = 0;
        if (f) a[k++] = id; //k记录数量
        sort(a, a+k, [](int x, int y){ //匿名函数-lambda表达式
            if (cnt[x] != cnt[y]) return cnt[x] > cnt[y];
            return x < y;
        });
        k = min(k, m); //最多m个，k当前实际有的
    }

    return 0;
}

算法2：set-map维护() $O(nlogm)$

//set维护次数-商品，次数负数表示，map正常存储商品-次数；次数更新时，set要删除
//常数比较大
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
set<PII> s; //默认是升序排序，小的在前，
map<int, int> cnt;
int n, m;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, id; i < n; ++ i) {
        scanf("%d", &id);
        if (i) {
            printf("%d: ", id);
            int j = 0;
            for (auto item : s) {
                if (++j > m) break;
                printf("%d ", item.second);
            }
            printf("\n");
        }
        if (!cnt[id]) { //没有出现，就加入进去
            cnt[id] = 1;
            s.insert({-1, id});
        } else {
            s.erase({-cnt[id], id}); //删除原有的次数
            cnt[id] = cnt[id] + 1;
            s.insert({-cnt[id], id}); //重新插入
        }

    }
    return 0;
}

算法1：模拟-字符串-操作-map(枚举) $O(n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int n;
string a[N];
unordered_map<string, int> mp;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    for (int i = 0; i < n; ++ i) {
        string x, y;
        int m, t;
        cin >> x >> m >> t;
        if (!t) continue;  //t为0，跳过，发给0个人，细节，不然有除0错误
        mp[x] -= m/t * t; //x减去要发出去的钱
        for (int i = 0; i < t; ++ i) {
            cin >> y;
            mp[y] += m/t; //y加上收到的钱
        }
    }
    for (int i = 0; i < n; ++ i) 
        cout << a[i] << ' ' << mp[a[i]] << endl;
    return 0;
}

算法2：模拟-字符串转换() $O(1)$

//字符串处理，转换为数字
#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
    cin >> a >> b;
    int x = 1, y = 1;
    for (int i = 0; i < a.size(); ++ i) x *= (a[i] - 'A' + 1);
    for (int i = 0; i < b.size(); ++ i) y *= (b[i] - 'A' + 1);

    if (x%47 == y%47) cout << "GO";
    else cout << "STAY";
    return 0;
}

算法1：封装成函数-字符串转换(暴力枚举) $O(1)$

//字符串处理，转换为数字
#include <bits/stdc++.h>
using namespace std;

string a, b;
int get(string s) {
    int res = 1; //最多6个字符，每个字母都是z, 就是26的6次方，3亿 不会超int
    for (int i = 0; i < s.size(); ++ i) 
        res = res * (s[i] - 'A' + 1);
    return res % 47;
}
int main() {
    cin >> a >> b;
    if (get(a) == get(b)) cout << "GO";
    else cout << "STAY";
    return 0;
}

算法1：循环(枚举) $O(n)$

//计算出左右两边回到当前点距离2倍的最小值
#include <bits/stdc++.h>
using namespace std;

int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        int l = abs(i-1) * 2, r = abs(n-i) * 2;
        cout << max(l, r) << endl;
        //cout << max(i-1, n-i) * 2 << endl;
    }
    return 0;
}