[APIO2018] New Home 新家

Solution

對于時間軸我們直接離散化+掃描線，維護每一個商店的加入和刪除。

對于詢問$(x,t)$，不好直接回答，這里的關鍵一步是：我們要求的是$k$種商店最小距離的最大值，于是考慮二分答案。二分一個最大值$mid$，那么$k$種商店必須都在$[x?mid,x+mid]$出現過。我們考慮對于每一個商店維護和它類型相同的商店的前驅。那么$[x?mid,x+mid]$的條件就轉化為了$(x+mid,\infty )$中的商店的前驅都不小于$x?mid$（注意$?1$的特殊情況）。

于是我們用一個$set$維護每種商店的序列，用線段樹維護后綴最小值即可。

時間復雜度$O(nlgn?lgT)$。

Details

具體實現時有一些細節：

• 我們把每一種商店的第一個的前驅設為$0$。
• 每種商店的最后加一個$\infty$以簡化$?1$的特判，具體可見代碼。
• 可能會出現類型坐標時間都相同的商店，因此我們要在線段樹每個位置維護一個$multiset$表示該坐標的最小值，而不能直接修改一個坐標的最小值。維護每個類型的$set$也要是$multiset$
• 因為怕麻煩，我直接用的是動態開點線段樹，跑得也挺輕松的。

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int MX=1e8+300000; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } multiset<int> V[MAXN],Set[MAXN]; int nodenum=1,mn[MAXN*30],ls[MAXN*30],rs[MAXN*30],Ans[MAXN],id[MAXN*30],ID=0; struct Cnode{ int t,x,y; } C[MAXN<<1],Q[MAXN]; void up(int x) {mn[x]=INF;if (ls[x]) upmin(mn[x],mn[ls[x]]);if (rs[x]) upmin(mn[x],mn[rs[x]]); } int query(int x,int l,int r,int L,int R) {if (!x) return INF;if (l>=L&&r<=R) return mn[x];int mid=(l+r)>>1;if (R<=mid) return query(ls[x],l,mid,L,R);else if (L>mid) return query(rs[x],mid+1,r,L,R);else return min(query(ls[x],l,mid,L,mid),query(rs[x],mid+1,r,mid+1,R)); } int update(int x,int l,int r,int y,int z) {if (!x) x=++nodenum;if (l==r) { id[x]=(id[x]?id[x]:++ID),V[id[x]].insert(z),mn[x]=*V[id[x]].begin(); return x; }int mid=(l+r)>>1;if (y<=mid) ls[x]=update(ls[x],l,mid,y,z);else rs[x]=update(rs[x],mid+1,r,y,z);up(x);return x; } void clear(int x,int l,int r,int y,int z) {if (l==r) { V[id[x]].erase(V[id[x]].find(z)); mn[x]=(V[id[x]].size()?*V[id[x]].begin():INF); return; }int mid=(l+r)>>1;if (y<=mid) clear(ls[x],l,mid,y,z);else clear(rs[x],mid+1,r,y,z);up(x); }int check(int x,int l) { return query(1,1,MX,min(x,(int)1e8+1),MX)>=max(l,1); } signed main() {int n=read(),k=read(),q=read(),num=0;for (int i=1;i<=n;i++){int x=read(),y=read(),a=read(),b=read();C[++num]=(Cnode){a,x,y},C[++num]=(Cnode){b+1,x,-y};}for (int i=1,x,y;i<=q;i++) x=read(),y=read(),Q[i]=(Cnode){y,x,i};sort(C+1,C+num+1,[&](Cnode a,Cnode b){ return (a.t<b.t)||(a.t==b.t&&a.x>b.x); });sort(Q+1,Q+q+1,[&](Cnode a,Cnode b){ return a.t<b.t; });for (int i=1;i<=k;i++) Set[i].insert(1e8+i),update(1,1,MX,1e8+i,0);C[num+1].t=INF;int nw=1;while (nw<=q&&Q[nw].t<C[1].t) Ans[Q[nw].y]=-1,nw++;for (int i=1;i<=num;i++){if (C[i].y>0){int t=C[i].y;Set[t].insert(C[i].x);multiset<int>::iterator it=Set[t].find(C[i].x),pre=it,nxt=it;update(1,1,MX,*(++nxt),*it);if (pre!=Set[t].begin()) update(1,1,MX,*it,*(--pre)),clear(1,1,MX,*(nxt),*pre);else update(1,1,MX,*it,0),clear(1,1,MX,*nxt,0);}else if (C[i].y<0){int t=-C[i].y;multiset<int>::iterator it=Set[t].find(C[i].x),pre=it,nxt=it;clear(1,1,MX,*(++nxt),*it);if (pre!=Set[t].begin()) clear(1,1,MX,*it,*(--pre)),update(1,1,MX,*nxt,*pre);else clear(1,1,MX,*it,0),update(1,1,MX,*nxt,0);Set[t].erase(it);}while (nw<=q&&Q[nw].t<C[i+1].t){int t=Q[nw].x,l=0,r=1e8;while (l<r){int mid=(l+r)>>1;if (check(t+mid+1,t-mid)) r=mid;else l=mid+1;}Ans[Q[nw].y]=(!check(t+r+1,t-r)?-1:r);nw++;}}for (int i=1;i<=q;i++) printf("%d\n",Ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的[APIO2018] New Home 新家(线段树，二分答案，离散化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。