LG P4899 [IOI2018] werewolf 狼人

Solution

我們發(fā)現(xiàn)$01$限制長這樣子：
$${?}_x(mi{n}_{i{d}_{s?>x}}\ge L\&ma{x}_{i{d}_{x?>e}}\le R)\to 1$$
因此我們只需要快速求出$x$沿著$\ge L$的編號能走到的點集和沿著$\le R$的編號能走到的點集的交即可。

然后上面的東西可以用$kruskal$重構樹維護。具體的，對于$mi{n}_{i{d}_{x?>x}}\ge L$的情況，我們把一條邊$(x,y)$的邊權設為$min(x,y)$，然后建$kruskal$重構樹，這樣$s$能走到的點集就是從重構樹上$s$開始跳到的最高的滿足$p$的點權$\ge L$祖先$p$的子樹中的所有葉子結點，因此它能走到的點集是在重構樹上的一棵子樹，也是重構樹的$dfs$序的一段區(qū)間$[x_1,x_2]$。

那么對于$ma{x}_{i{d}_{x?>e}}\le R$也求出一段區(qū)間$[y_1,y_2]$之后，問題就轉化為在第一棵樹上$dfn$為$[x_1,x_2]$在第二棵樹上$dfn$為$[y_1,y_2]$的點存不存在，直接二維數(shù)點即可。

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

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 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; } PR p[MAXN]; int n,m,q,Ans[MAXN]; struct Enode{ int u,v,c; } eg[MAXN]; struct Qnode{ int x,l,r,id; } Q[MAXN]; struct Binary_Index_Tree {int s[MAXN];void add(int x) { for (;x<=n;x+=x&(-x)) s[x]++; }int query(int x) { int ans=0; for (;x;x-=x&(-x)) ans+=s[x]; return ans; } } BIT; struct Kruskal_Tree {vector<int> e[MAXN];int num,DFN,f[MAXN],dfn[MAXN],fns[MAXN],dep[MAXN],fa[MAXN][20],Log[MAXN],a[MAXN];int find(int x) { return f[x]==x?f[x]:f[x]=find(f[x]); }void dfs(int x){dfn[x]=DFN+1,DFN+=(x<=n);for (int i=1;i<=Log[dep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];for (auto v:e[x]) fa[v][0]=x,dep[v]=dep[x]+1,dfs(v);fns[x]=DFN;}void build(){num=n,DFN=0;for (int i=1;i<=n+n;i++) f[i]=i,e[i].clear();sort(eg+1,eg+m+1,[&](Enode a,Enode b){ return a.c>b.c; });for (int i=1;i<=m;i++) {int u=find(eg[i].u),v=find(eg[i].v),c=eg[i].c;if (u==v) continue;a[++num]=c;f[num]=f[u]=f[v]=num;e[num].PB(u),e[num].PB(v);}Log[1]=0;for (int i=2;i<=num;i++) Log[i]=Log[i>>1]+1;dfs(num);}int jump(int x,int y){for (int i=Log[dep[x]];i>=0;i--)if (fa[x][i]&&a[fa[x][i]]>=y) x=fa[x][i];return x;}PR query(int x,int y){int z=jump(x,y);return MP(dfn[z],fns[z]);} } Ts,Te; VI check_validity(int N,VI X,VI Y,VI S,VI E,VI L,VI R) {n=N,m=X.size(),q=S.size();for (int i=1,u,v;i<=m;i++) u=X[i-1]+1,v=Y[i-1]+1,eg[i]=(Enode){u,v,min(u,v)};Ts.build();for (int i=1;i<=m;i++) eg[i].c=-max(eg[i].u,eg[i].v);Te.build();for (int i=1;i<=n;i++) p[i]=MP(Ts.dfn[i],Te.dfn[i]);for (int i=1;i<=q;i++){int s=S[i-1]+1,e=E[i-1]+1,l=L[i-1]+1,r=R[i-1]+1;PR x=Ts.query(s,l),y=Te.query(e,-r);Q[i]=(Qnode){x.fi-1,y.fi,y.se,-i};Q[i+q]=(Qnode){x.se,y.fi,y.se,i}; // cout<<"Query:"<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<endl;}sort(p+1,p+n+1,[&](PR a,PR b){ return a.fi<b.fi; });sort(Q+1,Q+q+q+1,[&](Qnode a,Qnode b){ return a.x<b.x; });for (int i=1,nw=0;i<=q+q;i++){while (nw<n&&p[nw+1].fi<=Q[i].x) BIT.add(p[++nw].se);int t=BIT.query(Q[i].r)-BIT.query(Q[i].l-1);if (Q[i].id>0) Ans[Q[i].id]+=t;if (Q[i].id<0) Ans[-Q[i].id]-=t;}VI A; A.clear();for (int i=1;i<=q;i++) A.PB(Ans[i]?1:0);return A; }

總結

以上是生活随笔為你收集整理的LG P4899 [IOI2018] werewolf 狼人(kruskal重构树，二维数点)的全部內容，希望文章能夠幫你解決所遇到的問題。

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