#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 200010;
int c2[N],c5[N],s2[N],s5[N];
int n, k;

int main ()
{
    int T;
    cin >> T;
    while(T --){
        cin >> n >> k;
        for(int i = 1; i <= n; i ++)
        {
            c2[i] = c5[i] = 0;
            int x;
            cin >> x;
            while(x % 2 == 0) c2[i] ++, x /= 2;
            while(x % 5 == 0) c5[i] ++, x /= 5;
            s2[i] = s2[i - 1] + c2[i];
            s5[i] = s5[i - 1] + c5[i];
        }
        LL res = 0;
        for(int i = 1; i <= n; i ++){
            int l1 = lower_bound(s2 + i, s2 + 1 + n, s2[i - 1] + k) - s2;
            int r1 = upper_bound(s2 + i, s2 + 1 + n, s2[i - 1] + k) - s2;
            int l2 = lower_bound(s5 + i, s5 + 1 + n, s5[i - 1] + k) - s5;
            int r2 = upper_bound(s5 + i, s5 + 1 + n, s5[i - 1] + k) - s5;
            int L = max(l1, l2), R = max(r1, r2);
            res += max(0, R - L);
        }
        cout << res << endl;
    }
    return 0;
}

https://codeforces.com/contest/229/problem/B

输入 n(2≤n≤1e5) m(0≤m≤1e5) 表示一个 n 点 m 边的无向图（节点编号从 1 开始）。
然后输入 m 条边，每条边包含 3 个数 a b c(1≤c≤1e4)，表示有一条边权为 c 的无向边连接 a 和 b，表示从 a 到 b 需要 c 秒。保证无自环、无重边。然后输入 n 行，每行第一个数 k 表示数组 t[i] 的长度，然后输入数组 t[i]。
数组 t[i] 是一个严格递增序列，0≤t[i][j]<1e9。所有 k 之和 ≤1e5。

初始时间为 0。你从 1 出发，要去 n。如果你在点 i，但是当前时间在数组 t[i] 中，那么你必须等待 1 秒。如果下一秒仍然在 t[i] 中，那么继续等待 1 秒。依此类推。
输出到达 n 的最早时间。
如果无法到达 n，输出 -1。
输入
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
输出 7

输入
3 1
1 2 3
0
1 3
0
输出 -1

v存储所有连续的区间

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 100010, M = 2 * N;
const long long INF = 1e18;

int n, m;
int e[M], w[M], ne[M], h[N], idx;
vector<pair<int,int>> v[N];
LL dis[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void D()
{
    for(int i = 1; i <= n; i ++) dis[i] = 1e18;

    if(v[1].size() > 0){
        if(v[1][0].first == 0) dis[1] = v[1][0].second + 1;
        else dis[1] = 0;
    } 
    else dis[1] = 0;

    priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
    heap.push({dis[1], 1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int u = t.second;
        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];

            if(dis[j] > dis[u] + w[i]){
                dis[j] = dis[u] + w[i];
                if(v[j].size() > 0 && j != n)
                {
                    int l = 0, r = v[j].size() - 1;
                    while(l < r){
                        int mid = l + r + 1 >> 1;
                        if(v[j][mid].first <= dis[j]) l = mid;
                        else r = mid - 1;
                    }
                    if(v[j][r].first <= dis[j] && v[j][r].second >= dis[j]) dis[j] = v[j][r].second + 1;
                }

                heap.push({dis[j], j});
            }
        }
    }
}
int main ()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for(int i = 1; i <= n; i ++){
        int k;
        cin >> k;
        vector<int> w;
        if(k > 0)
        {
            for(int j = 0; j < k; j ++)
            {
                int x;
                cin >> x;
                w.push_back(x);
            }
            for(int a = 0; a < k; a ++)
            {
                int b = a;
                while(b + 1 < k && w[b + 1] == w[b] + 1) b ++;

                v[i].push_back({w[a], w[b]});
                a = b;
            }
        }
    }

    D();
    if(dis[n] > INF / 2) puts("-1");
    else cout << dis[n] << endl;
    return 0;
}

https://codeforces.com/problemset/problem/1759/G

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入偶数 n(2≤n≤2e5) 和长为 n/2 的数组 b(1≤b[i]≤n)，下标从 1 开始。

构造一个长为 n 的 1~n 的排列 p（下标从 1 开始），满足 max(p[2i-1],p[2i]) = b[i]。
如果无法构造，输出 -1，否则输出字典序最小的 p。
输入
6
6
4 3 6
4
2 4
8
8 7 2 3
6
6 4 2
4
4 4
8
8 7 4 5
输出
1 4 2 3 5 6
1 2 3 4
-1
5 6 3 4 1 2
-1
1 8 6 7 2 4 3 5

倒序遍历找到小于b[i]的最大且没有被使用过的数

并查集能快速判断 如果一个数s被使用了，那么它的祖先指向s - 1的祖先

#include <bits/stdc++.h>

using namespace std;

vector<int> p;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void solve()
{
    int n;
    cin >> n;
    vector<int> ans(2 * n + 1), b(n + 1);
    p.resize(n + 1);
    vector<bool> st(n + 1, false);
    for(int i = 0; i <= n; i ++) p[i] = i;

    for(int i = 1; i <= n / 2; i ++){
        cin >> b[i];
        int pb = find(b[i]), pa = find(b[i] - 1);
        p[pb] = pa;
    }
    bool ok = true;
    for(int i = n / 2; i >= 1; i --){
        if(st[b[i]]){
            ok = false;
            break;
        }
        ans[i * 2] = b[i];
        st[b[i]] = true;
        int t = find(b[i] - 1);
        if(t == 0)
        {
            ok = false;
            break;
        }
        else{
            ans[i * 2 - 1] = t;
            st[t] = true;
            p[t] = find(t - 1);
        }
    }
    if(ok){
        for(int i = 1; i <= n; i ++){
            cout << ans[i] << ' ';
        }
        cout << endl;
    }
    else puts("-1");
}
int main ()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;
int n;
int a[N];

struct node{
    int l, r;
    LL s;
}tr[N << 2];

void build(int u, int l, int r)
{
    if(l == r){
        tr[u] = {r, r, 0};
        return;
    }
    tr[u] = {l, r, 0};
    int mid = (l + r) / 2;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void pushup(int u){
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}
void update(int u, int x, int c){
    if(tr[u].l == tr[u].r){
        tr[u].s = c;
        return;
    }
    int mid = (tr[u].l + tr[u].r) / 2;
    if(x <= mid) update(u << 1, x, c);
    else update(u << 1 | 1, x, c);
    pushup(u);
}
int query(int u, LL mid, int fg){
    if(tr[u].s < mid) return fg == 0? 1e9: -1e9;
    if(tr[u].l == tr[u].r){
        if(fg == 0){
            if(tr[u].s == mid) return tr[u].r + 1;
            else return tr[u].r;
        }
        else{
            if(tr[u].s ==mid) return tr[u].r - 1;
            else return tr[u].r;
        }
    }
    if(fg == 0){
        if(mid <= tr[u << 1].s){
            return query(u << 1, mid, fg);
        }
        else{
            return query(u << 1 | 1, mid - tr[u << 1].s, fg);
        }
    }
    else{
        if(tr[u << 1 | 1].s >= mid){
            return query(u << 1 | 1, mid, fg);
        }
        else{
            return query(u << 1, mid - tr[u << 1 | 1].s, fg);
        }
    }
}
int main(){
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        update(1, i, a[i]);
    }
    int q;
    cin >> q;
    while(q --){
        int k, x, y;
        cin >> k >> x;
        if(k == 1){
            cin >> y;
            update(1, x, y);
        }
        else{
            LL l = 0, r = 1e14;
            while(l < r){
                LL mid =(l + r) / 2;
                if(query(1, mid, 1) - query(1, mid, 0) + 1 <= x) r = mid;
                else l = mid + 1;
            }
            cout << r << endl;
        }
    }
    return 0;
}

https://codeforces.com/problemset/problem/1693/B

输入 T(≤1e3) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5) 表示一棵 n 个节点的树，编号从 1 开始，1 为根节点。
然后输入 p[2],p[3],…,p[n]，其中 p[i] 表示 i 的父节点。
然后输入 n 行，其中第 i 行输入两个数 l 和 r，表示第 i 个节点值的目标范围 [l,r]。

初始时，所有节点值均为 0。
每次操作你可以选择一条从 1 开始的路径，把路径上的每个节点值都加上一个数。要求这些数按照路径的顺序，
形成一个递增序列。（可以相等，可以等于 0，例如 [0,0,1,3,3]）
要使所有节点值都在对应的范围内，至少要操作多少次？
输入
4
2
1
1 5
2 9
3
1 1
4 5
2 4
6 10
4
1 2 1
6 9
5 6
4 5
2 4
5
1 2 3 4
5 5
4 4
3 3
2 2
1 1
输出
1
2
2
5

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
int e[N], ne[N], h[N], idx;
LL s[N];
int dp[N];
int n;
PII v[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u){
    if(h[u] == -1){
        s[u] = v[u].second;
        dp[u] = 1;
        return dp[u];
    }
    LL s1 = 0;
    int s2 = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);
        s1 += s[j];
        s2 += dp[j];
    }
    if(s1 > v[u].second){
        s[u] = v[u].second;
        dp[u] = s2;
    }
    else if(s1 >= v[u].first && s1 <= v[u].second){
        s[u] = s1;
        dp[u] = s2;
    }
    else{
        s[u] = v[u].second;
        dp[u] = s2 + 1;
    }
    return dp[u];
}
void solve(){
    cin >> n;
    memset(h, -1, sizeof h);
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= n; i ++) s[i] = 0;

    idx = 0;
    for(int i = 2; i <= n; i ++){
        int x;
        cin >> x;
        add(x, i);
    }
    for(int i = 1; i <= n; i ++) cin >> v[i].first >> v[i].second;

    cout << dfs(1) << endl;
}
int main ()
{
    int T;
    cin >> T;
    while(T --){
        solve();        
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>

using namespace std;

const int N = 30010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N], q[N];
bitset<N> f[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if ( -- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b] ++ ;
    }

    topsort();

    for (int i = n - 1; i >= 0; i -- )
    {
        int j = q[i];
        f[j][j] = 1;
        for (int k = h[j]; ~k; k = ne[k])
            f[j] |= f[e[k]];
    }

    for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count());

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<int> d(n + 1, 0);
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        d[a] ++;
        g[b].push_back(a);
    }
    queue<int> q;
    vector<int> ans(n + 1, 0);
    for(int i = 1; i <= n; i ++)
    {
        if(d[i] == 0){
            q.push(i);
            ans[i] = 100;
        }
    }
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int j : g[t]){
            if(-- d[j] == 0){
                ans[j] = ans[t] + 1;
                q.push(j);
            }
        }
    }
    int res = 0;
    bool ok = true;
    for(int i = 1; i <= n; i ++){
        res += ans[i];
        if(!ans[i]) ok = false;
    }
    if(ok)  
        cout << res;
    else puts("Poor Xed");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n;
int d[N];

int main()
{
    cin >> n;
    vector<vector<int>> g(n + 1);

    for(int i = 1; i <= n; i ++)
    {
        int x;
        while(cin >> x, x != 0){
            d[x] ++;
            g[i].push_back(x);
        }
    }
    queue<int> q;
    for(int i = 1; i <= n; i ++) if(d[i] == 0) q.push(i);

    vector<int> ans;
    while(q.size())
    {
        int t = q.front();
        ans.push_back(t);
        q.pop();
        for(int y : g[t]){
            if(-- d[y] == 0){
                q.push(y);
            }
        }
    }
    for(auto &x : ans) cout << x << ' ';
    return 0;
}

https://codeforces.com/problemset/problem/883/I

输入 n k(1≤k≤n≤3e5) 和长为 n 的数组 a(1≤a[i]≤1e9)。

把这 n 个数重新排列，然后分成若干个组，要求每组至少有 k 个数。
定义 diff(b) 表示序列 b 中最大值与最小值的差。
计算所有组的 diff 值的最大值 mx。
输出 mx 的最小值。
输入
5 2
50 110 130 40 120
输出 20

输入
4 1
2 3 4 1
输出 0

#include <bits/stdc++.h>

using namespace std;

const int N = 300010;
int a[N];
int n, k;

bool check(int mid)
{
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for(int i = 1, j = 1; i <= n; i ++){
        while(j <= i && a[i] - a[j] > mid || dp[j - 1] == false) j ++;

        if(i - j + 1 >= k) dp[i] = true;
    }
    return dp[n] == true;
}
int main ()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    sort(a + 1, a + 1 + n);
    int l = 0, r = 1e9;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

https://codeforces.com/problemset/problem/1118/D2

输入 n(1≤n≤2e5) (1≤m≤1e9) 和长为 n 的数组 a(1≤a[i]≤1e9)。

把这 n 个数重新排列，然后分成 x 个组。
每个组的第一个数不变，第二个数减一，第三个数减二，依此类推。
如果有数字减成负数，则从组中去掉。

要使所有数字之和至少为 m，x 最小是多少？
如果无法做到，输出 -1。

输入
5 8
2 3 1 1 2
输出
4
输入
7 10
1 3 4 2 1 4 2
输出
2

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010;
int n, m;
int a[N];
LL s[N];

bool check(int mid){
    int c = 0;
    int i, j;
    for(i = 1, j = 1; i <= n; i ++){
        if(i - j + 1 > mid){
            j = i;
            c ++;
        }
        if(a[i] - c <= 0) break;
    }

    LL sum = s[i - 1] - 1ll * (c - 1) * c / 2 * mid - 1ll * c * (i - j);

    return sum >= m;
}
int main ()
{
    cin >> n >> m;
    LL res = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] >= 0)
            res += a[i];
    }
    if(res < m){
        puts("-1");
    }
    else{
        sort(a + 1, a + 1 + n, greater<>());
        for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

        int l = 1, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << r << endl;
    }
    return 0;
}