「APIO 2019」桥梁

发表于 分类于

题目链接：https://loj.ac/problem/3145。

考虑对操作分块，那么每次处理当前块的时候，先对块内的操作和不会在这个块内被修改的边按权值排序，然后从大到小用并查集维护连通性。

那么对于每个询问，只需要暴力扫一遍块内的修改，判一下要不要加进去就行了，然后得到答案之后把这些操作撤销。

撤销操作可以利用按秩合并的并查集，这个东西可以每次$\log n$的操作，并且每次操作只会修改$O(1)$的值，那么暴力撤回就行。

假设分块的大小为$B$，复杂度就是$O((B^2+m\log m)\cdot \frac{q}{B})$。

那么$B=\sqrt {m\log m}$的时候复杂度为$O(q\sqrt{m\log m})$。

我也不知道复杂度是不是这样的，反正我卡卡常练炼金就过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

struct opr {
    int op,x,v,ans,t;
}a[maxn],b[maxn];

int n,m,q,p[maxn];
pii e[maxn];
vector<pii > c[maxn];

struct DSU {
    int rk[maxn],fa[maxn],top,sz[maxn];
    pair<int*,int > sta[maxn];

    void clear() {for(int i=1;i<=n;i++) fa[i]=i,rk[i]=0,sz[i]=1;}

    int find(int x) {return fa[x]==x?x:find(fa[x]);}

    void ins(int u,int v,int op) {
        u=find(u),v=find(v);if(u==v) return ;
        if(rk[u]<=rk[v]) {
            if(op) {
                sta[++top]=mp(fa+u,fa[u]);
                sta[++top]=mp(sz+v,sz[v]);
            }
            fa[u]=v,sz[v]+=sz[u];
            if(rk[u]==rk[v]) {
                if(op) sta[++top]=mp(rk+v,rk[v]);
                rk[v]++;
            }
        } else {
            if(op) {
                sta[++top]=mp(fa+v,fa[v]);
                sta[++top]=mp(sz+u,sz[u]);
            }
            fa[v]=u,sz[u]+=sz[v];
        }
    }

    void undo() {
        while(top) *sta[top].fr=sta[top].sc,top--;
    }
}T;

struct edge{int u,v,w;}t[maxn];

pii s[maxn];

int cmp1(edge a,edge b) {return a.w>b.w;}

int cmp2(opr a,opr b) {return a.v>b.v;}
int cmp3(opr a,opr b) {return a.t<b.t;}

int main() {
    int st=clock();
    read(n),read(m);
    for(int i=1;i<=m;i++) {
        int u,v,w;read(u),read(v),read(w);
        e[i]=mp(u,v),c[i].pb(mp(0,w));
    }
    read(q);
    for(int i=1;i<=q;i++) {
        read(a[i].op),read(a[i].x),read(a[i].v);a[i].t=i;
        if(a[i].op==1) c[a[i].x].pb(mp(i,a[i].v));
    }
    int B=1000;
    for(int w=1;w<=q;w++) {
        if((w-1)%B) continue;
        int l=w,r=min(q,w+B-1),cnt=0;
        T.clear();
        for(int i=1;i<=m;i++) 
            if(p[i]==(int)c[i].size()-1||c[i][p[i]+1].fr>r)
                t[++cnt]=(edge){e[i].fr,e[i].sc,c[i][p[i]].sc};
        sort(t+1,t+cnt+1,cmp1);
        sort(a+l,a+r+1,cmp2);
        int pos=0,tt=0;
        for(int i=l;i<=r;i++) if(a[i].op==1) b[++tt]=a[i];
        for(int i=l;i<=r;i++) {
            if(a[i].op==1) continue;
            while(pos<cnt&&t[pos+1].w>=a[i].v) pos++,T.ins(t[pos].u,t[pos].v,0);
            for(int j=1;j<=tt;j++) {
                int x=b[j].x;
                if(b[j].t<=a[i].t) {
                    if(!s[x].fr||s[x].fr<b[j].t)
                        s[x]=mp(b[j].t,b[j].v);
                } else if(!s[x].fr) s[x]=c[x][p[x]];
            }
            for(int j=1;j<=tt;j++) {
                int x=b[j].x;
                if(s[x].sc>=a[i].v) T.ins(e[x].fr,e[x].sc,1);
                s[x]=mp(0,0);
            }
            a[i].ans=T.sz[T.find(a[i].x)];
            T.undo();
        }
        for(int i=1;i<=m;i++)
            while(p[i]!=(int)c[i].size()-1&&c[i][p[i]+1].fr<=r) p[i]++;
    }
    sort(a+1,a+q+1,cmp3);
    for(int i=1;i<=q;i++) if(a[i].op==2) write(a[i].ans);
    cerr<<(lf)(clock()-st)/1e3<<endl;
    return 0;
}