E2. Array and Segments (Hard version)
题目链接：https://codeforces.com/problemset/problem/1108/E2
解题思路：线段树
blog：https://blog.csdn.net/Floraqiu/article/details/86632558
代码
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; const int maxm=300; int n,m; int a[maxn],l[maxm],r[maxm],ans[maxn]; vector<int>add[maxn],sub[maxn]; struct node { int l,r,lazy; int maxx;int minn; } 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[r]; 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() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>l[i]>>r[i]; sub[l[i]].push_back(i); add[r[i]].push_back(i); } build(1,1,n); int d=-0x3f3f3f,p; for(int i=1;i<=n;i++) { for(int j=0;j<add[i-1].size();j++) { int id=add[i-1][j]; update(1,l[id],r[id],1); } for(int j=0;j<sub[i].size();j++) { int id=sub[i][j]; update(1,l[id],r[id],-1); } int det = query_max(1, 1, n) - query_min(1, 1, n); if(det>d) { d=det; p=i; } } cout<<d<<endl; int cnt=0; for(int i=1; i<=m; i++)//统计区间 { if(l[i]<=p&&p<=r[i]) ans[cnt++] = i; } cout<<cnt<<endl; for(int i=0;i<cnt;i++) { if(i!=0) cout<<" "; cout<<ans[i]; } cout<<endl; return 0; }