C++14(g++5.4) 解法, 执行用时: 356ms, 内存消耗: 34928K, 提交时间: 2020-08-31 23:34:56

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
bool Cmp;
struct Line 
{
	mutable ll k, b, p;
	bool operator < (const Line& oth) const { return Cmp ? p < oth.p : k < oth.k; }
};
struct ConvecHull : multiset<Line> 
{
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) 
	{ 
		if(!b) return a>0 ? inf : -inf;
		return a / b - ((a ^ b) < 0 && a % b); 
	}
	bool isect(iterator x, iterator y) 
	{
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->b > y->b ? inf : -inf;
		else x->p = div((y->b - x->b), (x->k - y->k));
		return x->p >= y->p;
	}
	void add(ll k, ll b) 
	{
		auto z = insert({k, b, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
	}
	ll qry(ll x) 
	{
		Cmp = 1; auto l = *lower_bound({0, 0, x}); Cmp = 0;
		return l.k * x + l.b;
	}
}ch[N];
int n, h[N], cost[N];
ll dp[N];
void ins(int x, ll k, ll b)
{
	for(int i=x; i<=n; i+=(i&-i)) ch[i].add(k, b); 
}
ll ask(int x, ll p)
{
	ll ans = -LLONG_MAX;
	for(int i=x; i>0; i-=(i&-i)) if(ch[i].size()) ans = max(ans, ch[i].qry(p));
	return ans;
}
int main()
{
	int _; scanf("%d%d", &n, &_);
	for(int i=1; i<=n; i++) scanf("%d", h+i);
	for(int i=1; i<=n; i++) scanf("%d", cost+i), cost[i] += cost[i-1];
	ins(1, 2*h[1], -h[1]*h[1]+cost[1]);
	for(int i=2; i<=n; i++)
	{
		dp[i] = -ask(i-1, h[i]) + h[i]*h[i] + cost[i-1];
		ins(i, 2*h[i], -h[i]*h[i]+cost[i]-dp[i]);
	}
	ll lstans = 0;
	while(_--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x = ((x^lstans)%n + n)%n + 1;
		if(x==1) printf("%lld\n", lstans=0);
		else printf("%lld\n", lstans=-ask(x-1, y)+y*y+cost[x-1]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 200ms, 内存消耗: 22136K, 提交时间: 2020-08-21 21:35:25

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+9,M=1e6+9;
ll a[N],b[N],h[N],w[N],f[N];
int L[N*30],R[N*30];
int s[N*30],u,tot,rt[N];
inline ll g(int x,int o){return b[o]+a[o]*x;}
void upd(int old,int &k,int l,int r,int t){
	k=++tot; s[k]=s[old]; L[k]=L[old]; R[k]=R[old];
	if(l==r){
		if(g(l,t)<g(l,s[k]))s[k]=t;
		return;
	}
	int m=l+r>>1;
	if(g(m,t)<g(m,s[k])) swap(t,s[k]);
	if(g(l,t)<g(l,s[k])) upd(L[old],L[k],l,m,t);
	else if(g(r,t)<g(r,s[k])) upd(R[old],R[k],m+1,r,t);
}//插入直线
ll qry(int k,int l,int r){
	if(l==r)return g(u,s[k]);
	int m=l+r>>1;
	return min(g(u,s[k]),u<=m?qry(L[k],l,m):qry(R[k],m+1,r));
}//查询
int main(){
	int n,i,m;
	scanf("%d%d",&n,&m),b[0]=1e18;
	for(i=1;i<=n;++i)scanf("%lld",h+i);
	for(i=1;i<=n;++i)scanf("%lld",w+i),w[i]+=w[i-1];
	a[1]=-2*h[1],b[1]=h[1]*h[1]-w[1],upd(rt[0],rt[1],0,M,1);
	for(i=2;i<=n;++i){
		u=h[i],f[i]=h[i]*h[i]+w[i-1]+qry(rt[i-1],0,M);
		a[i]=-2*h[i],b[i]=f[i]+h[i]*h[i]-w[i],upd(rt[i-1],rt[i],0,M,i);
	}
	ll lst=0; 
	for (i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x=((x^lst)%n+n)%n+1;
		if (x==1){
			printf("%lld\n",(lst=0));
			continue;
		}
//		cout<<x<<" "<<y<<"   nani\n"; 
		u=y;lst=qry(rt[x-1],0,M)+y*y+w[x-1];
		printf("%lld\n",lst);
	}
	return 0;
}