cf1108E2 线段树类似扫描线

/*

有点像扫描线

思路：从左到右枚举每个点，枚举到点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[];

int lazy[maxn<<],Min[maxn<<];

inline void pushup(int rt){

    Min[rt]=min(Min[rt<<],Min[rt<<|]);

}

inline void pushdown(int rt){

    if(lazy[rt]){

        lazy[rt<<]+=lazy[rt];lazy[rt<<|]+=lazy[rt];

        Min[rt<<]+=lazy[rt];Min[rt<<|]+=lazy[rt];

        lazy[rt]=;

    }

}

void build(int l,int r,int rt){

    lazy[rt]=;

    if(l==r){Min[rt]=a[l];return;}

    int m=l+r>>;

    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>>;

    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>>,res=;

    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[];

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=m;i++)scanf("%d%d",&p[i].l,&p[i].r);

    int Max=-,index=;

    build(,n,);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(p[j].l<=i&&p[j].r>=i){//该区间和当前坐标有关

                if(i!= && !(p[j].l<=i-&&p[j].r>=i-))//和左边结点无关

                    update(p[j].l,p[j].r,,n,,);//加上这段的值

                continue;

            }

            ans[i].push_back(j);

            //算上之前没算上的区间

            if(i== || p[j].l<=i-&&p[j].r>=i-)

                update(p[j].l,p[j].r,,n,,-);

        }

        int tmp=query(,n,,n,);

        if(a[i]-tmp>Max){index=i;Max=a[i]-tmp;}

    }

    cout << Max << endl;

    cout << ans[index].size()<<endl;

    for(int i=;i<ans[index].size();i++)

        cout << ans[index][i]<< " ";

}