BZOJ4025 二分图 线段树分治、带权并查集
2024-10-11 00:22:44
如果边不会消失,那么显然可以带权并查集做(然后发现自己不会写带权并查集)
但是每条边有消失时间。这样每一条边产生贡献的时间对应一段区间,故对时间轴建立线段树,将每一条边扔到线段树对应的点上。
然后遍历整棵线段树,每遍历到一个点将覆盖这个点对应区间的边全部加入带权并查集中,递归到叶子节点输出答案。回溯的时候把在这一个点加入的边从并查集中栈序撤销。
因为需要撤销所以并查集不能使用路径压缩,只能按秩合并。
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
const int MAXN = 1e5 + 7;
int N , M , T;
#define PII pair < int , int >
#define st first
#define nd second
#define mid ((l + r) >> 1)
#define lch (x << 1)
#define rch (x << 1 | 1)
vector < PII > Edge[MAXN << 2];
void addEd(int x , int l , int r , int L , int R , PII Ed){
if(l >= L && r <= R){
Edge[x].push_back(Ed);
return;
}
if(mid >= L) addEd(lch , l , mid , L , R , Ed);
if(mid < R) addEd(rch , mid + 1 , r , L , R , Ed);
}
struct node{
int fa , val , sz;
}dsu[MAXN];
PII find(int x){
if(dsu[x].fa == x) return PII(x , 0);
PII t = find(dsu[x].fa);
return PII(t.st , t.nd ^ dsu[x].val);
}
void solve(int x , int l , int r , bool f){
stack < int > stk;
for(vector < PII > :: iterator t = Edge[x].begin() ; t != Edge[x].end() ; ++t){
int p = (*t).st , q = (*t).nd;
PII M = find(p) , N = find(q);
int m = M.st , n = N.st;
if(m != n){
if(dsu[m].sz > dsu[n].sz)
swap(n , m);
dsu[n].sz += dsu[m].sz;
dsu[m].fa = n;
dsu[m].val = M.nd ^ N.nd ^ 1;
stk.push(m);
}
else
f &= (M.nd ^ N.nd);
}
if(l == r)
puts(f ? "Yes" : "No");
else{
solve(lch , l , mid , f);
solve(rch , mid + 1 , r , f);
}
while(!stk.empty()){
int t = stk.top(); stk.pop();
dsu[dsu[t].fa].sz -= dsu[t].sz;
dsu[t].val = 0; dsu[t].fa = t;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
N = read(); M = read(); T = read();
for(int i = 1 ; i <= M ; ++i){
int a = read() , b = read() , l = read() , r = read();
if(l < r)
addEd(1 , 1 , T , l + 1 , r , PII(a , b));
}
for(int i = 1 ; i <= N ; ++i){
dsu[i].fa = i;
dsu[i].sz = 1;
}
solve(1 , 1 , T , 1);
return 0;
}
最新文章
- Ruby多行字符串,begin/end语句、注释
- bootstrap制作搜索框及添加回车搜索事件
- G++ 参数介绍(转载)
- ( 转 ) Android自绘字体大小paint.settextsize随分辨率大小变化
- $headers = $this->;input->;request_headers();返回请求头(header)数组
- Oracle逻辑体系:数据文件黑盒的内在洞天
- Warning: Name is nonexistent or not a directory
- IPMITOOL常用操作指令
- 【算法】螺旋方阵 上交OJ1021
- react~props和state的介绍与使用
- JQuery未来元素事件监听写法
- java 八种基本数据类型
- JAVA中方法和变量在继承中的覆盖和隐藏
- myeclipse的web项目导入到eclipse中
- finecms指定从第几篇文章开始调用5条记录,并调用文章所在栏目
- 结合以太通道的VLAN配置
- SpringMVC由浅入深day01_4DispatcherSerlvet.properties
- 记录一次读取memcache缓存的优化
- Zabbix学习之路(二)之添加主机监控及自定义item监控
- php替换 json符号