cf EC 172 C（0-＞-1 的转化+区间和使用前缀和表示，化简式子）+ D（二维的信息，先对一维排序，另一维看情况分析）

这道题和C 题一模一样。
添加链接描述

真是真是菜吧。这道题做的时候还能想到前缀和，下面那一道题赛时完全没想法。
因为有一个区间的和，所以比较自然的能想到区间和。
但是区间和化简之后的式子，不可行。
换成后缀之后，就十分可以求解了。
很神奇。

后来想了一下，下一道题没做出来。完全没有往前缀和的方向去思考。

添加链接描述
C题意：
有一个n 长度的01 串。1 是B的得分点，0是A的得分点
要求B的得分大于A的得分至少K 分。
问最少划分多少区间（区间的权值依次为 0 1 2 …m-1）（每个区间至少一个元素。）或者无法做到输出-1.
对于一个区间B和A得分的差是 （cnt1-cnt0）*权值
我们可以将0->-1 ，这样 cnt1-cnt0 的大小，可以直接用加法来代替。这个处理很常见。
这样区间的和，就可以尝试用前缀和来表示。
通过化简可以退出来我划分m的数组
那么B和A的差值是 (m-1)*sum-(m-1 个前缀)。
我们这个前缀当然选择最小的使用。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
void solve()
{
    int n, k;
    cin >> n >> k;
    string ss;
    cin >> ss;
    vector<int> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = ss[i - 1] - '0';
        if (a[i] == 0)
            a[i] = -1;
        sum += a[i];
        a[i] += a[i - 1];
    }

    sort(a.begin() + 1, a.end());

    vector<int> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        s[i] += s[i - 1];
        s[i] += a[i];
    }

    // 枚举划分的组数
    for (int i = 1; i <= n; i++)
    {
        int t = (i - 1) * sum - s[i - 1];
        if (t >= k)
        {
            cout << i << "\n";
            return;
        }
    }
    cout << -1 << "\n";
}
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D题意：
就是说 n个区间，区间端点 1-1e9。每个区间的值定义为 包含我这个区间的其他所有区间都具有的额外的长度。问每个区间的值
本质上是 询问 我每一区间 合法区间中的 最近的左端点和右端点。
思路：
对于二维的信息。一般的思路都有对某一维排序，之后的做法就得依据题目来分析。

我先按照左端点(升序)排序，将所有的右端点塞进set里面。这样我这个区间所有可能的合法区间的右端点都在这个set里面。我找到比我这个区间右端点大的第一个点就行。就是我合法区间里的最近的右端点。
然后再按照右端点（倒序）排序。将所有的左端点放进set里。找到比我小的第一个数

这道题 还有一个细节，就是sort 的时候，当我左/右端点相同的时候，怎么排序。
回到排序的实质，当我到了i 这个区间，我要遍历了所有可能是我i 这个区间合法的区间。
所以当按照左端点来排序的时候，当左端点相同的时候，我们右端点大的要在前面。
同理右端点排序的时候。
还有一个问题，就是当我出现两个一样的区间的时候，我这些区间的ans 都是0.
这个要额外处理一下。（因为按照我们的排序，第一次出现的那个区间不会变成0）

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

struct node
{
    int l = 0, r = 0;
    int index = 0;
};
bool cmp1(node &a, node &b)
{
    if (a.l != b.l)
        return a.l < b.l;
    else
        return a.r > b.r;
}
bool cmp2(node &a, node &b)
{
    if (a.r != b.r)
        return a.r > b.r;
    else
        return a.l < b.l;
}
void solve()
{
    int n;
    cin >> n;
    set<PII> vis;
    vector<node> a(n);
    vector<int> ans(n);
    map<PII, int> mp; // 记录下标
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].l >> a[i].r;
        if (vis.find({a[i].l, a[i].r}) == vis.end())
        {
            vis.insert({a[i].l, a[i].r});
            mp[{a[i].l, a[i].r}] = i;
        }
        else
        {
            ans[mp[{a[i].l, a[i].r}]] = -1e18;
            ans[i] = -1e18;
        }
        a[i].index = i;
    }

    // 左端点排序
    sort(a.begin(), a.end(), cmp1);
    set<int> se;
    for (int i = 0; i < n; i++)
    {
        int tar = a[i].r;
        auto it = se.lower_bound(tar);
        if (it != se.end())
        {
            ans[a[i].index] += *it - a[i].r;
        }
        se.insert(a[i].r);
    }
    set<int> se1;
    // 右端点排序
    sort(a.begin(), a.end(), cmp2);
    for (int i = 0; i < n; i++)
    {
        int tar = a[i].l;
        auto it = se1.upper_bound(tar);
        if (it == se1.begin())
        {
            se1.insert(a[i].l);
            continue;
        }
        it = prev(it);
        ans[a[i].index] += a[i].l - *it;
        se1.insert(a[i].l);
    }

    for (int i = 0; i < n; i++)
    {
        if (ans[i] < 0)
            cout << 0 << "\n";
        else
            cout << ans[i] << "\n";
    }
}
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}