坪山住房和建设局网站,买了一个域名如何做网站,wordpress注册不,网站是怎样制作的传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
线段树分治就是在线段树上进行遍历#xff0c;到每个点都加上它对子节点的贡献#xff0c;最后到叶子节点的时候算一下贡献。 对于这个题先考虑维护二分图的话#xff0c;可以用扩展域并…传送门
文章目录题意思路题意 思路
线段树分治就是在线段树上进行遍历到每个点都加上它对子节点的贡献最后到叶子节点的时候算一下贡献。 对于这个题先考虑维护二分图的话可以用扩展域并查集维护。 而对于每条边他有出现时间和消失时间我们按照时间来建一颗线段树让后可以将他出现的时间[l,r][l,r][l,r]在线段树上切分成lognlognlogn段对于每段都分别管理着不同的叶子节点。我们可以用vectorvectorvector存下来管理当前这颗子树的边让后把他们连上判断一下是否是二分图不是的话当前[l,r][l,r][l,r]时间段都不是二分图否则就继续遍历最后回溯的时候用可撤销并查集撤销一下就好了。 注意并查集不能路径压缩因为我们还要撤销。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includestack
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,k;
int p[N],se[N];
PII edge[N];
stackPIIs;
struct Node
{int l,r;vectorintv;
}tr[N2];void build(int u,int l,int r)
{tr[u]{l,r};if(lr) return;build(L,l,Mid); build(R,Mid1,r);
}void insert(int u,int l,int r,int id)
{if(tr[u].lltr[u].rr){tr[u].v.push_back(id);return;}if(lMid) insert(L,l,r,id);if(rMid) insert(R,l,r,id);
}int find(int x) { return xp[x]? x:find(p[x]); }void merge(int a,int b)
{if(ab) return;if(se[a]se[b]) swap(a,b);p[b]a; se[a]se[b];s.push({b,se[b]});
}void dfs(int u,int l,int r)
{int flag1,begs.size();for(int i0;itr[u].v.size();i){int idtr[u].v[i];int pafind(edge[id].X),pbfind(edge[id].Y);if(papb) { flag0; break; }merge(pa,find(edge[id].Yn)),merge(find(edge[id].Xn),pb);}if(flag){if(lr) puts(Yes);else dfs(L,l,Mid),dfs(R,Mid1,r);}else for(int il;ir;i) puts(No);while(s.size()beg) se[find(s.top().X)]-s.top().Y,p[s.top().X]s.top().X,s.pop();
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d%d,n,m,k);for(int i1;in*2;i) p[i]i,se[i]1;build(1,1,k);for(int i1;im;i){int x,y,l,r; scanf(%d%d%d%d,x,y,l,r);if(l!r) insert(1,l1,r,i);edge[i]{x,y};}dfs(1,1,k);return 0;
}
/**/
