只会做水题力……qwq（搞错大小写，自裁请）

每条边存在的时间事一个区间，因此考虑线段树分治……首先当然要写一个可撤销并查集。

然后每个点维护他到父亲的边的边权膜2，合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了，因为LCA到根的部分会算两遍，对答案无影响。

代码：

/**************************************************************
    Problem: 4025
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9928 ms
    Memory:34840 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
const int maxn = 100005;
const int maxno = maxn << 2;
const int maxm = 200005;
int n, m, T;
 
int p[maxn], siz[maxn], d[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; siz[i] = 1; d[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
int get_d(int x) {
  if(p[x] == x) {
    return 0;
  } else {
    return (d[x] + get_d(p[x])) % 2;
  }
}
typedef std::pair<int, int> upd;
upd link_set(int x, int y, int v) {
  if(siz[x] > siz[y]) std::swap(x, y);
  p[x] = y; siz[y] += siz[x]; d[x] = v;
  return std::make_pair(x, y);
}
upd merge_set(int x, int y) {
  int v = (get_d(x) + get_d(y) + 1) % 2;
  return link_set(get_fa(x), get_fa(y), v);
}
void unlink_set(const upd &pr) {
  int x = pr.first, y = pr.second;
  p[x] = x; siz[y] -= siz[x]; d[x] = 0;
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
std::vector<upd> event[maxno];
std::stack<std::pair<int, upd> > S;
void update(int o, int L, int R, int ql, int qr, upd v) {
  if(ql <= L && R <= qr) {
    event[o].push_back(v);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
  }
}
int val[maxno];
void solve(int o, int L, int R) {
  for(int i = 0; i < event[o].size(); i ++) {
    const upd &pr = event[o][i];
    int x = pr.first, y = pr.second;
    if(is_same(x, y)) {
      if((get_d(x) + get_d(y)) % 2 == 0) {
        val[o] = 0;
        break;
      }
    } else {
      S.push(std::make_pair(o, merge_set(x, y)));
    }
  }
  if(L == R) {
    if(val[o] != 0) val[o] = 1;
  } else {
    if(val[o] != 0) {
      int M = (L + R) / 2;
      solve(o << 1, L, M);
      solve(o << 1 | 1, M + 1, R);
    }
  }
  while((!S.empty()) && S.top().first >= o) {
    upd v = S.top().second; S.pop();
    unlink_set(v);
  }
}
void print(int o, int L, int R) {
  if(L == R) {
    if(val[o]) {
      puts("Yes");
    } else {
      puts("No");
    }
  } else {
    if(val[o] != -1) {
      val[o << 1] = val[o];
      val[o << 1 | 1] = val[o];
    }
    int M = (L + R) / 2;
    print(o << 1, L, M);
    print(o << 1 | 1, M + 1, R);
  }
}
 
int main() {
  memset(val, -1, sizeof(val));
  scanf("%d%d%d", &n, &m, &T);
  for(int i = 1; i <= m; i ++) {
    int u, v, s, t; scanf("%d%d%d%d", &u, &v, &s, &t);
    s ++; if(s <= t) update(1, 1, T, s, t, std::make_pair(u, v));
  }
  init_dsu(); solve(1, 1, T); print(1, 1, T);
  return 0;
}

• 相关文章
• 全局相关文章