洛谷评价紫色cf约2600题目抽象成代数是给定若干xi,yi,ti,对于每个询问ai,bi,求|ai-xi||bi-yi|ti的最小值绝对值问题的经典解法之一是拆括号分4类讨论//p1:aixi,biyi xiyiti -ai-bi//p2:aixi,biyi xi-yiti -aibi//p3:aixi,biyi -xi-yiti aibi//p4:aixi,biyi -xiyiti ai-bi拆点一个显而易见的好处是可以让每个询问给出的变量分到一起也就是说每次的答案仅取决于本次给出的值和满足当前条件的点对的最小值所以现在我们的问题就变成了4个小问题L1在aixi,biyi的情况下xiyiti的最小值是多少L2,3,4同上这其实是一个非常经典的二维偏序问题求同时满足两维条件限制情况下的极值如果你会树套树应该脑子里已经有解出这道题的方法了但因为代码量过大我忘了那玩意咋写所以我们考虑用扫描线完成第一维的排序具体的我们将所有的弹弓和询问全部放到名为point的数组中标记它们的属性对于xiai,从左到右扫描遇到弹弓就将它 的右端点位置的xiyiti也就是我们当前维护的点对极值更新表示这个位置的y存在这样一个解这个更新就是线段树的单点修改如此我们能够保证跟新的每一个点x合法然后对于询问分别考虑y的合法区间yb or yb),在此区间查询即可所以在本题扫描线的用处就是保证随着点的添加x的值一定合法这能够在二维偏序问题中帮助我们解决掉一维剩下的一维用数据结构非常好维护本题的思路有点类似P4269 [USACO18FEB] Snow Boots G - 洛谷 (luogu.com.cn)这里顺便附上该题的ac代码#includebits/stdc.h #define int long long #define inf 0x3f3f3f3f3f3f3f #define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define cnot coutNO\n #define cyes coutYES\n #define cans coutans\n #define pb push_back #define x0 first #define y0 second #define lc p1 #define rc p1|1 #define mem(a,b) memset(a,b,sizeof(a)) #define sp(x) fixedsetprecision(x) #define all(v) v.begin(),v.end() #define fr(i,st,ed) for(int ist;ied;i) #define ffr(i,st,ed,dt) for(int ist;ied;idt) using namespace std; typedef pairint,stringPis; typedef pairint,intPii; const int N2e410,mod998244353,M1e610; int lowbit(int x){ return x(-x);} struct Node1{ int dep,step,id,op; }; struct Node2{ int max0,left0,right0; }; vectorinta; vectorNode1vec; vectorNode2arr; vectorintans; bool cmp(Node1 a,Node1 b){ if(a.depb.dep) return a.stepb.step; return a.depb.dep; } void up(int p,int ls,int rs){ arr[p].max0max({arr[p1].max0,arr[p1|1].max0,arr[p1].right0arr[p1|1].left0}); arr[p].left0(arr[p1].left0ls?arr[p1].right0arr[p1|1].left0:arr[p1].left0); arr[p].right0(arr[p1|1].right0rs?arr[p1|1].left0arr[p1].right0:arr[p1|1].right0); } void build(int p,int l,int r){ if(lr){ arr[p].max0(a[l]0?1:0); arr[p].left0(a[l]0?1:0); arr[p].right0(a[l]0?1:0); return; } int mid(lr)1; build(p1,l,mid); build(p1|1,mid1,r); up(p,mid-l1,r-mid); } void upd(int p,int l,int r,int pos){ if(lr){ arr[p].max00; arr[p].left00; arr[p].right00; return; } int mid(lr)1; if(posmid)upd(p1,l,mid,pos); if(posmid)upd(p1|1,mid1,r,pos); up(p,mid-l1,r-mid); } int que(){ return arr[1].max0; } void solve(){ int n,b; cinnb; arr.resize((n2)10); a.resize(n1,0); ans.resize(n1,0); fr(i,1,n){ int d; cind; vec.pb({d,0,i,0}); } fr(i,1,b){ int d,sp; cindsp; vec.pb({d,sp,i,1}); } sort(all(vec),cmp); build(1,1,n); int mvec.size(); for(Node1 e:vec){ if(e.op0){ a[e.id]1; upd(1,1,n,e.id); } else{ ans[e.id](que()e.step?1:0); } } fr(i,1,b){ coutans[i]\n; } } signed main(){ GG; int _t1; //cin_t; while(_t--){ solve(); } }只不过本题需要4种情况分类讨论涉及线段树的重置以及数据范围层面在建树的时候需要先将点离散化所以难度由蓝提升到了紫下面是本题的ac Code#includebits/stdc.h #define int long long #define inf 0x3f3f3f3f3f3f3f #define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define cnot coutNO\n #define cyes coutYES\n #define cans coutans\n #define pb push_back #define x0 first #define y0 second #define lc p1 #define rc p1|1 #define mem(a,b) memset(a,b,sizeof(a)) #define sp(x) fixedsetprecision(x) #define all(v) v.begin(),v.end() #define fr(i,st,ed) for(int ist;ied;i) #define ffr(i,st,ed,dt) for(int ist;ied;idt) using namespace std; typedef pairint,stringPis; typedef pairint,intPii; typedef pairstring,stringPss; const int N2e410,mod1e97,M1e610; int lowbit(int x){ return x(-x);} int n,m; struct Node{ int minx; }; vectorNodetree; int num; void init(){ fr(i,1,num2){ tree[i].minxinf; } } void up(int p){ tree[p].minxmin(tree[p1].minx,tree[p1|1].minx); } void upd(int p,int l,int r,int idx,int val){ if(lr){ tree[p].minxmin(tree[p].minx,val); return; } int mid(lr)1; if(idxmid)upd(p1,l,mid,idx,val); if(idxmid)upd(p1|1,mid1,r,idx,val); up(p); } int que(int p,int l,int r,int nl,int nr){ int minninf; if(lnlrnr){ return tree[p].minx; } int mid(lr)1; if(nlmid)minnmin(minn,que(p1,l,mid,nl,nr)); if(nrmid)minnmin(minn,que(p1|1,mid1,r,nl,nr)); return minn; } struct Point{ int x,y,t,op,id;//id0tp,id1que }; bool cmp(Point a,Point b){ return a.xb.x?a.yb.y:a.xb.x; } void solve(){ cinnm; vectorPointpoint; vectorintans(m1); int xi,yi,ti; vectorintvec; fr(i,1,n){ cinxiyiti; point.pb({xi,yi,ti,0,0}); vec.pb(xi); vec.pb(yi); } fr(i,1,m){ cinxiyi; ans[i]abs(yi-xi); point.pb({xi,yi,0,1,i}); vec.pb(xi); vec.pb(yi); } sort(all(point),cmp); int sizpoint.size(); sort(all(vec)); vec.erase(unique(all(vec)),vec.end()); numvec.size(); fr(i,0,siz-1){ point[i].xlower_bound(all(vec),point[i].x)-vec.begin()1; point[i].ylower_bound(all(vec),point[i].y)-vec.begin()1; } tree.resize((num2)5); init(); //|ai-xi||bi-yi|ti //p1:aixi,biyi xiyiti -ai-bi for(int isiz-1;i0;i--){ if(point[i].op0){ upd(1,1,num,point[i].y,vec[point[i].x-1]vec[point[i].y-1]point[i].t); } else{ ans[point[i].id]min(ans[point[i].id],que(1,1,num,point[i].y,num)-vec[point[i].x-1]-vec[point[i].y-1]); } } //p2:aixi,biyi xi-yiti -aibi init(); for(int isiz-1;i0;i--){ if(point[i].op0){ upd(1,1,num,point[i].y,vec[point[i].x-1]-vec[point[i].y-1]point[i].t); } else{ ans[point[i].id]min(ans[point[i].id],que(1,1,num,1,point[i].y)-vec[point[i].x-1]vec[point[i].y-1]); } } init(); //p3:aixi,biyi -xi-yiti aibi fr(i,0,siz-1){ if(point[i].op0){ upd(1,1,num,point[i].y,-vec[point[i].x-1]-vec[point[i].y-1]point[i].t); } else{ ans[point[i].id]min(ans[point[i].id],que(1,1,num,1,point[i].y)vec[point[i].x-1]vec[point[i].y-1]); } } init(); //p4:aixi,biyi -xiyiti ai-bi fr(i,0,siz-1){ if(point[i].op0){ upd(1,1,num,point[i].y,-vec[point[i].x-1]vec[point[i].y-1]point[i].t); } else{ ans[point[i].id]min(ans[point[i].id],que(1,1,num,point[i].y,num)vec[point[i].x-1]-vec[point[i].y-1]); } } fr(i,1,m){ coutans[i]\n; } } signed main(){ GG; int _t1; //cin_t; while(_t--){ solve(); } }