自动搬运

查看原文

来自洛谷，原作者为

	Little_Cancel_Sunny 抗线，点灯，收残血，啥几把事都给nm做了||李超线段树真乃神技也

搬运于2025-08-24 23:11:11，当前版本为作者最后更新于2025-07-31 21:19:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

前置知识

李超线段树，线段树。

思路

其实和板子没什么差别，就是多了一个降噪设备。

考虑这个降噪设备的影响，不难发现它不过就是增加了线段的斜率，看个图。

所以对于一个点发出的噪声，如果有降噪设备的存在，不过就是我们需要多维护一两条线段而已。

对于左右的最近的两个降噪设备，直接线段树维护即可。

然后就可以利用找到的左右端点确定所有线段的形状，然后直接求解即可。

tips

1. 答案至少为 $0$。
2. 是线段！！！

代码

#include<bits/stdc++.h>
#define lson k<<1
#define rson k<<1|1
#define int long long 
using namespace std;

const int N=1e6+15;
const int inf=1e18;

struct line
{
	int k,b;
	int l,r;
	int get_y(int x)
	{
		if(x>=l&&x<=r)
			return k*x+b;
		return -inf;
	}
}li[N];
struct segment_tree
{
	int lans,rans;
}t[N];
struct lc_segment_tree
{
	int id;
}lt[N];
bool fl[N];
int a[N];
int lastans,n,m,cnt;

void push_up(int k)
{
	t[k].lans=min(t[lson].lans,t[rson].lans);
	t[k].rans=max(t[lson].rans,t[rson].rans);
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		if(fl[l])
			t[k].lans=t[k].rans=l;
		else 
			t[k].lans=inf,t[k].rans=-inf;
		return;
	}
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	push_up(k);
}

void update_p(int k,int l,int r,int loc,int x)
{
	if(l==r)
	{
		if(x)
			t[k].lans=t[k].rans=l;
		else 
			t[k].lans=inf,t[k].rans=-inf;
		return;
	}
	int mid=(l+r)>>1;
	if(loc<=mid)
		update_p(lson,l,mid,loc,x);
	else 
		update_p(rson,mid+1,r,loc,x);
	push_up(k);
}

int query_l(int k,int l,int r,int ln,int rn)
{
	if(l>=ln&&r<=rn)
		return t[k].rans;
	int mid=(l+r)>>1;
	if(rn<=mid)
		return query_l(lson,l,mid,ln,rn);
	else if(ln>mid)
		return query_l(rson,mid+1,r,ln,rn);
	else 
		return max(query_l(lson,l,mid,ln,rn),query_l(rson,mid+1,r,ln,rn));
}

int query_r(int k,int l,int r,int ln,int rn)
{
	if(l>=ln&&r<=rn)
		return t[k].lans;
	int mid=(l+r)>>1;
	if(rn<=mid)
		return query_r(lson,l,mid,ln,rn);
	else if(ln>mid)
		return query_r(rson,mid+1,r,ln,rn);
	else 
		return min(query_r(lson,l,mid,ln,rn),query_r(rson,mid+1,r,ln,rn));
}

void update(int k,int l,int r,int ln,int rn,int loc)
{
	int mid=(l+r)>>1;
	if(l>=ln&&r<=rn)
	{
		if(!lt[k].id)
		{
			lt[k].id=loc;
			return;
		}
//		cout<<"location "<<loc<<" "<<l<<" "<<r<<endl;
		if(li[lt[k].id].get_y(mid)<li[loc].get_y(mid))
			swap(lt[k].id,loc);
		if(li[lt[k].id].get_y(l)<li[loc].get_y(l))
			update(lson,l,mid,ln,rn,loc);
		if(li[lt[k].id].get_y(r)<li[loc].get_y(r))
			update(rson,mid+1,r,ln,rn,loc);
	}
	else 
	{
		if(rn<=mid)
			update(lson,l,mid,ln,rn,loc);
		else if(ln>mid)
			update(rson,mid+1,r,ln,rn,loc);
		else 
			update(lson,l,mid,ln,rn,loc),update(rson,mid+1,r,ln,rn,loc);
	}
}

int query(int k,int l,int r,int loc)
{
	int res=-inf;
	if(lt[k].id)
		res=li[lt[k].id].get_y(loc);
//	cout<<lt[k].id<<endl;
	if(l==r)
		return res;
	int mid=(l+r)>>1;
	if(loc<=mid)
		return max(res,query(lson,l,mid,loc));
	else 
		return max(res,query(rson,mid+1,r,loc));
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>fl[i];
	build(1,1,n);
	while(m--)
	{
		int opt,i,j;
		cin>>opt>>i;
		i=(i+lastans-1)%n+1;
		if(opt==1)
		{
			cin>>j;
//			j=(j+lastans-1)%n+1;
			update_p(1,1,n,i,0);
			int l=query_l(1,1,n,1,i);
			int r=query_r(1,1,n,i,n);
//			cout<<"l is "<<l<<endl;
//			cout<<"r is "<<r<<endl;
			li[++cnt]={a[i],j-(i)*a[i],max(1ll,l),i};
//			cout<<li[cnt].k<<" "<<li[cnt].b<<" "<<li[cnt].l<<" "<<li[cnt].r<<endl;
			update(1,1,n,li[cnt].l,li[cnt].r,cnt);
			li[++cnt]={-a[i],j+(i)*a[i],i,min(r,n)};
//			cout<<li[cnt].k<<" "<<li[cnt].b<<" "<<li[cnt].l<<" "<<li[cnt].r<<endl;
			update(1,1,n,li[cnt].l,li[cnt].r,cnt);
			if(l!=-inf)
			{
				li[++cnt]={2*a[i],j-(i-l)*a[i]-(l)*2*a[i],1,l};
//				cout<<li[cnt].k<<" "<<li[cnt].b<<" "<<li[cnt].l<<" "<<li[cnt].r<<endl;
				update(1,1,n,li[cnt].l,li[cnt].r,cnt);
			}
			if(r!=inf)
			{
				li[++cnt]={-2*a[i],j-(r-i)*a[i]+(r)*2*a[i],r,n};
//				cout<<li[cnt].k<<" "<<li[cnt].b<<" "<<li[cnt].l<<" "<<li[cnt].r<<endl;
				update(1,1,n,li[cnt].l,li[cnt].r,cnt);
			}
		}
		else if(opt==2)
		{
			lastans=max(query(1,1,n,i),0ll);
			cout<<lastans<<endl;
		}
		else 
			update_p(1,1,n,i,1);
	}
	return 0;
}