题意：给你一个长度为n的序列和m组区间操作，每组区间操作可以把区间[l, r]中的数字都-1，请选择一些操作（可以都不选），使得序列的最大值和最小值的差值尽量的大。
思路：容易发现如果最大值和最小值都在某个操作区间里，那么这个操作没有意义，因为差值没变，所以我们可以想到暴力枚举每一个位置，假设这个位置的数是最小的，那么就把所有与他相关的区间操作都执行，执行完后找到当前序列的最大值更新答案即可。
E1数据很小,直接3重循环暴力枚举就可以过了，复杂度为O(n * n * m)。
对于E2，很明显如果每次操作完了从头到尾循环一遍找最大值很费时间，看标题也能想到最大值要用线段树来维护（2333），但是就算用线段树找最大值，复杂度还是O(n * m * logn)。
我们可以直观感受一下，对于每个枚举的位置，每次都暴力的把可以的区间操作加上，再暴力的还原这些操作，非常的浪费，所有我们可以从这里优化。
假设一个操作区间为[l, r],那么实际这个区间操作可以使[l, r]区间之中的值变得更小，在这个范围之外，这个操作是多余的。所以我们可以用差分的思想，我们记录一下这个区间对答案影响的开始位置和结束位置，扫描到区间开始时在线段树中加上该区间的影响，到区间末尾时消去该区间的影响。
因为每个操作只会添加和消去一次， 总复杂度为O(n * logn + m * logn), 其中的n * logn 是线段树的建树时间。
代码：
#include <bits/stdc++.h>
#define ls(x) (x << 1)
#define rs(x) ((x << 1) | 1)
#define pii pair<int, int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 100010;
int a[maxn];
struct node{
int mx, add;
int l, r;
};
vector<int> st[maxn], ed[maxn];
node tr[maxn * 4];
pii b[310];
vector<int> res;
void pushdown(int o) {
if(tr[o].add != 0) {
tr[ls(o)].add += tr[o].add;
tr[rs(o)].add += tr[o].add;
tr[ls(o)].mx += tr[o].add;
tr[rs(o)].mx += tr[o].add;
tr[o].add = 0;
}
}
void maintain(int o) {
tr[o].mx = max(tr[ls(o)].mx,tr[rs(o)].mx);
}
void build(int o, int l, int r) {
if(l == r) {
tr[o].mx = a[l];
tr[o].add = 0;
tr[o].l = l;
tr[o].r = r;
return;
}
tr[o].l = l;
tr[o].r = r;
int mid = (l + r) >> 1;
build(ls(o), l, mid);
build(rs(o), mid + 1, r);
maintain(o);
}
void update(int o, int l, int r, int ql, int qr, int add) {
if(l >= ql && r <= qr) {
tr[o].mx += add;
tr[o].add += add;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if(mid >= ql) update(ls(o), l, mid, ql, qr, add);
if(mid < qr) update(rs(o), mid + 1, r, ql, qr, add);
maintain(o);
}
int query(int o, int l, int r, int ql ,int qr) {
if(l >= ql && r <= qr) {
return tr[o].mx;
}
int ans = -INF;
pushdown(o);
int mid = (l + r) >> 1;
if(ql <= mid) ans = max(ans, query(ls(o), l, mid, ql, qr));
if(qr > mid) ans = max(ans, query(rs(o), mid + 1, r, ql, qr));
return ans;
}
int main() {
int n, m, ans = 0;
int mx = - INF, mi = INF;
// freopen("in.txt","r",stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
mi = min(mi, a[i]);
}
ans = mx - mi;
build(1, 1, n);
for(int i = 1; i <= m; i++) {
scanf("%d%d",&b[i].first, &b[i].second);
st[b[i].first].push_back(b[i].second);
ed[b[i].second].push_back(b[i].first);
}
int pos = 0, tmp;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < st[i].size(); j++) {
update(1, 1, n, i, st[i][j], -1);
}
tmp = query(1, 1, n, 1, n) - query(1, 1, n, i, i);
if(tmp > ans) {
ans = tmp;
pos = i;
}
for(int j = 0; j < ed[i].size(); j++) {
update(1, 1, n, ed[i][j], i, 1);
}
}
printf("%d
", ans);
for(int i = 1; i <= m; i++) {
if(b[i].first <= pos && b[i].second >= pos)
res.push_back(i);
}
printf("%d
",res.size());
for(int i = 0; i < res.size(); i++)
printf("%d ",res[i]);
}