3 条题解
-
0
这是另一个时间复杂度较高的做法：将询问离线下来，利用莫队和可撤销并查集完成操作。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i(a);i<=(b);++i) #define req(i,a,b) for(int i(a);i>=(b);--i) using namespace std; char buf[1<<23],*p1=buf,*p2=buf,ubuf[1<<23],*u=ubuf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) template<typename TP> inline TP read(TP &num) { TP x=0; int f=0; char ch=getchar(); while(ch<48||ch>57) f|=ch=='-',ch=getchar(); while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return num=f?-x:x; } template<typename ...Args> inline void read(Args &...args) { (read(args),...); } template<typename TP> inline void write(TP x) { (x<0)?(putchar('-'),x=-x):0; (x>9)?(write(x/10),0):0; putchar((x%10)^48); } template<typename TP> inline void writeln(TP x) { write<TP>(x); puts(""); } struct DSU { int n,st,sts; vector<int> dsu; stack<pair<int,int>> undo; DSU(int n) { this->n=n; dsu.resize(n+1); rep(i,0,n) dsu[i]=i; st=n; } int find(int x,bool sa=0) { if(dsu[x]==x) return x; if(sa) undo.emplace(x,dsu[x]); return dsu[x]=find(dsu[x],sa); } bool join(int x,int y) { int fx=find(x),fy=find(y); if(fx==fy) return 0; --st; dsu[fx]=fy; return 1; } void save(){sts=st;} void recover() { st=sts; while(!undo.empty()) { pair<int,int> tmp=undo.top();undo.pop(); dsu[tmp.first]=tmp.second; } } void tempjoin(int x,int y) { int fx=find(x,1),fy=find(y,1); if(fx==fy) return; --st; undo.emplace(fx,dsu[fx]); dsu[fx]=fy; } }; namespace Solve { int n,m,q,block=170; inline void main() { read(n,m,q); vector<array<int,2>> edge(m); vector<array<int,3>> query(q); rep(i,0,m-1) read(edge[i][0],edge[i][1]); rep(i,0,q-1) read(query[i][0],query[i][1]),--query[i][0],--query[i][1],query[i][2]=i; sort(query.begin(),query.end(),[](array<int,3> &a,array<int,3> &b) { int ba=a[0]/block,bb=b[0]/block; if(ba!=bb) return ba<bb; return a[1]<b[1]; }); DSU dsu(n); vector<int> ans(q); int lst=-1,pos=0; rep(i,0,q-1) { int cur=query[i][0]/block; if(cur!=lst) { dsu=DSU(n); lst=cur; pos=(cur+1)*block-1; rep(j,(cur+1)*block,query[i][1]) dsu.join(edge[j][0],edge[j][1]),++pos; } while(pos<query[i][1]) ++pos,dsu.join(edge[pos][0],edge[pos][1]); dsu.save(); for(int j=query[i][0];j<=query[i][1]&&j<(cur+1)*block;++j) dsu.tempjoin(edge[j][0],edge[j][1]); ans[query[i][2]]=dsu.st; dsu.recover(); } rep(i,0,q-1) writeln(ans[i]); } } signed main() { int T=1;while(T--)Solve::main(); return 0; } -
0
/solution/134/68c6be552338344d93c87add
对于上述做法，将树状数组改为主席树，可以在线解决问题。
-
0
将询问离线下来，按右端点排序，用 LCT 维护割边并用树状数组查询即可。
#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 0; char ch = getchar(); while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar(); while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return f ? -x : x; } int __stk[128], __top; inline void write(int x) { if(x < 0) putchar('-'), x = -x; do { __stk[++__top] = x % 10, x /= 10; } while (x); while (__top) putchar(__stk[__top--] + '0'); } const int mod = 998244353; void Min(int &x, int y) { y < x and (x = y); } void Max(int &x, int y) { y > x and (x = y); } void inc(int &x, int y) { (x += y) >= mod and (x -= mod); } void mul(int &x, int y) { x = 1ll * x * y % mod; } int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; } bool stmer; const int N = 4e5 + 10; struct edge { int u, v; } e[N]; struct Query { int l, id; }; int n, m, q; int ans[N]; vector<Query> op[N]; namespace BIT { int t[N]; void add(int x, int k) { while (x) t[x] += k, x -= x & -x; } int ask(int x) { int res = 0; while (x <= m) res += t[x], x += x & -x; return res; } } namespace LCT { int top; int fa[N], t[N][2], a[N], s[N], tag[N]; int stk[N]; bool nrt(int x) { return t[fa[x]][0] == x or t[fa[x]][1] == x; } int get(int x) { return t[fa[x]][1] == x; } void reverse(int x) { swap(t[x][0], t[x][1]), tag[x] ^= 1; } void pushdown(int x) { if (tag[x]) reverse(t[x][0]), reverse(t[x][1]), tag[x] = 0; } void update(int x) { s[x] = min({ s[t[x][0]], s[t[x][1]], a[x] }); } void rotate(int x) { int f1 = fa[x], f2 = fa[f1], k = get(x); if (nrt(f1)) t[f2][get(f1)] = x; fa[x] = f2; t[f1][k] = t[x][!k], fa[t[f1][k]] = f1; t[x][!k] = f1, fa[f1] = x; update(f1), update(x); } void splay(int x) { int p = stk[++top] = x; while (nrt(p)) stk[++top] = p = fa[p]; while (top) pushdown(stk[top--]); for (int f = fa[x]; nrt(x); rotate(x), f = fa[x]) if (nrt(f)) rotate(get(x) == get(f) ? f : x); } void access(int x) { int f = 0; while (x) splay(x), t[x][1] = f, update(x), f = x, x = fa[x]; } void mkrt(int x) { access(x), splay(x), reverse(x); } void split(int u, int v) { mkrt(u), access(v), splay(v); } int findrt(int x) { access(x), splay(x); while (t[x][0]) pushdown(x), x = t[x][0]; splay(x); return x; } void link(int u, int v) { mkrt(u), fa[u] = v; } void cut(int u, int v) { split(u, v), fa[u] = t[v][0] = 0, update(v); } bool check(int u, int v) { mkrt(u); return findrt(v) == u; } void init() { for (int i = 0; i <= n + m; i++) { fa[i] = t[i][0] = t[i][1] = BIT :: t[i] = 0; s[i] = a[i] = i <= n ? n + m + 1 : i; } } } void solve() { n = read(), m = read(), q = read(), LCT :: init(); for (int i = 1; i <= m; i++) e[i] = { read(), read() }; for (int i = 1; i <= q; i++) { int l = read(), r = read(); op[r].push_back({ l, i }); } for (int i = 1; i <= m; i++) { int u = e[i].u, v = e[i].v; if (LCT :: check(u, v) and u != v) { LCT :: split(u, v); int x = LCT :: s[v] - n; BIT :: add(x, -1); LCT :: cut(e[x].u, x + n), LCT :: cut(e[x].v, x + n); } if (u ^ v) { BIT :: add(i, 1); LCT :: link(u, i + n); LCT :: link(i + n, v); } for (Query l : op[i]) ans[l.id] = n - BIT :: ask(l.l); op[i].clear(); } for (int i = 1; i <= q; i++) write(ans[i]), putchar('\n'); } bool edmer; signed main() { // freopen("A.in", "r", stdin); // freopen("A.out", "w", stdout); cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n"; int T = 1; while(T--) solve(); cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n"; return 0; }
Murasame
LV 11
MOD
@ 2026-1-18 23:50:35
- 1