1108E2 Array and Segments (Hard version) & 1108E1 Array and Segments (Easy version) 线段树 最小值与最大值

E2. Array and Segments (Hard version)

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The only difference between easy and hard versions is a number of elements in the array.

You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.

You are also given a set of mm segments. The jj-th segment is [lj;rj][lj;rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1;3][1;3] and [2;4][2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0]b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aa and obtain the array bb then the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers nn and mm (1≤n≤105,0≤m≤3001≤n≤105,0≤m≤300) — the length of the array aa and the number of segments, respectively.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−106≤ai≤106−106≤ai≤106), where aiai is the value of the ii-th element of the array aa.

The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.

Output

In the first line of the output print one integer dd — the maximum possible value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.

In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.

In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi of the obtained array bb is maximum possible.

If there are multiple answers, you can print any.

Examples

input

Copy

5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3

output

Copy

6
2
4 1 

input

Copy

5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5

output

Copy

7
2
3 2 

input

Copy

1 0
1000000

output

Copy

0
0

Note

In the first example the obtained array bb will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.

In the second example the obtained array bb will be [2,−3,1,−1,4][2,−3,1,−1,4] so the answer is 77.

In the third example you cannot do anything so the answer is 00.

题意
给定一个长度为n的序列，和m个区间。
对一个区间的操作是：对整个区间的数-1
可以选择任意个区间（可以为0个、每个区间最多被选择一次）进行操作后，要求最大化的序列极差（极差即最大值 - 最小值）。
easy version的范围是(1≤n≤300,0≤m≤300)
hard version的范围是(1≤n≤1e5,0≤m≤300)

第一个简单的可以使用暴力解决

#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\n",ans);
        int c=0;
        for(int i=1;i<=m;i++)
            if(l[i]<=id && id<=r[i]) ansc[c++]=i;
        printf("%d\n",c);
        for(int i=0;i<c;i++) printf("%d ",ansc[i]);
       printf("\n");;
    }

    return 0;
}

第二个暴力会超时  可以使用线段树来解决区间最大值与最小值的问题

 

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 305;

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 << 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[l];
        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()
{
    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] ].push_back(i);
    }

    //构造线段树
    build(1, 1, n);

    int d = -1, p;//d记录最大极差,p记录最小值的位置
    for(int i = 1; i <= n; i++)//枚举最小值出现的位置
    {
        for(int j = 0; j < add[i - 1].size(); j++)//消除包含i-1,不包含i区间的影响
        {
            int id = add[i - 1][j];//注意这里是i-1
            update(1, l[id], r[id], 1);
        }

        for(int j = 0; j < sub[i].size(); j++)//添加包含i,不包含i-1区间的影响
        {
            int id = sub[i][j];
            update(1, l[id], r[id], -1);
        }

        //查询极差 注意这里虽然知道最小值是a[i],但是由于使用了线段树,有lazy标记,标记可能没有更新到最底层,所以不能直接使用a[i]。
        int det = query_max(1, 1, n) - query_min(1, 1, n);
        if(det > d)
        {
            d = det;
            p = i;
        }
    }

    printf("%d\n", d);
    int t = 0;
    for(int i = 1; i <= m; i++)//统计区间
    {
        if(l[i] <= p && p <= r[i])
            ans[t++] = i;
    }
    printf("%d\n", t);
    for(int i = 0; i < t; i++)
    {
        if(i != 0)
            printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
    return 0;
}

同样的思想 优化暴力 另一类代码

#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\n",ans);
        int c=0;
        for(int i=1;i<=m;i++)
            if(l[i]<=id && id<=r[i]) ansc[c++]=i;
        printf("%d\n",c);
        for(int i=0;i<c;i++) printf("%d ",ansc[i]);
        printf("\n");
    }

    return 0;
}