你知道打完看题解发现自己乱搞解法是正解但是没有打下去是什么感觉吗

总之是道乱搞题

由于原题我根本没见过于是我直接开始乱搞

首先观察样例
第一组样例提示我们可以先找出有交区间内的答案再合并
先考虑两个区间的情况
由于 $ans \leq \Sigma^{i=1}_{n} A_i$,我们尝试构造答案。

有交区间

对于两个有交但不并的区间$A,B$，我们发现可以先满足$A$区间使答案最小并且显然没有比这更优的解

包含区间

假设$A \sub B$，满足$A$区间的答案让我们拿到了更高点。同时我们注意到若满足$A$后立刻满足$B$会导致重复计算。于是我们在满足$A$后优先满足更上方的区间，对于被包含的区间，由于最后我们处于一个最高点，我们可以在满足其他区间后单独考虑。

无交区间

由于向上是有代价的，我们优先满足靠上的区间

基于以上法则我们可以写出一个神秘sort的cmp函数 WA 0.jpg

合并

实际上，这种做法有一个比较显然的问题。是这个算法会从最顶的一个区间开始，从而使中间的区间重复计算。我们可以先从初始点往后找，将初始点到顶端的所有区间交按顺序完成。

代码在学校等我信息课改完再放

以上操作要求我们先找出所有有交区间，再在区间内进行排序输出，还是过于麻烦了。有没有更加简单而且时间复杂度同样优秀的做法呢？有的兄弟，有的。由于向下是没有代价的，我们可以在拿到高点后优先往后找重复计算，最后再从后往前找，可以证明后者操作$ans = \Sigma^{i=1}_{n} A_i$。

那么这时候就有人要问了欸你这么做就一点问题没有吗？有的兄弟，有的。

由于是从最低点开始往后枚举，如果初始层$f$恰好不在任意区间内且有比$f$更高层数的区间，那么$[f,l]$这一区间就被重复计算了。解决就如我第一种做法，我们初始时从$f$往上枚举。第一个区间我们可以枚举或二分。当然直接往后找也是没问题的。

这也是题解做法，贴份代码在这

#include <bits/stdc++.h>
#define inf INT_MAX
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define NN INT_MIN
typedef long long ll;
const ll mod = 998244353;
using namespace std;
int T;
struct node
{
    ll l, r, pos;
} a[200005];
bool cmp(node x, node y)
{
    return x.l < y.l;
}
bool cmp1(node x, node y)
{
    return x.r < y.r;
}
ll ans;
bool vis[200005];
int main()
{
#ifdef WHX_AK_IOI
    freopen("data.in", "r", stdin);
// freopen("dataout.txt","w",stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        memset(vis, 0, sizeof vis);
        ll n, f;
        ans = 0;
        cin >> n >> f;
        vector<int> tans;
        for (int i = 1; i <= n; i++)
            cin >> a[i].l >> a[i].r, ans += a[i].r - a[i].l, a[i].pos = i;
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            if (f <= a[i].r)
                ans += max(0ll, a[i].l - f), tans.push_back(a[i].pos), vis[a[i].pos] = 1, f = a[i].r;
        sort(a + 1, a + n + 1, cmp1);
        for (int i = n; i >= 1; i--)
            if (!vis[a[i].pos])
                tans.push_back(a[i].pos);
        cout << ans << endl;
        for (auto &&i : tans)
            cout << i << ' ';
        cout << endl;
    }
    // system("pause");
    return 0;
}