1011- DOS Card

给一个长度为 $n$ 的数组，$m$ 次询问，每次询问给定一个区间 $L, R$，在 $L, R$ 中选择四个位置 $i < j < k < l$，四个位置上的数两两成为一组，你可以任意搭配，但每个数只能在一组里。问你价值最大是多少。一对数 $a_i, a_j$ 的价值定义为 $a_i^2 - a_j^2$。$4≤\sum n≤2\times10^5,1≤\sum m≤2\times 10^5$

要想价值最大，那么任意一对数字里肯定前面的数尽可能的大，后面的数字尽可能地小。由于只有 $4$ 个数，下标还要递增。考虑分类讨论答案由哪些情况产生。答案其实是 $?^2 + ?^2 - ?^2 - ?^2$ 的形式，所以我们考虑为四个数字分配符号。

1. ++–, +-+-, 这就是答案

考虑如何得到答案：

选的数字可能会跨越线段树上的区间，所以我们需要把答案分割，像线段树递归一样。

++–可以分割为：

• ++｜–
• +｜+–

• ++-｜-

• 其中+–，++-分解为

• +｜– +-|-
• +|+-, ++|-

+-+-：

• +-｜+-
• +｜-+-
• +-+｜-

观察发现每个区间需要维护如下的最大值：

+，-，，+-，-+，–，-，+-+，+–，-+-，++–，+-+-

一共 $12$ 个

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif

constexpr long long inf = 1e18;

template<typename T>
void gao(T &a, T b) {
  if (b > a) {
    a = b;
  }
}

class segtree {
 public:
  struct node {
    // ++-- +-+-
    array<long long, 2> f4 = {{-inf, -inf}}; 
    // + -
    array<long long, 2> f1 = {{-inf, -inf}};
    // ++ +- -+ -- 
    array<long long, 4> f2 = {{-inf, -inf, -inf, -inf}};
    // +-- ++- +-+ -+-
    array<long long, 4> f3 = {{-inf, -inf, -inf, -inf}};
    void apply(int l, int r, long long v) {
      f1[0] = v;
      f1[1] = -v;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    for (int i = 0; i < 2; i++) {
      res.f4[i] = max(a.f4[i], b.f4[i]);
    }
    for (int i = 0; i < 2; i++) {
      res.f1[i] = max(a.f1[i], b.f1[i]);
    }
    for (int i = 0; i < 4; i++) {
      res.f2[i] = max(a.f2[i], b.f2[i]);
    }
    for (int i = 0; i < 4; i++) {
      res.f3[i] = max(a.f3[i], b.f3[i]);
    }
    // ++--: +|+--, ++|--, ++-|- 
    // +-+-: +|-+-, +-|+-, +-+|-
    gao(res.f4[0], a.f1[0] + b.f3[0]);
    gao(res.f4[0], a.f2[0] + b.f2[3]);
    gao(res.f4[0], a.f3[1] + b.f1[1]);
    gao(res.f4[1], a.f1[0] + b.f3[3]);
    gao(res.f4[1], a.f2[1] + b.f2[1]);
    gao(res.f4[1], a.f3[2] + b.f1[1]);

    gao(res.f2[0], a.f1[0] + b.f1[0]);
    gao(res.f2[1], a.f1[0] + b.f1[1]);
    gao(res.f2[2], a.f1[1] + b.f1[0]);
    gao(res.f2[3], a.f1[1] + b.f1[1]);
    gao(res.f3[0], a.f1[0] + b.f2[3]);
    gao(res.f3[0], a.f2[1] + b.f1[1]);
    gao(res.f3[1], a.f1[0] + b.f2[1]);
    gao(res.f3[1], a.f2[0] + b.f1[1]);
    gao(res.f3[2], a.f1[0] + b.f2[2]);
    gao(res.f3[2], a.f2[1] + b.f1[0]);
    gao(res.f3[3], a.f1[1] + b.f2[1]);
    gao(res.f3[3], a.f2[2] + b.f1[1]);
    return res;
  }

  inline void push(int x, int l, int r) {
    // int y = (l + r) >> 1;
    // int z = x + ((y - l + 1) << 1);
    // if (tree[x].f1[0]dd != 0) {
    //   tree[x + 1].f1[0]pply(l, y, tree[x].f1[0]dd);
    //   tree[z].f1[0]pply(y + 1, r, tree[x].f1[0]dd);
    //   tree[x].f1[0]dd = 0;
    // }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      a[i] *= a[i];
    }
    segtree st(a);
    while (q--) {
      int l, r;
      cin >> l >> r;
      l--; r--;
      auto nd = st.get(l, r);
      cout << max(nd.f4[0], nd.f4[1]) << '\n';
    }

  }
  return 0;
}