AC:

世界尽头 · 2021-01-08 15:39:57 · 题解

#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int rd()
{
    int data = 0;
    char ch = 0;
    ch = getchar();

    while(!isdigit(ch))ch = getchar();

    while(isdigit(ch))data = (data << 1) + (data << 3) + (ch ^ 48), ch = getchar();

    return data;
}
const int N = 5e5 + 5;
int n, q, a[N], dep[N], stk[N], top, first[N], cnt, f[N][20];
ll lastans, s[N][20];
struct edges
{
    int v, nxt;
} e[N];
inline void add(int u, int v)
{
    e[++cnt] = (edges) {v, first[u]}, first[u] = cnt;
}
void dfs(int u)
{
    for(int re i = 1; (1 << i) < dep[u]; ++i)f[u][i] = f[f[u][i - 1]][i - 1], s[u][i] = s[u][i - 1] + s[f[u][i - 1]][i - 1];

    for(int re v, i = first[u]; i; i = e[i].nxt)
    {
        v = e[i].v;

        if(!dep[v])s[v][0] = (ll)(u - v) * a[v], f[v][0] = u, dep[v] = dep[u] + 1, dfs(v);
    }
}
ll ask(int x, int l, ll re ret = 0)
{
    for(int re i = 19; ~i; --i)
        if(f[x][i] && f[x][i] - x <= l)
            ret += s[x][i], l -= (f[x][i] - x), x = f[x][i];

    ret += (ll)l * a[x];
    return ret;
}
signed main()
{
    n = rd(), q = rd();

    for(int re i = 1; i <= n; ++i)a[i] = rd();

    a[n + 1] = INT_MAX;

    for(int re i = 1; i <= n + 1; ++i)
    {
        while(top && a[stk[top]] < a[i])add(i, stk[top--]);

        stk[++top] = i;
    }

    dfs(n + 1);

    while(q--)
    {
        ll re u = rd(), v = rd();
        int re l = 1 + (u ^ lastans) % n, len = 1 + (v ^ (lastans + 1)) % (n - l + 1);
        printf("%lld\n", lastans = ask(l, len));
    }

    exit(0);
}