可以过样例但是挂成 0 分了/kel

具体做法大概就是对于每个可以取到的阀值 $x$（$x$ 显然只会取所给的序列 $a$ 中的数）求出其得到的区间数量和区间长度平方和；然后用 ST 表 $f_{i, j}$ 维护区间数量为 $[i, i + 2^j - 1]$ 范围内的最大最终得分所对应的阀值 $x$。然后每次询问 $(l, r)$ 的时候直接 ST 表查询就可以了。

求看看，代码有注释

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, t, a[N], fa[N], sz[N], f[N][21], lg[N];
ll res[N], lastans;
struct node{
    int val, pos;
}b[N];

bool cmp(node x, node y) {
    if(x.val == y.val) return x.pos < y.pos;
    return x.val < y.val;
}

int getrt(int x) {
    if(fa[x] == x) return x;
    return fa[x] = getrt(fa[x]);
}

void merge(int x, int y) {
    x = getrt(x), y = getrt(y);
    sz[y] += sz[x], fa[x] = y;
    return ;
}

void stpre() {
    sort(b + 1, b + n + 1, cmp);
    ll cur = 0; int num = 0;
    for (int i = 1; i <= n; ++i) {
        int x = b[i].val, ps = b[i].pos;
        // 将 a sort 了一遍，让 x 从小到大，那么每次由一个较小的 x(a_{i-1}) 变为一个较大的 x(a_i) 时位置为 i(ps) 的数也可以加入区间中，这时候就讨论 ps-1 和 ps+1 是否能和 ps 连起来。
        // 使用并查集维护连通性
        fa[ps] = ps, sz[ps] = 1, num++;
        if(ps - 1 >= 1 && ps + 1 <= n && a[ps - 1] <= x && a[ps + 1] <= x) {
            //那么可以合并 ps 左右两侧
            int lx = getrt(ps - 1), rx = getrt(ps + 1);
            ll lst = 1ll * sz[lx] * sz[lx] + 1ll * sz[rx] * sz[rx];
            merge(lx, ps); merge(ps, rx);
            int sp = getrt(ps);
            cur += 1ll * sz[sp] * sz[sp] - lst;
            num -= 2;
        }
        else if(ps - 1 >= 1 && a[ps - 1] <= x) {
            int lx = getrt(ps - 1);
            ll lst = 1ll * sz[lx] * sz[lx];
            merge(lx, ps);
            int sp = getrt(ps);
            cur += 1ll * sz[sp] * sz[sp] - lst;
            num--;
        }
        else if(ps + 1 <= n && a[ps + 1] <= x) {
            int rx = getrt(ps + 1);
            ll lst = 1ll * sz[rx] * sz[rx];
            merge(rx, ps);
            int sp = getrt(ps);
            cur += 1ll * sz[sp] * sz[sp] - lst;
            num--;
        }
        else cur += 1ll;
        res[ps] = cur;
        if(cur * a[f[num][0]] * 1ll > res[f[num][0]] * x * 1ll || f[num][0] == 0) f[num][0] = ps;
    }
    lg[0] = -1;
    for (int i = 1; i <= n; ++i) {
        lg[i] = lg[i >> 1] + 1;
        for (int j = 1; j <= 20; ++j) {
            if(f[i][j - 1] == 0) f[i][j] = f[i + (1 << (j - 1))][j - 1];
            else if(f[i + (1 << (j - 1))][j - 1] == 0) f[i][j] = f[i][j - 1];
            else if(res[f[i][j - 1]] * f[i + (1 << (j - 1))][j - 1] * 1ll > res[f[i + (1 << (j - 1))][j - 1]] * f[i][j - 1] * 1ll) f[i][j] = f[i][j - 1];
            else f[i][j] = f[i + (1 << (j - 1))][j - 1];
        }
    }
    // for (int i = 1; i <= n; ++i) cout << res[i] << "\n";
    // return ;
    // for (int i = 1; i <= n; ++i) {
    //     cout << f[i][0] << ' ' << f[i][1] << ' ' << f[i][2] << "\n";
    // }
    return ;
}

int query(int l, int r) {
    int k = lg[r - l + 1];
    int ret;
    if(f[r - (1 << k) + 1][k] == 0) ret = f[l][k];
    else if(f[l][k] == 0) ret = f[r - (1 << k) + 1][k];
    else if(res[f[l][k]] * f[r - (1 << k) + 1][k] * 1ll > res[f[r - (1 << k) + 1][k]] * f[l][k] * 1ll) ret = f[l][k];
    else ret = f[r - (1 << k) + 1][k];
    return ret;
}

int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[i] = {a[i], i};
    }
    stpre();
    // for (int i = 1; i <= n; ++i) cout << f[i][0] << "\n";
    // return 0;
    for (int i = 1; i <= t; ++i) {
        int aa, bb, x, y, l, r; ll ls; scanf("%d%d%d%d", &aa, &bb, &x, &y);
        aa %= n, bb %= n, x %= n, y %= n, ls = lastans;
        l = (1ll * aa * lastans + x - 1) * 1ll % n + 1;
        r = (1ll * bb * lastans + y - 1) * 1ll % n + 1;
        if(l > r) swap(l, r);
        int ans = query(l, r);
        if(ans == 0) puts("-1 -1"), lastans = 1;
        else printf("%lld %d\n", res[ans], a[ans]), lastans = 1ll * res[ans] * ans % n;
        printf("%d %d %lld\n", l, r, ls);
    }
    return 0;
}