danihao123's Blog

一张\(n\)个点的图，初始没边，然后要求你支持以下操作：

• 给定\((x, y)\)，在\(x\)和\(y\)两点间添加一条长度为\(i\)的边（假设这是第\(i\)次操作）。
• 给定\(k\)，删除当前图中边权最大的\(k\)条边。
• 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作，每次操作后输出当前图最小生成树的边权和（不存在的话输出\(0\)）。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

只会做水题力……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;
}

LCT+扫描线应该随便做吧这题……但我学了一下线段树分治

这个问题有删除非常的恶心，让我们考虑怎么去掉删除的影响。

每条边存在的时间段是一个区间，而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标，对所有询问建线段树，然后对一段区间加边就是一个区间打标记，最后扫一遍线段树就可以解决问题。

同时需要注意，这个题在DFS线段树的过程中，往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩，但是可以按轶合并。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
  Node *fa; int siz;
  Node() {
    fa = NULL; siz = 1;
  }
  void sc(Node *c) {
    siz += c -> siz;
    c -> fa = this;
  }
  void brk() {
    fa -> siz -= siz;
    fa = NULL;
  }
};
Node *r[maxn];
int n;
void init_set() {
  for(int i = 1; i <= n; i ++) {
    r[i] = new Node();
  }
}
Node *get_fa(Node *x) {
  if(x -> fa == NULL) {
    return x;
  } else {
    return get_fa(x -> fa);
  }
}
Node *link_set(Node *x, Node *y) {
  if(x -> siz < y -> siz) std::swap(x, y);
  x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
  return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
  return (get_fa(x) == get_fa(y));
}

const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
  if(ql <= L && R <= qr) {
    event[o].push_back(e);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
    if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
  }
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
  if(L == R) {
    que[o] = e;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      add_query(o << 1, L, M, p, e);
    } else {
      add_query(o << 1 | 1, M + 1, R, p, e);
    }
  }
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
  for(auto e : event[o]) {
    int u = e.first, v = e.second;
    if(!is_same(r[u], r[v])) {
#ifdef LOCAL
      printf("Merging %d and %d.\n", u, v);
#endif
      S.push(std::make_pair(merge_set(r[u], r[v]), o));
    }
  }
  if(L == R) {
    int u = que[o].first, v = que[o].second;
    if(u == -1 && v == -1) {
      ret[L] = -1;
    } else {
      if(is_same(r[u], r[v])) {
        ret[L] = 1;
      } else {
        ret[L] = 0;
      }
    }
  } else {
    int M = (L + R) / 2;
    solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
  }
  while(!S.empty() && S.top().second >= o) {
    Node *u = S.top().first; S.pop();
    u -> brk();
  }
}

std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
  int m; scanf("%d%d", &n, &m);
  init_set();
  pii fl(-1, -1);
  for(int i = 1; i <= m; i ++) {
    pii e; int op;
    scanf("%d%d%d", &op, &e.first, &e.second);
    if(e.first > e.second) {
      std::swap(e.first, e.second);
    }
    if(op == 2) {
      add_query(1, 1, m, i, e);
    } else {
      add_query(1, 1, m, i, fl);
      V.push_back(e);
      if(op == 0) {
        ma[e].push(i);
      } else {
        int last = ma[e].top(); ma[e].pop();
        add_event(1, 1, m, last, i - 1, e);
      }
    }
  }
  for(auto e : V) {
    while(!ma[e].empty()) {
      int g = ma[e].top(); ma[e].pop();
      add_event(1, 1, m, g, m, e);
    }
  }
  solve(1, 1, m);
  for(int i = 1; i <= m; i ++) {
    if(ret[i] != -1) {
      if(ret[i]) {
        puts("Y");
      } else {
        puts("N");
      }
    }
  }
  return 0;
}

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树，那就需要启发式合并了。

秒，秒啊……

很容易想到线段树，但是在[tex]N=10^6,M=10^7[/tex]的情况下，线段树肯定会TLE。

考虑修改，我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作，然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集！每个节点修改完后将其父亲改为下一个点，这样的话被修改的地方就可以轻松跳过了。

注意一个细节，第[tex]N[/tex]个馒头被染色后，其父亲会被修改为[tex]N+1[/tex]，所以说并查集实际上要开[tex]N+1[/tex]！

代码：

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路，瓶颈路需要MST，然后Kruskal求MST时最小边不是不可控的！也就是说我们可以控制最小边，从而求出符合要求的生成树，然后凿出瓶颈路。

所以我们可以直接枚举最小边，然后Kruskal求生成树，之后求瓶颈路。至于是否有解，第一遍Kruskal（第一遍求的其实是MST）之后看看是否联通即可。

不过这个题求瓶颈路个人建议用BFS而不是DFS，且不谈BFS效率高还不易炸堆栈段（尽管这个题没有炸堆栈段的隐患），DFS本身细节就很多，容易错。

代码：

/**************************************************************
    Problem: 1050
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3588 ms
    Memory:1172 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
    G_cnt++;
    next[G_cnt]=first[u];
    first[u]=G_cnt;
    to[G_cnt]=v;
    dist[G_cnt]=d;
}
inline void Clear_Graph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    G_cnt=0;
}
 
// BFS
bitset<maxn> vis;
struct Node{
    int x,maxv,minv;
};
pii BFS(){
    register int a,b,i;
    queue<Node> Q;
    Node tt;
    Q.push((Node){S,-1,0x7fffffff});
    vis[S]=true;
    while(!Q.empty()){
        tt=Q.front();
        Q.pop();
        if(tt.x==T)
            return make_pair(tt.maxv,tt.minv);
        REP_G(i,tt.x){
            if(!vis[to[i]]){
                vis[to[i]]=true;
                Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
            }
        }
    }
}
 
// BINGCHA Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    CL_ARR(rank,0);
}
 
// MST
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
    register int i,a,b,cnt=0;
    pii que;
    register double jia,yi;
    Clear_Graph();
    init_set();
    CUS_REP(i,x,E.size()){
        if(!is_same(E[i].u,E[i].v)){
            Add_Edge(E[i].u,E[i].v,E[i].d);
            Add_Edge(E[i].v,E[i].u,E[i].d);
            cnt++;
            union_set(E[i].u,E[i].v);
            if(cnt==n-1)
                break;
        }
    }
    if(is_same(S,T)){
        OK=true;
    }else{
        return;
    }
    vis.reset();
    que=BFS();
    a=que.first;
    b=que.second;
    jia=((double)a)/((double)b);
    yi=(double(ans.first))/(double(ans.second));
    if(jia<yi){
        ans.first=a;
        ans.second=b;
    }
}
 
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    REP(i,m){
        u=readint();
        v=readint();
        d=readint();
        E.push_back((Edge){u,v,d});
    }
    S=readint();
    T=readint();
    sort(E.begin(),E.end());
    ans.first=0x7fffffff;
    ans.second=1;
    REP(i,m){
        MST(i);
        if(!OK){
            if(!i){
                puts("IMPOSSIBLE");
                return 0;
            }else{
                break;
            }
        }
    }
    d=gcd(ans.first,ans.second);
    ans.first/=d;
    ans.second/=d;
    if(ans.second==1)
        printf("%d\n",ans.first);
    else
        printf("%d/%d\n",ans.first,ans.second);
    return 0;
}

倍增LCA经典题……

这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……

注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！

代码：

哎……做了这题，我才敢说我真的会了点并查集

这是道很经典，很有意思的并查集题目

其实也不难，每个点记录敌人集合然后乱搞即可

代码：

这道题到现在才A……

其实……离线处理并不像我想的那样变态……

需要注意的是，离线处理过程中，在将被删除的点加入时，联通分量数可能增加（其他一个点都连不了）

代码：

看起来是道并查集水题……

可i和j最高可达1000000000，直接开个数组放注定会MLE，怎么办？

注意n最高为1000000，所以每组数据中出现的i和j最多会有2000000种，所以我们可以把i和j“映射”为不大于2000000的整数，这样就能避免MLE了！

这种技术，就是离散化

同时注意防卡常！

代码：