题意
给定一个长度为n的序列，和m个区间。
对一个区间的操作是：对整个区间的数-1
可以选择任意个区间（可以为0个、每个区间最多被选择一次）进行操作后，要求最大化的序列极差（极差即最大值 - 最小值）。
easy version的范围是(1≤n≤300,0≤m≤300)
hard version的范围是(1≤n≤1e5,0≤m≤300)
分析： 我们可以通过枚举最大或者最小值出现的位置 ， 然后把不包括最大值位置或者包括最小值位置的区间选取 ， 如果数据小我们是可以通过暴力的 ， 但是这里的n有1e5 , 那我们就需要借助数据结构了 ， 我们很容易可以看出是线段树的区间修改与区间最值 ， 但是有个问题 ， 我们枚举的过程中选区出来的区间还要进行回复 ， 所有这里有个很精妙的东西：
我们可以对操作区间进行整理，使得在枚举过程中，不需要重复进行区间操作。
比如我们现在枚举的最小值位置是p，则我们需要选择包含了p的所有区间。
那么p前面一个状态p-1，进行的区间操作是包含了p-1的所有区间，这些p-1区间中，有些是包含了p的，有些是没包含p的，那么我们需要先删除掉没包含p的区间的影响（即把这些区间减掉的1给加回来）。同时还需要补上包含了p但是不包含p-1的区间（这样选择，就不会和p-1里面保留了的区间重复）。
包含了p-1，但不包含p的区间，显然是以p-1结尾的区间。我们用add[]数组保存以r[i]结尾的区间的编号。
包含了p，但不包含p-1的区间，显然是以p开始的区间。我们用sub[]数组保存以l[i]开始的区间的编号。
区间修改操作，就要用到线段树了。
最后输出答案时，使用最终确定的最小值的位置P，包含P的区间留下，不包含P的舍弃。
---------------------
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 305;
int n, m;
int a[maxn], l[maxm], r[maxm], ans[maxn];
vector<int> add[maxn], sub[maxn];
struct node
{
int l, r;
int maxx, minn, lazy;
} tree[maxn << 2];
void push_up(int k)
{
tree[k].maxx = max(tree[k << 1].maxx, tree[k << 1 | 1].maxx);
tree[k].minn = min(tree[k << 1].minn, tree[k << 1 | 1].minn);
}
void push_down(int k)
{
if(tree[k].l != tree[k].r)
{
tree[k << 1].maxx += tree[k].lazy, tree[k << 1].minn += tree[k].lazy;
tree[k << 1 | 1].maxx += tree[k].lazy, tree[k << 1 | 1].minn += tree[k].lazy;
tree[k << 1].lazy += tree[k].lazy;
tree[k << 1 | 1].lazy += tree[k].lazy;
}
tree[k].lazy = 0;
}
void build(int k, int l, int r)
{
tree[k].l = l;
tree[k].r = r;
if(l == r)
{
tree[k].maxx = a[l];
tree[k].minn = a[l];
tree[k].lazy = 0;
return ;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
push_up(k);
}
void update(int k, int l, int r, int x)
{
if(tree[k].lazy)
push_down(k);
tree[k].maxx += x;
tree[k].minn += x;
if(tree[k].l == l && tree[k].r == r)
{
tree[k].lazy += x;
return ;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if(r <= mid)
update(k << 1, l, r, x);
else if(l > mid)
update(k << 1 | 1, l, r, x);
else
{
update(k << 1, l, mid, x);
update(k << 1 | 1, mid + 1, r, x);
}
push_up(k);
}
int query_max(int k, int l, int r)
{
int maxx;
if(tree[k].lazy)
push_down(k);
if(tree[k].l == l && tree[k].r == r)
return tree[k].maxx;
int mid = (tree[k].l + tree[k].r) >> 1;
if(r <= mid)
maxx = query_max(k << 1, l, r);
else if(l > mid)
maxx = query_max(k << 1 | 1, l, r);
else
maxx = max(query_max(k << 1, l, mid), query_max(k << 1 | 1, mid + 1, r));
return maxx;
}
int query_min(int k, int l, int r)
{
int minn;
if(tree[k].lazy)
push_down(k);
if(tree[k].l == l && tree[k].r == r)
return tree[k].minn;
int mid = (tree[k].l + tree[k].r) >> 1;
if(r <= mid)
minn = query_min(k << 1, l, r);
else if(l > mid)
minn = query_min(k << 1 | 1, l, r);
else
minn = min(query_min(k << 1, l, mid), query_min(k << 1 | 1, mid + 1, r));
return minn;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &l[i], &r[i]);
//统计区间
sub[ l[i] ].push_back(i);
add[ r[i] ].push_back(i);
}
//构造线段树
build(1, 1, n);
int d = -1, p;//d记录最大极差,p记录最小值的位置
for(int i = 1; i <= n; i++)//枚举最小值出现的位置
{
for(int j = 0; j < add[i - 1].size(); j++)//消除包含i-1,不包含i区间的影响
{
int id = add[i - 1][j];//注意这里是i-1
update(1, l[id], r[id], 1);
}
for(int j = 0; j < sub[i].size(); j++)//添加包含i,不包含i-1区间的影响
{
int id = sub[i][j];
update(1, l[id], r[id], -1);
}
//查询极差 注意这里虽然知道最小值是a[i],但是由于使用了线段树,有lazy标记,标记可能没有更新到最底层,所以不能直接使用a[i]。
int det = query_max(1, 1, n) - query_min(1, 1, n);
if(det > d)
{
d = det;
p = i;
}
}
printf("%d
", d);
int t = 0;
for(int i = 1; i <= m; i++)//统计区间
{
if(l[i] <= p && p <= r[i])
ans[t++] = i;
}
printf("%d
", t);
for(int i = 0; i < t; i++)
{
if(i != 0)
printf(" ");
printf("%d", ans[i]);
}
printf("
");
return 0;
}
参考与原文：https://blog.csdn.net/Floraqiu/article/details/86632558