1.数据结构

hzoi_Shadow / 2024-10-05 / 原文

数据结构1

\(A\) luogu P5494 【模板】线段树分裂

\(B\) luogu P1637 三元上升子序列

  • 题解

\(C\) luogu P6492 [COCI2010-2011#6] STEP

  • L 视作 \(0\)R 视作 \(1\)

  • 则等价于查询最长 \(01\) 串长度,线段树维护前后缀信息即可,写法跟维护最大子段和差不多。

    点击查看代码
    int a[200010];
    struct SMT
    {
    	struct SegmentTree
    	{
    		int l,r,pre,suf,ans;
    	}tree[800010];
    	int lson(int x)
    	{
    		return x*2;
    	}
    	int rson(int x)
    	{
    		return x*2+1;
    	}
    	void pushup(int rt)
    	{
    		tree[rt].ans=max(tree[lson(rt)].ans,tree[rson(rt)].ans);
    		tree[rt].pre=tree[lson(rt)].pre;
    		tree[rt].suf=tree[rson(rt)].suf;
    		if(a[tree[lson(rt)].r]!=a[tree[rson(rt)].l])
    		{
    			tree[rt].ans=max(tree[rt].ans,tree[lson(rt)].suf+tree[rson(rt)].pre);
    			tree[rt].pre+=(tree[lson(rt)].pre==tree[lson(rt)].r-tree[lson(rt)].l+1)*tree[rson(rt)].pre;
    			tree[rt].suf+=(tree[rson(rt)].suf==tree[rson(rt)].r-tree[rson(rt)].l+1)*tree[lson(rt)].suf;
    		}
    	}
    	void build(int rt,int l,int r)
    	{
    		tree[rt].l=l;
    		tree[rt].r=r;
    		if(l==r)
    		{
    			tree[rt].pre=tree[rt].suf=tree[rt].ans=1;
    			return;
    		}
    		int mid=(l+r)/2;
    		build(lson(rt),l,mid);
    		build(rson(rt),mid+1,r);
    		pushup(rt);
    	}
    	void update(int rt,int pos)
    	{
    		if(tree[rt].l==tree[rt].r)
    		{
    			a[tree[rt].l]^=1;
    			return;
    		}
    		int mid=(tree[rt].l+tree[rt].r)/2;
    		if(pos<=mid)
    		{
    			update(lson(rt),pos);
    		}
    		else
    		{
    			update(rson(rt),pos);		
    		}
    		pushup(rt);
    	}
    	SegmentTree query(int rt,int x,int y)
    	{
    		if(x<=tree[rt].l&&tree[rt].r<=y)
    		{
    			return tree[rt];
    		}
    		int mid=(tree[rt].l+tree[rt].r)/2;
    		SegmentTree p,q,ans;
    		if(y<=mid)
    		{
    			return query(lson(rt),x,y);
    		}
    		else
    		{
    			if(x>mid)
    			{
    				return query(rson(rt),x,y);
    			}
    			else
    			{
    				p=query(lson(rt),x,y);
    				q=query(rson(rt),x,y);
    				ans.ans=max(p.ans,q.ans);
    				ans.pre=p.pre;
    				ans.suf=q.suf;
    				if(a[p.r]!=a[q.l])
    				{
    					ans.ans=max(ans.ans,p.suf+q.pre);
    					ans.pre+=(p.pre==p.r-p.l+1)*q.pre;
    					ans.suf+=(q.suf==q.r-q.l+1)*p.suf;
    				}
    				return ans;
    			}
    		}
    	}
    }T;
    int main()
    {
    	int n,m,x,i;
    	cin>>n>>m;
    	T.build(1,1,n);
    	for(i=1;i<=m;i++)
    	{
    		cin>>x;
    		T.update(1,x);
    		cout<<T.query(1,1,n).ans<<endl;
    	}
    	return 0;
    }
    

\(D\) luogu P6136 【模板】普通平衡树(数据加强版)

  • 题解

\(E\) luogu P3038 [USACO11DEC] Grass Planting G

  • 多倍经验: SP12005 GRASSPLA - Grass Planting
  • 题解

\(F\) luogu P7735 [NOI2021] 轻重边

  • 维护路径信息,考虑树剖。

  • 边权直接维护不太好维护,考虑转成点权。而直接将边权信息赋给深度较深的儿子节点在本题中难以适应。

  • 考虑给每一个点赋一个权值 \(val\) 使得对于任意一条边 \(u \to v\)\(val_{u}=val_{v}\)\(u \to v\) 是重边,否则是轻边。

  • 此时操作 \(1\) 等价于将 \(u \to v\) 上的点的权值都赋成一个统一的值;操作 \(2\) 等价于查询 \(u \to v\) 上相邻两点权值相同的无序点对,做法同 luogu P2486 [SDOI2011] 染色 差不多,线段树维护即可。

    点击查看代码
    struct node
    {
    	int nxt,to;
    }e[200010];
    int head[200010],c[200010],cc[200010],fa[200010],dep[200010],siz[200010],son[200010],dfn[200010],top[200010],cnt=0,tot=0;
    void add(int u,int v)
    {
    	cnt++;
    	e[cnt].nxt=head[u];
    	e[cnt].to=v;
    	head[u]=cnt;
    }
    struct SMT
    {
    	struct SegmentTree
    	{
    		int l,r,lazy,lc,rc,ans;
    	}tree[800010];
    	int lson(int x)
    	{
    		return x*2;
    	}
    	int rson(int x)
    	{
    		return x*2+1;
    	}
    	void pushup(int rt)
    	{
    		tree[rt].ans=tree[lson(rt)].ans+tree[rson(rt)].ans+(tree[lson(rt)].rc==tree[rson(rt)].lc);
    		tree[rt].lc=tree[lson(rt)].lc;
    		tree[rt].rc=tree[rson(rt)].rc;
    	}
    	void build(int rt,int l,int r)
    	{
    		tree[rt].l=l;
    		tree[rt].r=r;
    		tree[rt].lazy=0;
    		if(l==r)
    		{
    			tree[rt].lc=tree[rt].rc=cc[l];
    			tree[rt].ans=0;
    			return;
    		}
    		int mid=(l+r)/2;
    		build(lson(rt),l,mid);
    		build(rson(rt),mid+1,r);
    		pushup(rt);
    	}
    	void pushdown(int rt)
    	{
    		if(tree[rt].lazy!=0)
    		{
    			tree[lson(rt)].lc=tree[lson(rt)].rc=tree[rt].lazy;
    			tree[rson(rt)].lc=tree[rson(rt)].rc=tree[rt].lazy;
    			tree[lson(rt)].ans=tree[lson(rt)].r-tree[lson(rt)].l+1-1;
    			tree[rson(rt)].ans=tree[rson(rt)].r-tree[rson(rt)].l+1-1;
    			tree[lson(rt)].lazy=tree[rson(rt)].lazy=tree[rt].lazy;
    			tree[rt].lazy=0;
    		}
    	}
    	void update(int rt,int x,int y,int val)
    	{
    		if(x<=tree[rt].l&&tree[rt].r<=y)	
    		{
    			tree[rt].lc=tree[rt].rc=tree[rt].lazy=val;
    			tree[rt].ans=tree[rt].r-tree[rt].l+1-1;
    			return;
    		}
    		pushdown(rt);
    		int mid=(tree[rt].l+tree[rt].r)/2;
    		if(x<=mid)
    		{
    			update(lson(rt),x,y,val);
    		}
    		if(y>mid)
    		{
    			update(rson(rt),x,y,val);
    		}
    		pushup(rt);
    	}
    	SegmentTree query(int rt,int x,int y)
    	{
    		if(x<=tree[rt].l&&tree[rt].r<=y)
    		{
    			return tree[rt];
    		}
    		pushdown(rt);
    		int mid=(tree[rt].l+tree[rt].r)/2;
    		SegmentTree p,q,ans;
    		if(y<=mid)
    		{
    			return query(lson(rt),x,y);
    		}
    		else
    		{
    			if(x>mid)
    			{
    				return query(rson(rt),x,y);
    			}
    			else
    			{
    				p=query(lson(rt),x,y);
    				q=query(rson(rt),x,y);
    				ans.ans=p.ans+q.ans+(p.rc==q.lc);
    				ans.lc=p.lc;
    				ans.rc=q.rc;
    				return ans;
    			}
    		}
    	}
    }T;
    void dfs1(int x,int father)
    {
    	siz[x]=1;
    	fa[x]=father;
    	dep[x]=dep[father]+1;
    	for(int i=head[x];i!=0;i=e[i].nxt)
    	{
    		if(e[i].to!=father)
    		{
    			dfs1(e[i].to,x);
    			siz[x]+=siz[e[i].to];
    			son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
    		}
    	}
    }
    void dfs2(int x,int id)
    {
    	top[x]=id;
    	tot++;
    	dfn[x]=tot;
    	cc[tot]=c[x];
    	if(son[x]!=0)
    	{
    		dfs2(son[x],id);
    		for(int i=head[x];i!=0;i=e[i].nxt)
    		{
    			if(e[i].to!=fa[x]&&e[i].to!=son[x])
    			{
    				dfs2(e[i].to,e[i].to);
    			}
    		}
    	}
    }
    void update1(int u,int v,int val)
    {
    	while(top[u]!=top[v])
    	{
    		if(dep[top[u]]>dep[top[v]])
    		{
    			T.update(1,dfn[top[u]],dfn[u],val);
    			u=fa[top[u]];
    		}
    		else
    		{
    			T.update(1,dfn[top[v]],dfn[v],val);
    			v=fa[top[v]];
    		}
    	}
    	if(dep[u]<dep[v])
    	{
    		T.update(1,dfn[u],dfn[v],val);
    	}
    	else
    	{
    		T.update(1,dfn[v],dfn[u],val);
    	}
    }
    int query1(int u,int v)
    {
    	int ans=0;
    	while(top[u]!=top[v])
    	{
    		if(dep[top[u]]>dep[top[v]])
    		{
    			ans+=T.query(1,dfn[top[u]],dfn[u]).ans+(T.query(1,dfn[top[u]],dfn[top[u]]).lc==T.query(1,dfn[fa[top[u]]],dfn[fa[top[u]]]).lc);
    			u=fa[top[u]];
    		}
    		else
    		{
    			ans+=T.query(1,dfn[top[v]],dfn[v]).ans+(T.query(1,dfn[top[v]],dfn[top[v]]).lc==T.query(1,dfn[fa[top[v]]],dfn[fa[top[v]]]).lc);
    			v=fa[top[v]];
    		}
    	}
    	if(dep[u]<dep[v])
    	{
    		ans+=T.query(1,dfn[u],dfn[v]).ans;
    	}
    	else
    	{
    		ans+=T.query(1,dfn[v],dfn[u]).ans;
    	}
    	return ans;
    }
    int main()
    {
    	int t,n,m,pd,u,v,i,j;
    	scanf("%d",&t);
    	for(j=1;j<=t;j++)
    	{
    		cnt=tot=0;
    		memset(e,0,sizeof(e));
    		memset(head,0,sizeof(head));
    		memset(son,0,sizeof(son));
    		scanf("%d%d",&n,&m);
    		for(i=1;i<=n;i++)
    		{
    			c[i]=i;
    		}
    		for(i=1;i<=n-1;i++)
    		{
    			scanf("%d%d",&u,&v);
    			add(u,v);
    			add(v,u);
    		}
    		dfs1(1,0);
    		dfs2(1,1);
    		T.build(1,1,n);
    		for(i=1;i<=m;i++)
    		{
    			scanf("%d%d%d",&pd,&u,&v);
    			if(pd==1)
    			{
    				update1(u,v,n+i);
    			}
    			else
    			{
    				printf("%d\n",query1(u,v));
    			}
    		}
    	}
    	return 0;
    }
    

\(G\) luogu P3605 [USACO17JAN] Promotion Counting P

  • 题解

\(H\) luogu P7394 「TOCO Round 1」History

\(I\) luogu P7671 [GDOI2016] 疯狂动物城

\(J\) CF915E Physical Education Lessons

  • 题解

\(K\) CF19D Points

  • 离散化后线段树套 set 即可。

  • 叶子节点只保留 \(y\) 坐标的最大值然后进行线段树上二分。

    点击查看代码
    int x[200010],y[200010],xx[200010],yy[200010];
    char pd[200010][8];
    set<int>s[200010];
    struct SMT
    {
    	struct SegmentTree
    	{
    		int l,r,maxx;
    	}tree[800010];
    	int lson(int x)
    	{
    		return x*2;
    	}
    	int rson(int x)
    	{
    		return x*2+1;
    	}
    	void pushup(int rt)
    	{
    		tree[rt].maxx=max(tree[lson(rt)].maxx,tree[rson(rt)].maxx);
    	}
    	void build(int rt,int l,int r)
    	{
    		tree[rt].l=l;
    		tree[rt].r=r;
    		if(l==r)
    		{
    			s[l].insert(-0x7f7f7f7f);
    			tree[rt].maxx=-0x7f7f7f7f;
    			return;
    		}
    		int mid=(l+r)/2;
    		build(lson(rt),l,mid);
    		build(rson(rt),mid+1,r);
    		pushup(rt);
    	}
    	void update(int rt,int pos,int val)
    	{
    		if(tree[rt].l==tree[rt].r)
    		{
    			tree[rt].maxx=val;
    			return;
    		}
    		int mid=(tree[rt].l+tree[rt].r)/2;
    		if(pos<=mid)
    		{
    			update(lson(rt),pos,val);
    		}
    		else
    		{
    			update(rson(rt),pos,val);
    		}
    		pushup(rt);
    	}
    	int query(int rt,int x,int y,int val)
    	{
    		if(tree[rt].maxx<val)
    		{
    			return -1;
    		}
    		if(tree[rt].l==tree[rt].r)
    		{
    			return tree[rt].l;
    		}
    		int mid=(tree[rt].l+tree[rt].r)/2,p,q;
    		if(y<=mid)
    		{
    			return query(lson(rt),x,y,val);
    		}
    		else
    		{
    			if(x>mid)
    			{
    				return query(rson(rt),x,y,val);
    			}
    			else
    			{
    				p=query(lson(rt),x,y,val);
    				if(p!=-1)
    				{
    					return p;
    				}
    				q=query(rson(rt),x,y,val);
    				if(q!=-1)
    				{
    					return q;
    				}
    				return -1;
    			}
    		}
    	}
    }T;
    int main()
    {
    	int n,ans,i;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    	{
    		scanf("%s%d%d",(pd[i]+1),&x[i],&y[i]);
    		xx[i]=x[i];
    		yy[i]=y[i];
    	}
    	sort(xx+1,xx+1+n);
    	sort(yy+1,yy+1+n);
    	xx[0]=unique(xx+1,xx+1+n)-(xx+1);
    	yy[0]=unique(yy+1,yy+1+n)-(yy+1);
    	T.build(1,1,xx[0]);
    	for(i=1;i<=n;i++)
    	{
    		x[i]=lower_bound(xx+1,xx+1+xx[0],x[i])-xx;
    		y[i]=lower_bound(yy+1,yy+1+yy[0],y[i])-yy;
    		if(pd[i][1]=='a')
    		{
    			ans=*--s[x[i]].end();
    			s[x[i]].insert(y[i]);
    			if(ans!=*--s[x[i]].end())
    			{
    				T.update(1,x[i],*--s[x[i]].end());
    			}
    		}
    		if(pd[i][1]=='r')
    		{
    			ans=*--s[x[i]].end();
    			s[x[i]].erase(s[x[i]].find(y[i]));
    			if(ans!=*--s[x[i]].end())
    			{
    				T.update(1,x[i],*--s[x[i]].end());
    			}
    		}
    		if(pd[i][1]=='f')
    		{
    			if(x[i]+1<=xx[0])
    			{
    				ans=T.query(1,x[i]+1,xx[0],y[i]+1);
    				if(ans==-1)
    				{
    					printf("-1\n");
    				}
    				else
    				{
    					printf("%d %d\n",xx[ans],yy[*s[ans].upper_bound(y[i])]);
    				}
    			}
    			else
    			{
    				printf("-1\n");
    			}
    		}
    	}
    	return 0;
    }
    

\(L\) CF193D Two Segments

\(M\) CF1983F array-value

\(N\) [ABC371F] Takahashi in Narrow Road

  • 题解

\(O\) CF1304F2 Animal Observation (hard version)

\(P\) CF946G Almost Increasing Array

\(Q\) CF718C Sasha and Array

  • 容易有 \(\begin{bmatrix} Fib_{n} & Fib_{n+1} \end{bmatrix}=\begin{bmatrix} Fib_{n-1} & Fib_{n} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\)

  • 建树时暴力算斐波那契数,修改时维护 \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) 的指数增加量标记,区间和维护矩阵加法即可。

    • 本质上应用了矩阵的结合律 \(A \times B+A \times C=A \times (B+C)\)
  • 为方便重载运算符,将原 \(F\) 矩阵写作 \(\begin{bmatrix} Fib_{n} & Fib_{n+1} \\ 0 & 0 \end{bmatrix}\)

    点击查看代码
    const ll p=1000000007;
    struct Matrix
    {
    	ll ma[3][3];
    	Matrix()
    	{
    		memset(ma,0,sizeof(ma));
    	}
    	Matrix operator + (const Matrix &another) const
    	{
    		Matrix ans;
    		for(ll i=1;i<=2;i++)
    		{
    			for(ll j=1;j<=2;j++)
    			{
    				ans.ma[i][j]=(ma[i][j]+another.ma[i][j])%p;
    			}
    		}
    		return ans;
    	}
    	Matrix operator * (const Matrix &another) const
    	{
    		Matrix ans;
    		for(ll i=1;i<=2;i++)
    		{
    			for(ll j=1;j<=2;j++)
    			{
    				for(ll h=1;h<=2;h++)
    				{
    					ans.ma[i][j]=(ans.ma[i][j]+ma[i][h]*another.ma[h][j]%p)%p;
    				}
    			}
    		}
    		return ans;
    	}
    	bool operator == (const Matrix &another) const
    	{
    		for(ll i=1;i<=2;i++)
    		{
    			for(ll j=1;j<=2;j++)
    			{
    				if(ma[i][j]!=another.ma[i][j])
    				{
    					return false;
    				}
    			}
    		}
    		return true;
    	}
    }base,I;
    ll a[100010];
    Matrix qpow(Matrix a,ll b,ll p)
    {
    	Matrix ans;
    	for(ll i=1;i<=2;i++)
    	{
    		ans.ma[i][i]=1;
    	}
    	while(b)
    	{
    		if(b&1)
    		{
    			ans=ans*a;
    		}
    		b>>=1;
    		a=a*a;
    	}
    	return ans;
    }
    struct SMT
    {
    	struct SegmentTree
    	{
    		ll l,r;
    		Matrix sum,lazy;
    	}tree[400010];
    	ll lson(ll x)
    	{
    		return x*2;
    	}
    	ll rson(ll x)
    	{
    		return x*2+1;
    	}
    	void pushup(ll rt)
    	{
    		tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;
    	}
    	void build(ll rt,ll l,ll r)
    	{
    		tree[rt].l=l;
    		tree[rt].r=r;
    		tree[rt].lazy=I;
    		if(l==r)
    		{
    			tree[rt].sum.ma[1][1]=tree[rt].sum.ma[2][1]=tree[rt].sum.ma[2][2]=0;
    			tree[rt].sum.ma[1][2]=1;
    			tree[rt].sum=tree[rt].sum*qpow(base,a[l],p);
    			return;
    		}
    		ll mid=(l+r)/2;
    		build(lson(rt),l,mid);
    		build(rson(rt),mid+1,r);
    		pushup(rt);
    	}
    	void pushdown(ll rt)
    	{
    		if(!(tree[rt].lazy==I))
    		{
    			tree[lson(rt)].sum=tree[lson(rt)].sum*tree[rt].lazy;
    			tree[rson(rt)].sum=tree[rson(rt)].sum*tree[rt].lazy;
    			tree[lson(rt)].lazy=tree[lson(rt)].lazy*tree[rt].lazy;
    			tree[rson(rt)].lazy=tree[rson(rt)].lazy*tree[rt].lazy;
    			tree[rt].lazy=I;
    		}
    	}
    	void update(ll rt,ll x,ll y,Matrix val)
    	{
    		if(x<=tree[rt].l&&tree[rt].r<=y)
    		{
    			tree[rt].sum=tree[rt].sum*val;
    			tree[rt].lazy=tree[rt].lazy*val;
    			return;
    		}
    		pushdown(rt);
    		ll mid=(tree[rt].l+tree[rt].r)/2;
    		if(x<=mid)
    		{
    			update(lson(rt),x,y,val);
    		}
    		if(y>mid)
    		{
    			update(rson(rt),x,y,val);
    		}
    		pushup(rt);
    	}
    	ll query(ll rt,ll x,ll y)
    	{
    		if(x<=tree[rt].l&&tree[rt].r<=y)
    		{
    			return tree[rt].sum.ma[1][1];
    		}
    		pushdown(rt);
    		int mid=(tree[rt].l+tree[rt].r)/2,ans=0;
    		if(x<=mid)
    		{
    			ans=(ans+query(lson(rt),x,y))%p;
    		}
    		if(y>mid)
    		{
    			ans=(ans+query(rson(rt),x,y))%p;
    		}
    		return ans;
    	}
    }T;
    int main()
    {
    	ll n,m,pd,l,r,x,i;
    	cin>>n>>m;
    	for(i=1;i<=n;i++)
    	{
    		cin>>a[i];
    	}
    	base.ma[1][1]=0;
    	base.ma[1][2]=base.ma[2][1]=base.ma[2][2]=1;
    	I.ma[1][1]=I.ma[2][2]=1;
    	I.ma[1][2]=I.ma[2][1]=0;
    	T.build(1,1,n);
    	for(i=1;i<=m;i++)
    	{
    		cin>>pd>>l>>r;
    		if(pd==1)
    		{
    			cin>>x;
    			T.update(1,l,r,qpow(base,x,p));
    		}
    		else
    		{
    			cout<<T.query(1,l,r)<<endl;
    		}
    	}
    	return 0;
    }
    

\(R\) CF1956F Nene and the Passing Game

\(S\) [ABC351G] Hash on Tree

\(T\) [ARC073F] Many Moves

\(U\) luogu P4719 【模板】"动态 DP"&动态树分治

\(V\) luogu P6348 [PA2011] Journeys

  • 题解

\(W\) luogu P2605 [ZJOI2010] 基站选址

  • 题解

\(X\) luogu P3521 [POI2011] ROT-Tree Rotations

  • 题解

数据结构2

\(A\) luogu B3656 【模板】双端队列 1

  • list 代替 deque

  • 关于 dequelist 的空间问题,详见 关于deque和list 。

    点击查看代码
    list<int>q[1000001];
    int main()
    {
        int n,i,a,x;
        string pd;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>pd;
            if(pd=="push_back")
            {
                cin>>a>>x;
                q[a].push_back(x);
            }
            if(pd=="pop_back")
            {
                cin>>a;
                if(q[a].empty()==0)
                {
                    q[a].pop_back();
                }
            }
            if(pd=="push_front")
            {
                cin>>a>>x;
                q[a].push_front(x);
            }
            if(pd=="pop_front")
            {
                cin>>a;
                if(q[a].empty()==0)
                {
                    q[a].pop_front();
                }
            }
            if(pd=="size")
            {
                cin>>a;
                cout<<q[a].size()<<endl;
            }
            if(pd=="front")
            {
                cin>>a;
                if(q[a].empty()==0)
                {
                    cout<<q[a].front()<<endl;
                }
            }
            if(pd=="back")
            {
                cin>>a;
                if(q[a].empty()==0)
                {
                    cout<<q[a].back()<<endl;
                }
            }
        }
        return 0;
    }
    

\(B\) luogu P1892 [BOI2003] 团伙

  • 考虑扩展域并查集,把一个点 \(x\) 拆成两个节点 \(x_{friend}\)\(x_{enemy}\)

  • \(x,y\) 是朋友,则合并 \(x_{friend},y_{friend}\) ;否则合并 \(x_{friend},y_{enemy}\)\(x_{enemy},y_{friend}\)

    点击查看代码
    int vis[2010];
    struct DSU
    {
    	int fa[2010];
    	void init(int n)
    	{
    		for(int i=1;i<=n;i++)
    		{
    			fa[i]=i;
    		}
    	}
    	int find(int x)
    	{
    		return fa[x]==x?x:fa[x]=find(fa[x]);
    	}
    	void merge(int x,int y)
    	{
    		x=find(x);
    		y=find(y);
    		if(x!=y)
    		{
    			fa[x]=y;
    		}
    	}
    }D;
    int main()
    {
    	int n,m,x,y,ans=0,i;
    	char pd;
    	cin>>n>>m;
    	D.init(2*n);
    	for(i=1;i<=m;i++)
    	{
    		cin>>pd>>x>>y;
    		if(pd=='F')
    		{
    			D.merge(x,y);
    		}
    		else
    		{
    			D.merge(x,y+n);
    			D.merge(x+n,y);
    		}
    	}
    	for(i=1;i<=n;i++)
    	{
    		ans+=(vis[D.find(i)]==0);
    		vis[D.find(i)]=1;		
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    

\(C\) luogu P2502 [HAOI2006] 旅行

\(D\) luogu P3402 可持久化并查集

  • 题解

\(E\) luogu P4768 [NOI2018] 归程

\(F\) luogu P5854 【模板】笛卡尔树

\(G\) luogu P2081 [NOI2012] 迷失游乐园

\(H\) luogu P4381 [IOI2008] Island

  • 题解 。

\(I\) CF1713E Cross Swapping

\(J\) HDU6403 Card Game

  • 题解

\(K\) luogu P6453 [COCI2008-2009#4] PERIODNI

  • 多倍经验: SP3734 PERIODNI - Periodni

\(L\) luogu P3765 总统选举

\(M\) CF1920F2 Smooth Sailing (Hard Version)

\(N\) CF1687C Sanae and Giant Robot

\(O\) [AGC003E] Sequential operations on Sequence

\(P\) luogu P3452 [POI2007] BIU-Offices