题解：P11896 「LAOI-9」此方的座位
题解：P11896 「LAOI-9」此方的座位
前置知识
李超线段树，线段树。
思路
其实和板子没什么差别，就是多了一个降噪设备。
考虑这个降噪设备的影响，不难发现它不过就是增加了线段的斜率，看个图。
所以对于一个点发出的噪声，如果有降噪设备的存在，不过就是我们需要多维护一两条线段而已。
对于左右的最近的两个降噪设备，直接线段树维护即可。
然后就可以利用找到的左右端点确定所有线段的形状，然后直接求解即可。
tips
- 答案至少为
0 。 - 是线段！！！
代码
#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;
}