/*
有点像扫描线
思路：从左到右枚举每个点，枚举到点i时，把所有以i为起点的区间的影响删去
再加上以i-1为结尾的区间的影响
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int n,m,a[maxn];
struct Inv{
int l,r;}p[
400];
int lazy[maxn<<
2],Min[maxn<<
2];
inline void pushup(
int rt){
Min[rt]=min(Min[rt<<
1],Min[rt<<
1|
1]);
}
inline void pushdown(
int rt){
if(lazy[rt]){
lazy[rt<<
1]+=lazy[rt];lazy[rt<<
1|
1]+=
lazy[rt];
Min[rt<<
1]+=lazy[rt];Min[rt<<
1|
1]+=
lazy[rt];
lazy[rt]=
0;
}
}
void build(
int l,
int r,
int rt){
lazy[rt]=
0;
if(l==r){Min[rt]=a[l];
return;}
int m=l+r>>
1;
build(lson);
build(rson);
pushup(rt);
}
void update(
int L,
int R,
int l,
int r,
int rt,
int val){
if(L<=l && R>=
r){
Min[rt]+=val,lazy[rt]+=val;
return;
}
pushdown(rt);
int m=l+r>>
1;
if(L<=
m)update(L,R,lson,val);
if(R>
m)update(L,R,rson,val);
pushup(rt);
}
int query(
int L,
int R,
int l,
int r,
int rt){
if(L<=l&&R>=r){
return Min[rt];}
pushdown(rt);
int m=l+r>>
1,res=
99999999;
if(L<=m)res=
min(res,query(L,R,lson));
if(R>m)res=
min(res,query(L,R,rson));
pushup(rt);
return res;
}
vector<
int>ans[
100005];
int main(){
cin>>n>>
m;
for(
int i=
1;i<=n;i++)scanf(
"%d",&
a[i]);
for(
int i=
1;i<=m;i++)scanf(
"%d%d",&p[i].l,&
p[i].r);
int Max=-
1,index=
0;
build(1,n,
1);
for(
int i=
1;i<=n;i++
){
for(
int j=
1;j<=m;j++
){
if(p[j].l<=i&&p[j].r>=i){
//该区间和当前坐标有关
if(i!=
1 && !(p[j].l<=i-
1&&p[j].r>=i-
1))
//和左边结点无关
update(p[j].l,p[j].r,
1,n,
1,
1);
//加上这段的值
continue;
}
ans[i].push_back(j);
//算上之前没算上的区间
if(i==
1 || p[j].l<=i-
1&&p[j].r>=i-
1)
update(p[j].l,p[j].r,1,n,
1,-
1);
}
int tmp=query(
1,n,
1,n,
1);
if(a[i]-tmp>Max){index=i;Max=a[i]-
tmp;}
}
cout << Max <<
endl;
cout << ans[index].size()<<
endl;
for(
int i=
0;i<ans[index].size();i++
)
cout << ans[index][i]<<
" ";
}
转载于:https://www.cnblogs.com/zsben991126/p/10313849.html
