题解：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;
}