最优贸易分块

C国有 n 座城市，编号是 1 到 n ，编号为 i 的城市有路到编号为 i+1 的城市（编号为 n 的城市没有路到其他的城市）。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙再次来到C国旅游。他还是想贩卖水晶赚取旅费，在某个城市买入，再另一个城市卖出。

他将从编号为 a 的城市到编号到 b 的城市。请你帮他算算，最多能赚多少钱。

注：他最多进行一次买入和一次卖出。

输入描述:

第一行两个整数n和m，表示n个城市和m个询问。
第二行n个整数，表示n座城市水晶的买入和卖出的价格。
接下来m行，每行两个整数a,b，表示阿龙要从编号为a的城市到编号为b的城市（保证a<b）。

输出描述:

对于每个询问输出阿龙最多能赚多少钱。

示例1
输入

6 3
2 1 3 6 4 5
1 2
2 4
1 6

输出

0
5
5

说明

从1到2，无法赚钱。
从2到4，在编号为2的城市买入，在编号为4的城市卖出。
从1到6，在编号为2的城市买入，在编号为4的城市卖出。

zuiyoumaoyi_fenkuai.cppview raw

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;


const int N = 320, M = 100010;
int n, m;
int S;
int A[M];
int V[N], Mi[N], Mx[N];

int query(int L, int R){
    int ka = L/S, kb= R/S;
    int res = 0, mi = A[L];
    if(ka==kb){
        for(int i=L+1;i<=R;i++){
            res = max(res, A[i] - mi);
            mi = min(mi, A[i]);
        }
    }
    else{
        for(int i=L+1;i<(ka+1)*S;i++){
            res = max(res, A[i] - mi);
            mi = min(mi, A[i]);
        }
        for(int i=ka+1;i<kb;i++){
            res = max(res, max(V[i], Mx[i] - mi));
            mi = min(mi, Mi[i]);
        }

        for(int i=kb*S;i<=R;i++){
            res = max(res, A[i] - mi);
            mi = min(mi, A[i]);
        }
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &A[i]);
    S = sqrt(n);
    for(int i=1;i<=n/S; i++){
        V[i] = 0;
        Mi[i] = 1e9;
        Mx[i] = 0;
    }

    for(int i=0;i<=n;i++){
        int x = i/S;
        V[x] = max(V[x], A[i] - Mi[x]);
        Mi[x] = min(Mi[x], A[i]);
        Mx[x] = max(Mx[x], A[i]);
    }

    while(m--){
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = query(l, r);
        printf("%d\n", ans);
    }
    return 0;

}

zuiyoumaoyi_segtree.cppview raw

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100010;
int n, m;
int A[N];

struct Node{
    int val, mi, mx;
    int L, R;
}tree[N<<2];


void up(Node&root, Node &ls, Node &rs){
    root.val = max(max(ls.val, rs.val), rs.mx-ls.mi);
    root.mi = min(ls.mi, rs.mi);
    root.mx = max(ls.mx, rs.mx);
}

void build(int L, int R, int p){
    tree[p].L = L, tree[p].R = R;
    if(L==R){
        tree[p].val = 0;
        tree[p].mi = A[L];
        tree[p].mx = A[L];
        return;
    }
    int mid = L+R>>1;
    build(L, mid, p<<1);
    build(mid+1, R, p<<1|1);
    //递归完毕，用tree
    up(tree[p], tree[p<<1], tree[p<<1|1]);
}


Node query(int L, int R, int p){
    if(tree[p].L ==L && tree[p].R==R){
        return tree[p];
    }
    int mid = tree[p].L + tree[p].R >>1;
    if(R<=mid) return query(L, R, p<<1);
    else if(L>mid) return query(L, R, p<<1|1);
    else{
//        准备开始递归
        Node B = query(L, mid, p<<1);
        Node C = query(mid+1, R, p<<1|1);
        Node res;
        up(res, B, C);
        return res;
    }
}

int main(){
    scanf("%d%d", &n ,&m);
    for(int i=1;i<=n;i++) scanf("%d", &A[i]);
    build(1, n, 1);
    while(m--){
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d\n", query(L, R, 1).val);
    }
    return 0;
}

zuiyoumaoyi_beizeng.cppview raw

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100010;
int A[N];
int n, m;
int V[N][17], Mi[N][17], Mx[N][17];

int query(int L, int R){
    int step = R - L + 1;
    int res = 0, mi = 1e9;
    for(int i=0;(1<<i)<=step;i++){
        if(step & (1<<i)){
            res = max(res, max(V[L][i], Mx[L][i] - mi));
            mi = min(mi, Mi[L][i]);
            L += (1<<i);
        }
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) {
        scanf("%d", &A[i]);
        V[i][0] = 0;
        Mi[i][0] = A[i];
        Mx[i][0] = A[i];
    }

    for(int j=1;(1<<j)<=n;j++){
//      i starts from i cause'  A starts from 1
        for(int i=1;i+(1<<j)-1<=n;i++){
            int t = i+(1<<j-1);
            V[i][j] = max(max(V[i][j-1], V[t][j-1]), Mx[t][j-1] - Mi[i][j-1]);
            Mx[i][j] = max(Mx[i][j-1], Mx[t][j-1]);
            Mi[i][j] = min(Mi[i][j-1], Mi[t][j-1]);
        }
    }

    while(m--){
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d\n", query(L, R));
    }
    return 0;
}

zuiyoumaoyi_union_set.cppview raw

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100010;
int A[N];
int fa[N];
// corresponding value from i to root
int V[N], Mx[N], Mi[N];
int ans[N];

int n, m;

struct Node{
    int L, id;
};
vector<Node>query[N];


int getfa(int x){
    if(fa[x] != x) {
        int t = fa[x];
        // finish calc of father's Mi[t], V[t], Mx[t]
        fa[x] = getfa(t);
        // x--> t --> fa[x]
        V[x] = max(V[x], max(V[t], Mx[t] - Mi[x]));
        Mi[x] = min(Mi[x], Mi[t]);
        Mx[x] = max(Mx[x], Mx[t]);
    }
    return fa[x];
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%d", &A[i]);
        fa[i] = i;
        Mi[i] = Mx[i] = A[i];
        V[i] = 0;
    }

    for(int i=1;i<=m;i++){
        int L, R;
        scanf("%d%d", &L, &R);
        query[R].push_back((Node){L, i});
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<query[i].size();j++){
            int L = query[i][j].L;  //[L, i]
            getfa(L);
            ans[query[i][j].id] = V[L];
        }
        fa[i] = i+1;
    }

    for(int i=1;i<=m;i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}