以前其实学过的但是不会拍扁重构……所以这几天学了一下 \(K-D\ Tree\) 的正确打开姿势。
\(K\) 维 \(K-D\ Tree\) 的单次操作最坏时间复杂度为 \(O(k\times n^{1-\frac 1k})\)
1、[Violet]天使玩偶/SJY摆棋子
二维 \(K-D\ Tree\)。
不过要暴力重构。。。我终于会了，但不开 \(O_2\) 过不去。。。
\(Code\ Below:\)
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
const int inf=0x3f3f3f3f;
const double alpha=0.75;
int n,m,D,rt,tot,ans,cnt,rub[maxn<<1],top;
struct node{
int d[2];
}a[maxn<<1];
struct KD_Tree{
int d[2],Max[2],Min[2],ch[2],siz;
inline void init(){
d[0]=d[1]=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=siz=0;
}
inline void get(node a){
Max[0]=Min[0]=d[0]=a.d[0];
Max[1]=Min[1]=d[1]=a.d[1];
}
}t[maxn<<1];
inline bool operator < (const node &a,const node &b){
return a.d[D]<b.d[D];
}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline int newnode(){
int x=top?rub[top--]:++cnt;
t[x].init();return x;
}
inline void update(int x,int y){
t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);
t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);
t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);
t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x){
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
if(t[x].ch[0]) update(x,t[x].ch[0]);
if(t[x].ch[1]) update(x,t[x].ch[1]);
}
int build(int l,int r,int now){
int mid=(l+r)>>1,x=newnode();D=now;
nth_element(a+l,a+mid,a+r+1);
t[x].get(a[mid]);
if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);
if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);
pushup(x);return x;
}
inline void del(int x){
if(t[x].ch[0]) del(t[x].ch[0]);
a[++tot]=(node){t[x].d[0],t[x].d[1]};
rub[++top]=x;
if(t[x].ch[1]) del(t[x].ch[1]);
}
inline void check(int &x,int now){
if(1.0*max(t[t[x].ch[0]].siz,t[t[x].ch[1]].siz)>1.0*alpha*t[x].siz)
tot=0,del(x),x=build(1,tot,now);
}
void insert(int &x,node c,int now){
if(!x){
x=newnode();
t[x].get(c);
return ;
}
if(c.d[now]<=t[x].d[now]) insert(t[x].ch[0],c,now^1);
else insert(t[x].ch[1],c,now^1);
pushup(x);check(x,now);
}
inline int dis(int x,int X,int Y){
return max(t[x].Min[0]-X,0)+max(X-t[x].Max[0],0)+max(t[x].Min[1]-Y,0)+max(Y-t[x].Max[1],0);
}
void query(int x,int X,int Y){
int L=abs(t[x].d[0]-X)+abs(t[x].d[1]-Y),d[2],k;
d[0]=t[x].ch[0]?dis(t[x].ch[0],X,Y):inf;
d[1]=t[x].ch[1]?dis(t[x].ch[1],X,Y):inf;
ans=min(ans,L);k=d[0]>d[1];
if(d[k]<ans) query(t[x].ch[k],X,Y);
if(d[k^1]<ans) query(t[x].ch[k^1],X,Y);
}
int main()
{
n=read(),m=read();tot=n;
for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();
rt=build(1,n,0);
int op,x,y;
while(m--){
op=read(),x=read(),y=read();
if(op==1) insert(rt,(node){x,y},0);
else ans=inf,query(rt,x,y),printf("%d\n",ans);
}
return 0;
}
\(CDQ\) 分治解法：
我们做 \(4\) 次 \(CDQ\) 分治，每次只计算左下角的点，将问题转换成在树状数组上查最小。
\(Code\ Below:\)
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=500000+10;
const int maxm=1000000+10;
const int inf=0x3f3f3f3f;
int n,m,X,Y,c[maxm],ans[maxn],cnt,tot;
struct Query{
int op,x,y,id;
}p[maxn<<1],q[maxn<<1],t[maxn<<1];
namespace IO{
#define gc() (iS==iT?(iT=(iS=ibuff)+fread(ibuff,1,SIZ,stdin),(iS==iT?EOF:*iS++)):*iS++)
const int SIZ=1<<21|1;
char *iS,*iT,ibuff[SIZ],obuff[SIZ],*oS=obuff,*oT=oS+SIZ-1,fu[110],c;int fr;
inline void out(){
fwrite(obuff,1,oS-obuff,stdout);
oS=obuff;
}
template <class T>
inline void read(T &x){
x=0;T y=1;
for(c=gc();(c>'9'||c<'0')&&c!='-';c=gc());
c=='-'?y=-1:x=(c&15);
for(c=gc();c>='0'&&c<='9';c=gc()) x=x*10+(c&15);
x*=y;
}
template <class T>
inline void print(T x,char text='\n'){
if(x<0) *oS++='-',x*=-1;
if(x==0) *oS++='0';
while(x) fu[++fr]=x%10+'0',x/=10;
while(fr) *oS++=fu[fr--];
*oS++=text;out();
}
}
inline void update(int x,int y){
for(;x<=Y;x+=lowbit(x)) c[x]=max(c[x],y);
}
inline int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans=max(ans,c[x]);
return ans;
}
inline void clear(int x){
for(;x<=Y;x+=lowbit(x)){
if(c[x]) c[x]=0;
else break;
}
}
void CDQ(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
CDQ(l,mid);CDQ(mid+1,r);
int u=l,v=mid+1,j=l,tmp;
for(int i=mid+1;i<=r;i++)
if(q[i].op==2){
for(;j<=mid&&q[j].x<=q[i].x;j++)
if(q[j].op==1) update(q[j].y,q[j].x+q[j].y);
tmp=query(q[i].y);
if(tmp) ans[q[i].id]=min(ans[q[i].id],q[i].x+q[i].y-tmp);
}
for(int i=l;i<j;i++)
if(q[i].op==1) clear(q[i].y);
j=l;
while(u<=mid&&v<=r){
if(q[u].x<=q[v].x) t[j++]=q[u++];
else t[j++]=q[v++];
}
while(u<=mid) t[j++]=q[u++];
while(v<=r) t[j++]=q[v++];
for(int i=l;i<=r;i++) q[i]=t[i];
}
void del(){
int X=0,Y=0,cnt=0;
for(int i=1;i<=tot;i++)
if(q[i].op==2) X=max(X,q[i].x),Y=max(Y,q[i].y);
for(int i=1;i<=tot;i++)
if(q[i].x<=X&&q[i].y<=Y) q[++cnt]=q[i];
CDQ(1,cnt);
}
int main()
{
IO::read(n),IO::read(m);
int op,x,y;
for(int i=1;i<=n;i++){
IO::read(x),IO::read(y);
x++;y++;
p[++tot]=(Query){1,x,y,0};
X=max(X,x);Y=max(Y,y);
}
for(int i=1;i<=m;i++){
IO::read(op),IO::read(x),IO::read(y);
x++;y++;
if(op==1) p[++tot]=(Query){1,x,y,0};
else p[++tot]=(Query){2,x,y,++cnt};
X=max(X,x);Y=max(Y,y);
}
X++;Y++;
for(int i=1;i<=cnt;i++) ans[i]=inf;
for(int i=1;i<=tot;i++) q[i]=p[i];
del();
for(int i=1;i<=tot;i++) q[i]=p[i],q[i].x=X-p[i].x;
del();
for(int i=1;i<=tot;i++) q[i]=p[i],q[i].y=Y-p[i].y;
del();
for(int i=1;i<=tot;i++) q[i]=p[i],q[i].x=X-p[i].x,q[i].y=Y-p[i].y;
del();
for(int i=1;i<=cnt;i++) IO::print(ans[i]);
return 0;
}
2、[CQOI2016]K远点对
我们用一个小根堆来计算第 \(k\) 小。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
int n,k,D,rt,cnt;
priority_queue<ll,vector<ll>,greater<ll> > pq;
struct node{
int d[2];
}a[maxn];
struct KD_Tree{
int d[2],Max[2],Min[2],ch[2],siz;
inline void init(){
d[0]=d[1]=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=siz=0;
}
inline void get(node a){
Max[0]=Min[0]=d[0]=a.d[0];
Max[1]=Min[1]=d[1]=a.d[1];
}
}t[maxn];
inline bool operator < (const node &a,const node &b){
return a.d[D]<b.d[D];
}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void update(int x,int y){
t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);
t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);
t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);
t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x){
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
if(t[x].ch[0]) update(x,t[x].ch[0]);
if(t[x].ch[1]) update(x,t[x].ch[1]);
}
int build(int l,int r,int now){
int mid=(l+r)>>1,x=++cnt;D=now;
nth_element(a+l,a+mid,a+r+1);
t[x].get(a[mid]);
if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);
if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);
pushup(x);return x;
}
inline ll dis(int x,int X,int Y){
return max(1ll*(t[x].Min[0]-X)*(t[x].Min[0]-X),1ll*(t[x].Max[0]-X)*(t[x].Max[0]-X))
+max(1ll*(t[x].Min[1]-Y)*(t[x].Min[1]-Y),1ll*(t[x].Max[1]-Y)*(t[x].Max[1]-Y));
}
inline ll dist(int x,int X,int Y){
return 1ll*(t[x].d[0]-X)*(t[x].d[0]-X)+1ll*(t[x].d[1]-Y)*(t[x].d[1]-Y);
}
void query(int x,int X,int Y){
ll L=dist(x,X,Y),d[2];int k;
d[0]=t[x].ch[0]?dis(t[x].ch[0],X,Y):-inf;
d[1]=t[x].ch[1]?dis(t[x].ch[1],X,Y):-inf;
if(L>pq.top()) pq.pop(),pq.push(L);
k=d[1]>d[0];
if(d[k]>pq.top()) query(t[x].ch[k],X,Y);
if(d[k^1]>pq.top()) query(t[x].ch[k^1],X,Y);
}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();
rt=build(1,n,0);
for(int i=1;i<=k*2;i++) pq.push(0ll);
for(int i=1;i<=n;i++) query(rt,a[i].d[0],a[i].d[1]);
printf("%lld\n",pq.top());
return 0;
}
3、[国家集训队]JZPFAR
我们在 \(K\) 远点对的基础上再记一个 \(minid\)，一样暴力查询。
\(Code\ Below:\)
#include <bits/stdc++.h>
#define ll long long
#define pli pair<ll,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
int n,m,D,rt,cnt;
priority_queue<pli,vector<pli>,greater<pli> > pq;
struct node{
int d[2],id;
}a[maxn];
struct KD_Tree{
int d[2],id,ID,Max[2],Min[2],ch[2],siz;
inline void init(){
d[0]=d[1]=id=ID=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=siz=0;
}
inline void get(node a){
Max[0]=Min[0]=d[0]=a.d[0];
Max[1]=Min[1]=d[1]=a.d[1];
id=ID=a.id;
}
}t[maxn];
inline bool operator < (const node &a,const node &b){
return (a.d[D]!=b.d[D])?a.d[D]<b.d[D]:a.id>b.id;
}
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void update(int x,int y){
t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);
t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);
t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);
t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x){
t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
t[x].ID=min(t[x].ID,min(t[t[x].ch[0]].ID,t[t[x].ch[1]].ID));
if(t[x].ch[0]) update(x,t[x].ch[0]);
if(t[x].ch[1]) update(x,t[x].ch[1]);
}
int build(int l,int r,int now){
int mid=(l+r)>>1,x=++cnt;D=now;
nth_element(a+l,a+mid,a+r+1);
t[x].get(a[mid]);
if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);
if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);
pushup(x);return x;
}
inline ll dis(int x,int X,int Y){
return max(1ll*(t[x].Min[0]-X)*(t[x].Min[0]-X),1ll*(t[x].Max[0]-X)*(t[x].Max[0]-X))
+max(1ll*(t[x].Min[1]-Y)*(t[x].Min[1]-Y),1ll*(t[x].Max[1]-Y)*(t[x].Max[1]-Y));
}
inline ll dist(int x,int X,int Y){
return 1ll*(t[x].d[0]-X)*(t[x].d[0]-X)+1ll*(t[x].d[1]-Y)*(t[x].d[1]-Y);
}
void query(int x,int X,int Y){
ll L=dist(x,X,Y),d[2];int k;
d[0]=t[x].ch[0]?dis(t[x].ch[0],X,Y):-inf;
d[1]=t[x].ch[1]?dis(t[x].ch[1],X,Y):-inf;
if((L>pq.top().F)||(L==pq.top().F&&t[x].id<-pq.top().S)) pq.pop(),pq.push(mp(L,-t[x].id));
k=d[1]>d[0];
if((d[k]>pq.top().F)||(d[k]==pq.top().F&&t[t[x].ch[k]].ID<-pq.top().S)) query(t[x].ch[k],X,Y);
if((d[k^1]>pq.top().F)||(d[k^1]==pq.top().F&&t[t[x].ch[k^1]].ID<-pq.top().S)) query(t[x].ch[k^1],X,Y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read(),a[i].id=i;
rt=build(1,n,0);
m=read();
int x,y,k;
while(m--){
x=read(),y=read(),k=read();
for(int i=1;i<=k;i++) pq.push(mp(0ll,-inf));
query(rt,x,y);
printf("%d\n",-pq.top().S);
while(!pq.empty()) pq.pop();
}
return 0;
}
4、[SDOI2010]捉迷藏
最远点对最近点对问题，经典 \(K-D\ Tree\) 问题。不过最近点对要除去自己。
\(Code\ Below:\)
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
int n,D,rt,ans=inf,ans1,ans2;
struct node{
int d[2];
}a[maxn];
inline bool operator < (const node &a,const node &b){
return a.d[D]<b.d[D];
}
struct KD_Tree{
int d[2],Max[2],Min[2],ch[2];
inline void init(){
d[0]=d[1]=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=0;
}
inline void get(node a){
Max[0]=Min[0]=d[0]=a.d[0];
Max[1]=Min[1]=d[1]=a.d[1];
}
}t[maxn];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void update(int x,int y){
t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);
t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);
t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);
t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x){
if(t[x].ch[0]) update(x,t[x].ch[0]);
if(t[x].ch[1]) update(x,t[x].ch[1]);
}
int build(int l,int r,int now){
int mid=(l+r)>>1,x=mid;D=now;
nth_element(a+l,a+mid,a+r+1);
t[x].init();t[x].get(a[mid]);
if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);
if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);
pushup(x);return x;
}
inline int maxdis(int x,int X,int Y){
return max(abs(t[x].Min[0]-X),abs(t[x].Max[0]-X))+max(abs(t[x].Min[1]-Y),abs(t[x].Max[1]-Y));
}
inline int mindis(int x,int X,int Y){
return max(t[x].Min[0]-X,0)+max(X-t[x].Max[0],0)+max(t[x].Min[1]-Y,0)+max(Y-t[x].Max[1],0);
}
inline int dis(int x,int X,int Y){
return abs(t[x].d[0]-X)+abs(t[x].d[1]-Y);
}
void query_max(int x,int X,int Y){
int L=dis(x,X,Y),d[2],k;
d[0]=t[x].ch[0]?maxdis(t[x].ch[0],X,Y):-inf;
d[1]=t[x].ch[1]?maxdis(t[x].ch[1],X,Y):-inf;
ans1=max(ans1,L);k=d[1]>d[0];
if(d[k]>ans1) query_max(t[x].ch[k],X,Y);
if(d[k^1]>ans1) query_max(t[x].ch[k^1],X,Y);
}
void query_min(int x,int X,int Y){
int L=dis(x,X,Y),d[2],k;
d[0]=t[x].ch[0]?mindis(t[x].ch[0],X,Y):inf;
d[1]=t[x].ch[1]?mindis(t[x].ch[1],X,Y):inf;
if(L) ans2=min(ans2,L);k=d[1]<d[0];
if(d[k]<ans2) query_min(t[x].ch[k],X,Y);
if(d[k^1]<ans2) query_min(t[x].ch[k^1],X,Y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();
rt=build(1,n,0);
for(int i=1;i<=n;i++){
ans1=0;ans2=inf;
query_max(rt,a[i].d[0],a[i].d[1]);
query_min(rt,a[i].d[0],a[i].d[1]);
ans=min(ans,ans1-ans2);
}
printf("%d\n",ans);
return 0;
}
5、Generating Synergy
带下传标记的 \(K-D\ Tree\)。修改的时候暴力修改，查询的时候要将其祖先的标记下传。
\(Code\ Below:\)
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
int n,D,rt,ans=inf,ans1,ans2;
struct node{
int d[2];
}a[maxn];
inline bool operator < (const node &a,const node &b){
return a.d[D]<b.d[D];
}
struct KD_Tree{
int d[2],Max[2],Min[2],ch[2];
inline void init(){
d[0]=d[1]=Max[0]=Max[1]=Min[0]=Min[1]=ch[0]=ch[1]=0;
}
inline void get(node a){
Max[0]=Min[0]=d[0]=a.d[0];
Max[1]=Min[1]=d[1]=a.d[1];
}
}t[maxn];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void update(int x,int y){
t[x].Max[0]=max(t[x].Max[0],t[y].Max[0]);
t[x].Max[1]=max(t[x].Max[1],t[y].Max[1]);
t[x].Min[0]=min(t[x].Min[0],t[y].Min[0]);
t[x].Min[1]=min(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x){
if(t[x].ch[0]) update(x,t[x].ch[0]);
if(t[x].ch[1]) update(x,t[x].ch[1]);
}
int build(int l,int r,int now){
int mid=(l+r)>>1,x=mid;D=now;
nth_element(a+l,a+mid,a+r+1);
t[x].init();t[x].get(a[mid]);
if(l<mid) t[x].ch[0]=build(l,mid-1,now^1);
if(mid<r) t[x].ch[1]=build(mid+1,r,now^1);
pushup(x);return x;
}
inline int maxdis(int x,int X,int Y){
return max(abs(t[x].Min[0]-X),abs(t[x].Max[0]-X))+max(abs(t[x].Min[1]-Y),abs(t[x].Max[1]-Y));
}
inline int mindis(int x,int X,int Y){
return max(t[x].Min[0]-X,0)+max(X-t[x].Max[0],0)+max(t[x].Min[1]-Y,0)+max(Y-t[x].Max[1],0);
}
inline int dis(int x,int X,int Y){
return abs(t[x].d[0]-X)+abs(t[x].d[1]-Y);
}
void query_max(int x,int X,int Y){
int L=dis(x,X,Y),d[2],k;
d[0]=t[x].ch[0]?maxdis(t[x].ch[0],X,Y):-inf;
d[1]=t[x].ch[1]?maxdis(t[x].ch[1],X,Y):-inf;
ans1=max(ans1,L);k=d[1]>d[0];
if(d[k]>ans1) query_max(t[x].ch[k],X,Y);
if(d[k^1]>ans1) query_max(t[x].ch[k^1],X,Y);
}
void query_min(int x,int X,int Y){
int L=dis(x,X,Y),d[2],k;
d[0]=t[x].ch[0]?mindis(t[x].ch[0],X,Y):inf;
d[1]=t[x].ch[1]?mindis(t[x].ch[1],X,Y):inf;
if(L) ans2=min(ans2,L);k=d[1]<d[0];
if(d[k]<ans2) query_min(t[x].ch[k],X,Y);
if(d[k^1]<ans2) query_min(t[x].ch[k^1],X,Y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();
rt=build(1,n,0);
for(int i=1;i<=n;i++){
ans1=0;ans2=inf;
query_max(rt,a[i].d[0],a[i].d[1]);
query_min(rt,a[i].d[0],a[i].d[1]);
ans=min(ans,ans1-ans2);
}
printf("%d\n",ans);
return 0;
}