_abcd_
2024-11-18 10:20:58
考虑单次询问怎么做。
不难想到枚举
回到原题。同样是枚举
关于
至于对
否则
那么,有
即
对于
#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define maxn 500005
#define ls pos<<1
#define rs pos<<1|1
#define inf 1000000000
using namespace std;
int re()
{
int x=0;
bool t=1;
char ch=getchar();
while(ch>'9'||ch<'0')
t=ch=='-'?0:t,ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return t?x:-x;
}
void gx(int &x,int y)
{
if(y>x)
x=y;
}
void gn(int &x,int y)
{
if(y<x)
x=y;
}
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)
{
return x<y?x:y;
}
struct Tag
{
int a,b,c;
void clr()
{
a=inf,b=inf,c=inf;
}
void add(Tag t)
{
gn(b,t.b);
if(c<inf)
gn(b,c+t.a);
else
gn(a,t.a);
if(t.c<inf)
c=t.c;
}
}tag[maxn<<2];
int n;
int a[maxn],b[maxn];
int pre[maxn];
int mx[maxn<<2],mn[maxn<<2];
void update(int pos)
{
mx[pos]=max(mx[ls],mx[rs]);
mn[pos]=min(mn[ls],mn[rs]);
}
void add(int pos,Tag t)
{
if(t.c<inf)
mx[pos]=mn[pos]=t.c;
tag[pos].add(t);
}
void pushtag(int pos)
{
add(ls,tag[pos]);
add(rs,tag[pos]);
tag[pos].clr();
}
void build_tree(int pos,int l,int r)
{
tag[pos].clr();
mx[pos]=pre[r];
mn[pos]=pre[l];
if(l==r)
return;
int mid=l+r>>1;
build_tree(ls,l,mid);
build_tree(rs,mid+1,r);
update(pos);
}
void cha(int pos,int l,int r,int L,int x)
{
if(mn[pos]>=x)
return;
if(l>=L&&mx[pos]<=x)
{
add(pos,{inf,inf,x});
return;
}
pushtag(pos);
int mid=l+r>>1;
if(L<=mid)
cha(ls,l,mid,L,x);
cha(rs,mid+1,r,L,x);
update(pos);
}
void print(int pos,int l,int r)
{
if(l==r)
{
printf("%d\n",min(pre[l]+tag[pos].a,tag[pos].b));
return;
}
pushtag(pos);
int mid=l+r>>1;
print(ls,l,mid);
print(rs,mid+1,r);
}
signed main()
{
n=re();
for(int i=1;i<=n;i++)
a[i]=re();
for(int i=1;i<=n;i++)
b[i]=re();
vector<pair<int,int>>tmp;
for(int i=1;i<=n;i++)
{
if(a[i]<b[i])
swap(a[i],b[i]);
tmp.push_back({a[i],i});
tmp.push_back({b[i],i});
}
pre[0]=-1e9;
for(int i=1;i<=n;i++)
pre[i]=max(pre[i-1],-a[i]);
build_tree(1,1,n);
sort(all(tmp));
reverse(all(tmp));
for(auto [x,i]:tmp)
{
tag[1].add({x,inf,inf});
if(x>b[i])
cha(1,1,n,i,-b[i]);
else
cha(1,1,n,i,inf-1);
}
print(1,1,n);
return 0;
}