codeforces Array and Segments (easy & hard version)

easy version传送门
遇到很多不确定量的时候我们不妨设一个量为已知量。
分区间只有三种情况：
1.包括最小值，最大值
2.包括最小值
3.包括最大值
我们假设一个值为最大值，显然第一种情况无所谓取与不取，第二种情况一定要取，第三种情况一定不取。所以我们遍历一下数组，设每个值为最大值，再结合差分的应用，就可以在o(n2)的时间复杂度内完成这道题。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pii pair<int,int>
#define r0 return 0
const int N = 2e5 + 5;
int a[400];
int b[400];
 vector<pii>v;
 vector<int>tmp;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int maxx = 0;
    int minn = 0x3f3f3f3f;
    int ans = 0;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        v.push_back({ l,r }); 
    }
    for (int i = 1; i <= n; i++)
    {
        minn = 0x3f3f3f3f;
        for (int j = 1; j <= n; j++)
        {
            b[j] = a[j] - a[j-1];// 构造差分数组
        }
        maxx = a[i];
        vector<int>save;// 记录每次操作的区间

        for (int j = 0; j < v.size(); j++)
        {
            int l = v[j].first, r = v[j].second;
            if (i<l || i>r)
            {
                save.push_back(j+1);
                b[l] -= 1;
                b[r + 1] += 1;
            }
        }
        for (int j = 1; j <= n; j++)
            b[j] += b[j - 1];
        for (int j = 1; j <= n; j++)
        {
            if (j != i) minn = min(minn, b[j]);
        }
        if (maxx - minn > ans) tmp = save,ans = maxx- minn;
    }
    cout << ans << endl;
    cout << tmp.size()<<endl;
    for (auto& i : tmp)
        cout << i << ' ';
    return 0;
}

hard version传送门

这题不会啊，参考了https://blog.csdn.net/qq_46030630/article/details/109412212
这里我们找每次的最小值，最小值要不就不在所给区间中，要不就在所给区间中，我们先记录下第一种情况的值然后去找第二种情况的答案。我们可以把区间都分成一段一段，然后用第一个值来代替整个区间。假设最小值就在这个区间中。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define pii pair<int,int>
#define r0 return 0;
const int N = 2e5 + 5;
int a[N];
int b[N];
 vector<pii>v;
 vector<int>tmp;
 set<int>st;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        v.push_back({ l,r });
        st.insert(l);
        if(r+1<n)st.insert(r + 1);
    }
    int maxx = *max_element(a + 1, a + 1 + n);
    int minn = *min_element(a + 1, a + 1 + n);
    int ans = maxx - minn;
    for (auto& i : st)
    {
        vector<int> t;
        maxx = -1e9; // 记得要设成负值，0的话是不行的
        minn = 1e9;
        for (int j = 1; j <= n; j++) b[j] = a[j] - a[j - 1];
        for(int j = 0;j<v.size();j++)
        {
            int l = v[j].first, r = v[j].second;
            if (i >= l && i <= r) b[l] -= 1, b[r + 1] += 1, t.push_back(j+1);
        }
        for (int j = 1; j <= n; j++)
        {
            b[j] += b[j - 1];
            maxx = max(maxx, b[j]),minn = min(minn,b[j]);
        }
        if (ans < maxx - minn) tmp = t, ans = maxx - minn;
    }
    cout << ans << endl;
    cout << tmp.size() << endl;
    for (auto& i : tmp) cout << i << ' ';
    r0; 
}