分析

令 为以 结尾的最小代价。 ，后面的可以前缀和优化一下。 。令 为 的决策点，那么可以化简为 。那么这个就是个一次函数。其中 ，所以为了让 最小，那么我们显然要让 最小。那么现在就是要求 的最小值，放在坐标轴上，就是求直线 与所有一次函数的最小值，这个可以李超线段树来求，这样单次查询的复杂度为 。因为查询的直线有时间顺序，所以要可持久化一下，每次查询的就是一个前缀树，其实如果不是强制在线，这道题其实还可以 分治。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x:x;
}
const LL N = 1e5 + 100,M = 1e7,inf = 0x3f3f3f3f3f3f3f3f;
LL n,m,h[N],S[N],g[N],last = 0,A[N],B[N],rt[N],lastans;
LL size,lc[N * 30],rc[N * 30],id[N * 30];
LL f(LL Id,LL x) {return A[Id] * x + B[Id];}
void update(LL &a,LL b,LL l,LL r,LL u) {
    a = ++size;id[a] = id[b];lc[a] = lc[b];rc[a] = rc[b];
    LL val_l = f(id[a],l),val_r = f(id[a],r);
    LL val_L = f(u,l),val_R = f(u,r);
    if(!id[a] || (val_R <= val_r && val_L <= val_l)) {id[a] = u;return;}
    if(val_r <= val_R && val_l <= val_L) return;
    LL mid = l + r >> 1;
    update(lc[a],lc[b],l,mid,u);
    update(rc[a],rc[b],mid+1,r,u);
}
LL query(LL u,LL l,LL r,LL p) {
    if(l == r) return f(id[u],p);
    LL ans = f(id[u],p);
    LL mid = l + r >> 1;
    if(p <= mid) return min(ans,query(lc[u],l,mid,p));
    else return min(ans,query(rc[u],mid+1,r,p));
}
int main() {
    n = read();m = read();
    for(LL i = 1;i <= n;i++) h[i] = read();
    for(LL i = 1;i <= n;i++) S[i] = S[i-1] + read();
    B[0] = inf;
    g[1] = 0;A[1] = -2 * h[1];B[1] = h[1] * h[1] - S[1];
    update(rt[1],rt[0],1,M,1);
    for(LL i = 2;i <= n;i++) {
        g[i] = h[i] * h[i] + S[i-1] + query(rt[i-1],1,M,h[i]);
        A[i] = -2 * h[i];B[i] = g[i] + h[i] * h[i] - S[i];
        update(rt[i],rt[i-1],1,M,i);
    }
    while(m--) {
        LL x = ((read() ^ lastans) % n + n) % n + 1,y = read();
        if(x == 1) lastans = 0;
        else lastans = query(rt[x-1],1,M,y) + y * y + S[x-1];
        printf("%lld\n",lastans);
    }
    return 0;
}