题目大意：
给定n m (1≤n≤1e5,0≤m≤300)
给定序列的n个数
给定m个区间
选择一个区间操作 会对整个区间-1
要求选择任意个（可以为0个）区间操作后
最大化整个序列的最大值与最小值的差
easy version的范围是(1≤n≤300,0≤m≤300)，
可以直接O(n*n)暴力枚举最大值位置和最小值位置
再O(m)查找只对最小值位置修改的区间个数 更新差值
总的O(n*n*m) 还是可以过的
但是hard version的范围是(1≤n≤1e5,0≤m≤300)
m的范围还是300 应该考虑从m入手解题
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long using namespace std; const int N=1e5+5; int n, m; int a[N], l[305], r[305]; vector <int> add[N], sub[N]; int ansc[305]; void change(int l,int r,int v) { for(int i=l;i<=r;i++) a[i]+=v; } int main() { while(~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]+1].push_back(i); } int maxi,mini; maxi=mini=a[1]; for(int i=2;i<=n;i++) maxi=max(maxi,a[i]), mini=min(mini,a[i]); int ans=maxi-mini, id; /// 这个方法能得到所有区间执行方案的结果 // 对每个位置 执行所有覆盖该位置的区间的操作 // 而不覆盖该位置的区间不执行 减小影响 for(int i=1;i<=n;i++) { for(int j=0;j<add[i].size();j++) { int ind=add[i][j]; change(l[ind],r[ind],1); } // 消除(不覆盖该位置的)区间的影响 for(int j=0;j<sub[i].size();j++) { int ind=sub[i][j]; change(l[ind],r[ind],-1); } // 执行(此处开始覆盖该位置的)区间的操作 // 该位置位于中间的那些区间之前已经操作过 if(!sub[i].empty() or !add[i].empty()) { maxi=mini=a[1]; for(int i=2;i<=n;i++) maxi=max(maxi,a[i]), mini=min(mini,a[i]); if(ans<maxi-mini) ans=maxi-mini, id=i; } } printf("%d ",ans); int c=0; for(int i=1;i<=m;i++) if(l[i]<=id && id<=r[i]) ansc[c++]=i; printf("%d ",c); for(int i=0;i<c;i++) printf("%d ",ansc[i]); printf(" "); } return 0; }