题解：P11896 「LAOI-9」此方的座位

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
	template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
	template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
	template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
	int lowbit(int x){return (x&-x);}
} using namespace Memory_Love;
const int N=1e5+5;
const int INF=0x3f3f3f3f3f3f3f3fll;
int n,m,a[N];
set<int> S;

#define Tree(u) tree[u]
#define Point(u) LINE[u]
#define F(u,x) Point(u).f(x)
#define lson(u) (u<<1)
#define rson(u) (u<<1|1)
#define mid (left+right>>1) 
struct Line
{
	int k,b;
	Line(int K=0,int B=0){k=K,b=B;}
	int f(int x){return k*x+b;}
	bool friend operator !=(const Line &a,const Line &b){return a.k!=b.k || a.b!=b.b;}
};
struct Segment_Tree
{
	Line LINE[N<<2];
	int tree[N<<2],tot;
	Line New_Line(double k,double b){return Line(k,b);}
	bool comp(int x,int y,int pos){return F(x,pos)>F(y,pos);}
	PII Max(PII a,PII b){return a.fi>b.fi? a:b;}
	void addtag(int u,int left,int right,int x)
	{
		int &y=Tree(u);
		if(comp(x,y,mid)) swap(x,y);
		if(comp(x,y,left)) addtag(lson(u),left,mid,x);
		if(comp(x,y,right)) addtag(rson(u),mid+1,right,x);
	}
	void update(int u,int L,int R,int x,int left=1,int right=n)
	{
		if(L<=left && R>=right)
		return addtag(u,left,right,x);
		if(L<=mid) update(lson(u),L,R,x,left,mid);
		if(R>mid)  update(rson(u),L,R,x,mid+1,right);
	}
	void insert_Pre(int x,int xx,int yy,double k)
	{
		int b=yy-k*xx;
		Point(++tot)=New_Line(k,b);
		return update(1,x,xx,tot);
	}
	void insert_Nex(int x,int y,int xx,double k)
	{
		int b=y-k*x;
		Point(++tot)=New_Line(k,b);
		return update(1,x,xx,tot);
	}
	PII query(int u,int x,int left=1,int right=n)
	{
		if(left==right)
		return mp(F(Tree(u),x),Tree(u));
		PDI ans=mp(F(Tree(u),x),Tree(u));
		if(x<=mid) ans=Max(ans,query(lson(u),x,left,mid));
		else ans=Max(ans,query(rson(u),x,mid+1,right));
		return ans;
	}
}ST;

void solve(int x,int y)
{
	if(S.find(x)!=S.end()) S.erase(x);
	
	int Pre=(*--S.lower_bound(x));
	int Nex=(*S.upper_bound(x));
	
	if(Pre==-INF)
	ST.insert_Pre(1,x,y,a[x]);
	else
	{
		ST.insert_Pre(Pre,x,y,a[x]);
		ST.insert_Pre(1,Pre,y-a[x]*(x-Pre),a[x]*2);
	}
	
	if(Nex==INF)
	ST.insert_Nex(x,y,n,-a[x]);
	else
	{
		ST.insert_Nex(x,y,Nex,-a[x]);
		ST.insert_Nex(Nex,y-a[x]*(Nex-x),n,-a[x]*2);
	}
}

bool Ending;
signed main()
{
	int i,kind,x,y,last_ans=0;
	read(n,m);
	S.insert(-INF),S.insert(INF);
	for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=n;i++)
	{
		x=read();
		if(x) S.insert(i);
	}
	while(m--)
	{
		read(kind,x);
		x=(x+last_ans-1)%n+1;
		if(kind==1)
		{
			y=read();
			solve(x,y);
		}
		if(kind==2) write(last_ans=max(ST.query(1,x).fi,0ll),'\n');
		if(kind==3) S.insert(x);
	}
	
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}