题意:
题解:
离线求出每条边出现的时间,然后像标记持久化一样放到线段树里面,然后遍历整个线段树,进入一个节点就把它里面所有的边的端点用并查集合起来,离开就撤销这些操作。
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, T;
struct pnt
{
pnt *f, *s[2];
int sz, x, mn;
bool rev;
pnt(int _x = 0)
{
f = s[0] = s[1] = NULL;
rev = 0;
mn = _x > n ? _x - n : -1;
sz = (~mn) ? 1 : 0;
x = _x;
}
}p[300010];
struct edge
{
int x, y, st, ed;
}e[200010];
vector<int>st[100010], ed[100010];
bool in[200010], on[200010];
int sum = 0;
bool is_root(pnt *x)
{
return x->f == 0 || x->f->s[0] != x && x->f->s[1] != x;
}
void pushup(pnt *x)
{
x->sz = x->x > n;
x->mn = x->x > n ? x->x - n: -1;
if (x->s[0])
{
x->sz += x->s[0]->sz;
if (x->s[0]->mn != -1 && (x->mn == -1 || e[x->s[0]->mn].ed < e[x->mn].ed))
x->mn = x->s[0]->mn;
}
if (x->s[1])
{
x->sz += x->s[1]->sz;
if (x->s[1]->mn != -1 && (x->mn == -1 || e[x->s[1]->mn].ed < e[x->mn].ed))
x->mn = x->s[1]->mn;
}
}
void pushdown(pnt *x)
{
if (x->rev)
{
if (x->s[0])
{
x->s[0]->rev ^= 1;
swap(x->s[0]->s[0], x->s[0]->s[1]);
}
if (x->s[1])
{
x->s[1]->rev ^= 1;
swap(x->s[1]->s[0], x->s[1]->s[1]);
}
x->rev = 0;
}
}
void rot(pnt *x)
{
pnt *f = x->f, *ff = f->f, *R, *r;
int w = x == f->s[0];
R = f;
r = x->s[w];
R->s[1 - w] = r;
if (r)
r->f = R;
R = ff;
r = x;
if (!is_root(f))
R->s[f == ff->s[1]] = r;
r->f = R;
R = x;
r = f;
R->s[w] = r;
r->f = R;
pushup(f);
pushup(x);
}
void splay(pnt *x)
{
pnt *hh = x;
static stack<pnt*>sta;
while (!is_root(hh))
{
sta.push(hh);
hh = hh->f;
}
sta.push(hh);
while (!sta.empty())
{
pushdown(sta.top());
sta.pop();
}
while (!is_root(x))
{
pnt *f = x->f, *ff = f->f;
if (is_root(f))
{
rot(x);
}
else if((x == f->s[0]) == (f == ff->s[0]))
{
rot(f);
rot(x);
}
else
{
rot(x);
rot(x);
}
}
}
void access(pnt *x)
{
pnt *last = NULL;
while (x)
{
splay(x);
x->s[1] = last;
pushup(x);
last = x;
x = x->f;
}
}
void make_root(pnt *x)
{
access(x);
splay(x);
x->rev ^= 1;
swap(x->s[0], x->s[1]);
}
void split(pnt *x, pnt *y)
{
make_root(x);
access(y);
splay(y);
}
void link(pnt *x, pnt *y)
{
make_root(x);
x->f = y;
}
void cut(pnt *x, pnt *y)
{
split(x, y);
y->s[0] = x->f = 0;
}
pnt *get_root(pnt *x)
{
access(x);
splay(x);
while (x->s[0])
{
pushdown(x);
x = x->s[0];
}
return x;
}
void ins(int x)
{
if (e[x].x == e[x].y)
{
in[x] = 1;
sum++;
return;
}
pnt *px = e[x].x + p, *py = e[x].y + p;
if (get_root(px) != get_root(py))
{
on[x] = 1;
link(px, p + x + n);
link(py, p + x + n);
}
else
{
split(px, py);
int mn = py->mn;
if (e[mn].ed >= e[x].ed)
{
if (py->sz & 1 ^ 1)
{
in[x] = 1;
sum++;
}
}
else
{
if (py->sz & 1 ^ 1)
{
in[mn] = 1;
sum++;
}
cut(p + e[mn].x, p + mn + n);
cut(p + e[mn].y, p + mn + n);
link(px, p + x + n);
link(py, p + x + n);
on[mn] = 0;
on[x] = 1;
}
}
}
void del(int x)
{
if (in[x])
{
in[x] = 0;
sum--;
}
else if(on[x])
{
cut(p + e[x].x, p + x + n);
cut(p + e[x].y, p + x + n);
}
}
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 1; i <= n + m; i++)
new(p + i) pnt(i);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].st, &e[i].ed);
st[e[i].st].push_back(i);
ed[e[i].ed].push_back(i);
}
for (int i = 0; i < T; i++)
{
int sz = ed[i].size();
for (int j = 0; j < sz; j++)
del(ed[i][j]);
sz = st[i].size();
for (int j = 0; j < sz; j++)
ins(st[i][j]);
puts(sum ? "No" : "Yes");
}
}