建设网站了还能消除吗,郴州网站建设案例,网站备案方法,05网补充答案全部关于什么是合理的实现 解析
本题把并查集写在了题面上 然而#xff0c;我却一直沉浸在一个及其通用的判断二分图的方法中#xff1a; 一个图是二分图的充要条件是它没有奇环 怎么维护这个玩意#xff1f;带权并查集#xff01; 怎么套线段树分治#xff1f;可持久化… 关于什么是合理的实现 解析
本题把并查集写在了题面上 然而我却一直沉浸在一个及其通用的判断二分图的方法中 一个图是二分图的充要条件是它没有奇环 怎么维护这个玩意带权并查集 怎么套线段树分治可持久化 就这样口胡完一个写起来几乎不可写的《正解》后我却没有勇气把它实现… 因为可持久化的带权并查集再套个线段树…这玩意一听就没200行写不来啊… 而且最关键的是本大聪明又动了动装着一片大海的脑瓜发现这个东西似乎是3log了… 然后…就恬不知耻的点进了题解 然后…看完题解…就无地自容的点了出来…
但U1S1这确实令人有些耳目一新
首先回归二分图的本质就是有连边的两点不能在同一集合 所以直接拿状态并查集就可以很轻松的维护了 这就已经把带权给去掉了 那怎么可持久化呢 不必使用恶心的要死的主席树可以直接维护一个栈存储并查集的合并操作在递归结束时撤销 为了方便撤销我们需要保留树的形态因此不能路径压缩 但是本来主席树实现的可持久化也不行啊 这样的复杂度就是一个log的 再加上线段树分治的log总复杂度nlogn2nlogn^2nlogn2
以后在一些需要撤销并查集操作的地方都可以借鉴这个思路 虽然 似乎是 做不了可持久化并查集但在绝大多数的时候都可以代替 不仅少个log代码也好写的多
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
const int N2e5100;
ll read() {ll x0,f1;char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {xx*10(c^48);cgetchar();}return x*f;
}int n,m,k;
int fa[N],siz[N];
int find(int x){return xfa[x]?x:find(fa[x]);
}
struct node{int x,y;
};
node zhan[N];
int top;
vectornodev[N2];
bool vis[N];
#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
void add(int k,int l,int r,int x,int y,node o){if(xlry){int xxo.x,yyo.y;//printf(xx%d yy%d\n,xx,yy);v[k].push_back((node){xxn,yy});v[k].push_back((node){xx,yyn});return;}if(xmid) add(ls,l,mid,x,y,o);if(ymid) add(rs,mid1,r,x,y,o);return;
}
int tp[N2];
#define oth(a) (an?a-n:an)
void give(int k,int l,int r){if(lr){vis[l]1;return;}give(ls,l,mid);give(rs,mid1,r);return;
}
void work(int k,int l,int r){//printf(k%d (%d %d)\n,k,l,r);tp[k]top;int flag0;for(int j0,ov[k].size();jo;j){int xv[k][j].x,yv[k][j].y;xfind(x);yfind(y);//printf( merge:x%d y%d\n,x,y);if(xoth(y)||yoth(x)){//printf( give!\n);give(k,l,r);flag1;break;}if(siz[x]siz[y]) swap(x,y);fa[x]y;siz[y]siz[x];zhan[top](node){x,y};}if(lr!flag){work(ls,l,mid);work(rs,mid1,r);}while(top!tp[k]){int xzhan[top].x,yzhan[top].y;top--;fa[x]x;siz[y]-siz[x];}return;
}
int main(){nread();mread();kread();for(int i1;i2*n;i){fa[i]i;siz[i]1;}for(int i1;im;i){int xread(),yread(),lread(),rread();l;add(1,1,k,l,r,(node){x,y});}work(1,1,k);for(int i1;ik;i){if(vis[i]) printf(No\n);else printf(Yes\n);}return 0;
}
/*
*/
