分析

看完题，首先这绝对是一个DP题
我们设

• Height[]表示高度
• Cost[]表示花费
• DP[]表示以当前点为截至点的花费最小值
• Pre[]表示花费的前缀和

算法一

那么DP方程：

那么我们就得到了一个的转移方程式

算法二

我们发现，对于每次的修改，需要的只是最后一次从转移到的最小值
那么我们考虑由这个性质来维护
当我们把位置上的值改为时
若要转移到位置
由转移式：

那么我们设

• A[i]=-2*Height[i]
• B[i]=Height[i]*Height[i]-Pre[i]+DP[i]
• Loc=y

我们发现这一次转移的最小值就是的最小值
所以，我们预处理出A[]和B[]即可，将A[]看作斜率,B[]看作截距
这个就可以用权值上的李超线段树维护了
以每个数组下标建立权值可持久化李超线段树即可维护
时间复杂度：

代码

//Newcoder 6944 E
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=1e5+10,MaxM=1e6+10;

LL Map[MaxN<<5];
LL Height[MaxN],DP[MaxN],Pre[MaxN];
LL Cost[MaxN],A[MaxN],B[MaxN]={INF};
LL Root[MaxN],Child[MaxN<<5][2];
LL Total,Test,Loc,Last,u,v,w,Cnt;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Copy(LL Res,LL New) { Child[Res][0]=Child[New][0]; Child[Res][1]=Child[New][1]; Map[Res]=Map[New]; }
inline LL Calc(LL X,LL Y) { return X*A[Y]+B[Y]; }
inline void Update(LL New,LL &Pre,LL L,LL R,LL Temp) {
    Pre=++Cnt;
    Copy(Pre,New);
    if(L==R) { if(Calc(L,Temp)<Calc(L,Map[Pre])) Map[Pre]=Temp; return; }
    LL Mid=(L+R)>>1;
    if(Calc(Mid,Temp)<Calc(Mid,Map[Pre])) swap(Temp,Map[Pre]);
    if(Calc(L,Temp)<Calc(L,Map[Pre])) Update(Child[New][0],Child[Pre][0],L,Mid,Temp);
    else if(Calc(R,Temp)<Calc(R,Map[Pre])) Update(Child[New][1],Child[Pre][1],Mid+1,R,Temp);
}

inline LL Get(LL New,LL L,LL R) {
    if(L==R) { return Calc(Loc,Map[New]); }
    LL Mid=(L+R)>>1,Res=INF;
    Res=min(Res,Calc(Loc,Map[New]));
    if(Loc<=Mid) { Res=min(Res,Get(Child[New][0],L,Mid)); }
    else { Res=min(Res,Get(Child[New][1],Mid+1,R)); }
    return Res;
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total>>Test;
    FOR(i,1,Total) cin>>Height[i];
    FOR(i,1,Total) cin>>Cost[i],Pre[i]=Pre[i-1]+Cost[i];
    A[1]=-2*Height[1];
    B[1]=Height[1]*Height[1]-Pre[1];
    Update(Root[0],Root[1],0,MaxM,1);
    FOR(i,2,Total) {
        Loc=Height[i];
        DP[i]=Height[i]*Height[i]+Pre[i-1]+Get(Root[i-1],0,MaxM);
        A[i]=-2*Height[i];
        B[i]=DP[i]+Height[i]*Height[i]-Pre[i];
        Update(Root[i-1],Root[i],0,MaxM,i);
    }
    while(Test--) {
        cin>>u>>v;
        u=((u^Last)%Total+Total)%Total+1;
        if(u==1) { cout<<(Last=0)<<endl; }
        else {
            Loc=v;
            cout<<(Last=Get(Root[u-1],0,MaxM)+v*v+Pre[u-1])<<endl;
        }
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}