题意
给定一个长度为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 + ;
const int maxm = ; 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 << ]; void push_up(int k)
{
tree[k].maxx = max(tree[k << ].maxx, tree[k << | ].maxx);
tree[k].minn = min(tree[k << ].minn, tree[k << | ].minn);
} void push_down(int k)
{
if(tree[k].l != tree[k].r)
{
tree[k << ].maxx += tree[k].lazy, tree[k << ].minn += tree[k].lazy;
tree[k << | ].maxx += tree[k].lazy, tree[k << | ].minn += tree[k].lazy;
tree[k << ].lazy += tree[k].lazy;
tree[k << | ].lazy += tree[k].lazy;
}
tree[k].lazy = ;
} 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 = ;
return ;
}
int mid = (l + r) >> ;
build(k << , l, mid);
build(k << | , mid + , 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) >> ;
if(r <= mid)
update(k << , l, r, x);
else if(l > mid)
update(k << | , l, r, x);
else
{
update(k << , l, mid, x);
update(k << | , mid + , 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) >> ;
if(r <= mid)
maxx = query_max(k << , l, r);
else if(l > mid)
maxx = query_max(k << | , l, r);
else
maxx = max(query_max(k << , l, mid), query_max(k << | , mid + , 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) >> ;
if(r <= mid)
minn = query_min(k << , l, r);
else if(l > mid)
minn = query_min(k << | , l, r);
else
minn = min(query_min(k << , l, mid), query_min(k << | , mid + , r));
return minn;
} int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
scanf("%d", &a[i]); for(int i = ; i <= m; i++)
{
scanf("%d%d", &l[i], &r[i]); //统计区间
sub[ l[i] ].push_back(i);
add[ r[i] ].push_back(i);
} //构造线段树
build(, , n); int d = -, p;//d记录最大极差,p记录最小值的位置
for(int i = ; i <= n; i++)//枚举最小值出现的位置
{
for(int j = ; j < add[i - ].size(); j++)//消除包含i-1,不包含i区间的影响
{
int id = add[i - ][j];//注意这里是i-1
update(, l[id], r[id], );
} for(int j = ; j < sub[i].size(); j++)//添加包含i,不包含i-1区间的影响
{
int id = sub[i][j];
update(, l[id], r[id], -);
} //查询极差 注意这里虽然知道最小值是a[i],但是由于使用了线段树,有lazy标记,标记可能没有更新到最底层,所以不能直接使用a[i]。
int det = query_max(, , n) - query_min(, , n);
if(det > d)
{
d = det;
p = i;
}
} printf("%d\n", d);
int t = ;
for(int i = ; i <= m; i++)//统计区间
{
if(l[i] <= p && p <= r[i])
ans[t++] = i;
}
printf("%d\n", t);
for(int i = ; i < t; i++)
{
if(i != )
printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return ;
}
参考与原文：https://blog.csdn.net/Floraqiu/article/details/86632558