题面
思路
首先看看我们到底要干什么：有$1e6$次询问，遍历$i$，每次要求一个形如$b_i ast a_j - a_i ast b_j$的东西的最大值
考虑如果一个$j$的决策在当前的$i$上比$k$这个位置更优会得到什么：
$b_i ast a_j - a_i ast b_j > b_i ast a_k - a_i ast b_k$
$b_i ast (a_j-a_k) > a_i ast (b_j-b_k)$
$frac{b_i}{a_i} > frac{b_j-b_k}{a_j-a_k}$
考虑对于询问区间维护右边那个玩意儿的下凸包$lis$，显然第一个满足$frac{b_{lis[j]}-b_{lis[j+1]}}{a_{lis[j]}-a_{lis[j+1]}} > frac{b_i}{a_i}$的$j$就是最优解，因为维护了下凸包所以这个东西可以二分
我们开一棵线段树维护每个线段树节点区间上的下凸包，查询的时候就把目标区间拆分到线段树节点上，再做一次上面的操作
线段树维护凸包的总复杂度是$O(qlog n)$，查询因为区间拆分完了二分，复杂度还是$O(qlog n)$
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#define MOD 1000000007
#define ll long long
using namespace std;
inline ll read(){
ll re=0,flag=1;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') flag=-1;
ch=getchar();
}
while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n;ll g[1000010];int a[1000010],b[1000010],c[1000010];
int mmp[30000010],len[4000010];
int *q[4000010],*cur=mmp;//动态内存池，实际上大概2.5e7就够了
void build(int l,int r,int num){
q[num]=cur;len[num]=0;
cur+=r-l+2;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,num<<1);
build(mid+1,r,num<<1|1);
}
inline double get(int l,int r){return (double)(b[r]-b[l])/(double)(a[r]-a[l]);}
void change(int l,int r,int num,int pos){插入新元素，维护log个凸包
while(len[num]>=2&&get(q[num][len[num]-1],q[num][len[num]])>get(q[num][len[num]],pos)) q[num][len[num]--]=0;
q[num][++len[num]]=pos;
if(l==r) return;
int mid=(l+r)>>1;
if(mid>=pos) change(l,mid,num<<1,pos);
else change(mid+1,r,num<<1|1,pos);
}
inline ll f(int i,int j){
return 1ll*b[i]*a[j]-1ll*b[j]*a[i];
}
ll query(int l,int r,int ql,int qr,int num,double lim,int now){
if(l>=ql&&r<=qr){//找到目标拆分区间，二分查询
if(len[num]==1) return f(now,q[num][1]);//注意特判凸包只有一个点的情况
l=1;r=len[num]-1;int mid;
while(l<r){
mid=(l+r)>>1;
if(get(q[num][mid],q[num][mid+1])<lim) l=mid+1;
else r=mid;
}
if(l==len[num]-1&&get(q[num][l],q[num][l+1])<lim) l++;//注意特判找到的倒数第二个点没有最后一个点优的情况
return f(now,q[num][l]);
}
int mid=(l+r)>>1;ll re=-1e18;
if(mid>=ql) re=max(re,query(l,mid,ql,qr,num<<1,lim,now));
if(mid<qr) re=max(re,query(mid+1,r,ql,qr,num<<1|1,lim,now));
return re;
}
int main(){
n=read();int i;ll tmp;
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=n;i++) b[i]=read();
for(i=1;i<=n;i++) c[i]=read();
build(1,n,1);
for(i=1;i<=n;i++){
a[i]^=g[i-1];
b[i]^=g[i-1];
c[i]^=g[i-1];
change(1,n,1,i);
g[i]=(g[i-1]+(tmp=query(1,n,1,i-c[i],1,(double)b[i]/(double)a[i],i))%MOD+MOD)%MOD;
}
cout<<g[n]<<'
';
}