word如何做网站链接,搜索引擎优化规则,广东深圳网站建设,东莞专业做网站题意#xff1a;有nnn个点mmm条边#xff0c;qqq次询问连接区间[L,R][L,R][L,R]中的边后的连通块个数。强制在线。 n,m,q≤2105n,m,q\leq 2\times10^5n,m,q≤2105
显然连通块个数n−任意一个生成森林的边数连通块个数n-任意一个生成森林的边数连通块个数n−任意一个生成森林…题意有nnn个点mmm条边qqq次询问连接区间[L,R][L,R][L,R]中的边后的连通块个数。强制在线。
n,m,q≤2×105n,m,q\leq 2\times10^5n,m,q≤2×105
显然连通块个数n−任意一个生成森林的边数连通块个数n-任意一个生成森林的边数连通块个数n−任意一个生成森林的边数
先遍历一遍所有边用LCT维护标号的最大生成树并记录下加入每条边iii时删除的边的编号aia_iai(如果没有删除边ai0a_i0ai0)
询问[L,R][L,R][L,R]时假装加入了[1,R][1,R][1,R]中的边。对于i∈[L,R]i\in[L,R]i∈[L,R]如果ai≥La_i\geq Lai≥L那么加入iii后会形成一个环并且环上所有边的编号都在[L,R][L,R][L,R]内这样iii就没有贡献。
所以只需要询问∑iLR[aiL]\sum_{iL}^R[a_iL]∑iLR[aiL]即可用主席树维护
复杂度O(nlogn)O(n\log n)O(nlogn)
注意自环要让aim1a_im1aim1
#include iostream
#include cstdio
#include cstring
#include cctype
#include cassert
#define MAXN 400005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int n,m;
int u[MAXN],v[MAXN],a[MAXN];
namespace LCT
{inline int min(const int x,const int y){return xy? x:y;}int ch[MAXN][2],fa[MAXN],rv[MAXN],mn[MAXN];inline void update(int x){mn[x]x;if (ch[x][0]) mn[x]min(mn[x],mn[ch[x][0]]);if (ch[x][1]) mn[x]min(mn[x],mn[ch[x][1]]);}inline void pushr(int x){swap(ch[x][0],ch[x][1]),rv[x]^1;}inline void pushdown(int x){if (rv[x]){if (ch[x][0]) pushr(ch[x][0]);if (ch[x][1]) pushr(ch[x][1]);rv[x]0;}}inline bool isroot(int x){return ch[fa[x]][0]!xch[fa[x]][1]!x;}inline int get(int x){return ch[fa[x]][1]x;}inline void rotate(int x){int yfa[x],zfa[y];int lget(x),rl^1;int wch[x][r];if (!isroot(y)) ch[z][get(y)]x;ch[x][r]y,ch[y][l]w;if (w) fa[w]y;fa[y]x,fa[x]z;update(y),update(x);}int q[MAXN],tp;inline void splay(int x){q[tp1]x;for (int ix;!isroot(i);ifa[i]) q[tp]fa[i];for (int itp;i1;i--) pushdown(q[i]);while (!isroot(x)){int yfa[x];if (!isroot(y)){if (get(x)get(y)) rotate(y);else rotate(x);}rotate(x);}}inline void access(int x){for (int y0;x;yx,xfa[x]) splay(x),ch[x][1]y,update(x);}inline void evert(int x){access(x),splay(x),pushr(x);}inline int findrt(int x){access(x),splay(x);while (ch[x][0]) xch[x][0],pushdown(x);return x;}inline bool link(int x,int y){evert(x);if (findrt(y)x) return false;fa[x]y;return true;}inline void cut(int x,int y){evert(x);
// access(y),splay(y);assert(findrt(y)xfa[x]y!ch[x][1]);ch[y][0]fa[x]0,update(y);}inline int query(int x,int y){evert(x),access(y),splay(y);return mn[y];}inline void addnode(int k){if (u[k]v[k]) return (void)(a[k]m1);int xmu[k],ymv[k];if (link(x,y)) cut(x,y);else{a[k]query(x,y);cut(a[k],mu[a[k]]),cut(a[k],mv[a[k]]);}link(x,k),link(y,k);}
}
using LCT::addnode;
namespace HJT
{int sum[MAXN5],ch[MAXN5][2],cnt;void insert(int x,int y,int l,int r,int k){xcnt,sum[x]sum[y],ch[x][0]ch[y][0],ch[x][1]ch[y][1];sum[x];if (lr) return;int mid(lr)1;if (kmid) insert(ch[x][0],ch[y][0],l,mid,k);else insert(ch[x][1],ch[y][1],mid1,r,k);}int query(int x,int l,int r,int ql,int qr){if (!x) return 0;if (qllrqr) return sum[x];if (qrl||rql) return 0;int mid(lr)1;return query(ch[x][0],l,mid,ql,qr)query(ch[x][1],mid1,r,ql,qr);}
}
int rt[MAXN];
using HJT::insert;
using HJT::query;
int main()
{nread(),mread();int q,t;qread(),tread();for (int i1;im;i) u[i]read(),v[i]read(),addnode(i);for (int i1;im;i) insert(rt[i],rt[i-1],0,m1,a[i]);int lans0;while (q--){int l,r;lread(),rread();if (t) l^lans,r^lans;printf(%d\n,lansn-query(rt[r],0,m1,0,l-1)query(rt[l-1],0,m1,0,l-1));}return 0;
}
