#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

const int N = 1010;
const double eps = 1e-6, inf = 1e10;

typedef std::pair<double, double> PDD;

int n, d;
PDD seg[N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    std::cin >> n >> d;
    bool ok = true;

    for(int i = 0;i < n;i ++)
    {
        double x, y;
        std::cin >> x >> y;

        if(y > d)
        {
            ok = false;
            break;
        }
        double r = sqrt(d * d - y * y);
        seg[i] = {x + r, x - r};
    }

    if(ok)
    {
        std::sort(seg, seg + n);
        int res = 0;
        double last = -inf;
        for(int i = 0;i < n;i ++)
        {
            if(seg[i].second > last + eps) 
            {
                res ++;
                last = seg[i].first;
            }
        }

        std::cout << res << '\n';
    }
    else puts("-1");

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11, M = 110;

int P;
int f[N][10][M];

int mod(int x, int y)
{
    return (x % y + y) % y;
}

void init()
{
    memset(f, 0, sizeof f);

    for (int i = 0; i <= 9; i ++ ) f[1][i][i % P] ++ ;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k < P; k ++ )
                for (int x = 0; x <= 9; x ++ )
                    f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}

int dp(int n)
{
    if (!n) return 1;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = 0; j < x; j ++ )
            res += f[i + 1][j][mod(-last, P)];

        last += x;

        if (!i && last % P == 0) res ++ ;
    }

    return res;
}

int main()
{
    int l, r;
    while (cin >> l >> r >> P)
    {
        init();

        cout << dp(r) - dp(l - 1) << endl;
    }

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
    for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = -2;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }

    // 特殊处理有前导零的数
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main()
{
    init();

    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}

超宝赛高

算法1

树状数组$O(nlogn)$

就一点，树状数组每个tr[x]存储的是tr[x - lowbit(x) + 1] - tr[x]之间的最大值！

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 100010;

int n, m;
int h[N], trmin[N], trmax[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for(int i = x;i <= n;i += lowbit(i))
    {
        trmin[i] = std::min(trmin[i], c);
        trmax[i] = std::max(trmax[i], c);
    }
}

int get_max(int l, int r)
{
    if(r > l)
    {
        if(r - lowbit(r) >= l) return std::max(trmax[r], get_max(l, r - lowbit(r)));
        else return std::max(h[r], get_max(l, r - 1));
    }

    return h[l];
}

int get_min(int l, int r)
{
    if(r > l)
    {
        if(r - lowbit(r) >= l) return std::min(trmin[r], get_min(l, r - lowbit(r)));
        else return std::min(h[r], get_min(l, r - 1));
    }

    return h[l];
}

void solve()
{
    scanf("%d%d", &n, &m);
    memset(trmin, 0x3f, sizeof trmin);
    for(int i = 1;i <= n;i ++) 
    {
        scanf("%d", h + i);
        add(i, h[i]);
    }

    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", get_max(a, b) - get_min(a, b));
        printf("max = %d\n", get_max(a, b));
    }
}

int main()  
{
    int t = 1;

    while(t --) solve();

    return 0;
}

算法2

(st表 / RMQ算法) $O(O(n)$

RMQ yyds

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using LL = long long;

const int N = 100010, M = 17;

int n, m;
int f[N][M], g[N][M];
int h[N];

void init()
{
    for(int j = 0;j < M;j ++)
        for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            if(!j) f[i][j] = h[i];
            else f[i][j] = std::max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

    for(int j = 0;j < M;j ++)
        for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            if(!j) g[i][j] = h[i];
            else g[i][j] = std::min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}

int query_max(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

int query_min(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return std::min(g[l][k], g[r - (1 << k) + 1][k]);
}

void solve()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++) scanf("%d", h + i);

    init();

    while(m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(l, r) - query_min(l, r));
    }
}

int main()
{
    int t = 1;

    while(t --) solve();

    return 0;
}

算法1

树状数组

时间复杂度 $O(nlogn)$

由ai + aj > bi + bj -> ai - bi > aj - bj, 相当于对于所有的i，存在多少j（i < j）满足ai - bi > aj - bj
满足树状数组求前缀和后对于每一个ai - bi有多少个aj - bj小于它。

蠢在两个地方:1.树状数组只存储了aj - bj的前缀和，所以不需要考虑ai - bi的影响
2.对于存储的树状数组，因为是排序去重后的结果，所以最坏的情况下，下标最大为2 * n，而不是n

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 400010;

int n, m;
int a[N], b[N], x[N], y[N], tr[N], res[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for(int i = x;i <= n * 2;i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i;i -= lowbit(i)) res += tr[i];

    return res;
}

void solve()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++) scanf("%d", a + i);
    for(int i = 1;i <= n;i ++) scanf("%d", b + i);

    for(int i = 1;i <= n;i ++)
    {
        x[i] = a[i] - b[i];
        y[i] = b[i] - a[i];
        res[++ m] = x[i], res[++ m] = y[i];
    }

    std::sort(res + 1, res + m + 1);
    m = std::unique(res + 1, res + m + 1) - res - 1;
    for(int i = 1;i <= n;i ++)
    {
        x[i] = std::lower_bound(res + 1, res + m + 1, x[i]) - res;
        y[i] = std::lower_bound(res + 1, res + m + 1, y[i]) - res;
        add(y[i], 1);
    }

    LL ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        add(y[i], -1);
        ans += sum(x[i] - 1);
    }

    printf("%lld\n", ans);
}

int main()
{
    int t = 1;
    //scanf("%d", &t);

    while(t --) solve();

    return 0;
}

let fs = require('fs');
let buf = '';

process.stdin.on('readable', function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
    buf.split('\n').forEach(function(line) {
        let tokens = line.split(' ').map(function(x) { return parseInt(x); });
        if (tokens.length != 2) return;
        console.log(tokens.reduce(function(a, b) { return a + b; }));
    });
});

深感人生之艰难,就像那不息之长河,虽有东去大海之志,却流程缓慢,征程多艰,然，江河水总有入海之时,而人生之志,却常常难以实现,令人抱恨终生。

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>

    <style>
        .container {
            width: 50%;
            height: 500px;
            background-color: lightblue;
            display: flex;
            margin: 10px;
        }

        .container>* {
            width: 120px;
            height: 120px;
        }

        .container>*:nth-child(odd) {
            background-color: lightsalmon;
        }

        .container>*:nth-child(even) {
            background-color: lightgreen;
        }

        .container:nth-child(1) {
            flex-wrap: wrap;
            justify-content: space-between;
            align-content: flex-start;
        }

        .container:nth-child(2) {
            flex-direction: row-reverse;
            flex-wrap: nowrap;
        }

        .container:nth-child(2)>*:nth-child(odd) {
            flex-grow: 3;
            flex-shrink: 3;
        }

        .container:nth-child(2)>*:nth-child(even) {
            flex-grow: 1;
            flex-shrink: 1;
        }
    </style>
</head>

<body>
    <div class="container">
        <div>1</div>
        <div>2</div>
        <div>3</div>
        <div>4</div>
        <div>5</div>
        <div>6</div>
    </div>

    <div class="container">
        <div>1</div>
        <div>2</div>
        <div>3</div>
        <div>4</div>
        <div>5</div>
        <div>6</div>
    </div>
</body>

</html>

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>

    <style>
        .container {
            height: 500px;
            width: 500px;
            background-color: lightblue;
        }

        .item {
            height: 100px;
            width: 100px;
            margin: 10px;
            background-color: lightcoral;
            float: left;
        }

        .next-line {
            width: 150px;
            height: 150px;
            background-color: rgba(0, 0, 255, 0.5);
            clear: both;
        }
    </style>
</head>

<body>
    <div class="container">
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="next-line"></div>
    </div>
</body>

</html>