简单数据结构模板

3>bitset

bitsetbitset容器概论

bitsetbitset容器其实就是个01串。可以被看作是一个bool数组。它比bool数组更优秀的优点是：节约空间，节约时间，支持基本的位运算。在bitset容器中，8位占一个字节，相比于bool数组4位一个字节的空间利用率要高很多。同时，n位的bitset在执行一次位运算的复杂度可以被看作是n/32.

bitset容器的声明

因为bitset容器就是装01串的，所以不用在<>中装数据类型，这和一般的STL容器不太一样。<>中装01串的位数。

如：（声明一个1e5位的bitset）

bitset<100000> s;

常用的操作函数

• count()函数

它的作用是数出1的个数。

s.count();

• any()/none()函数

如果，bitset中全都为0，那么s.any()返回false，s.none()返回true。

反之，假如bitset中至少有一个1，即哪怕有一个1，那么s.any()返回true，s.none()返回false.

s.any();
s.none();

• set()函数

set()函数的作用是把bitset全部置为1.

特别地，set()函数里面可以传参数。set(u,v)的意思是把bitset中的第u位变成v,v∈0/1。

s.set();
s.set(u,v);

• reset()函数

与set()函数相对地，reset()函数将bitset的所有位置为0。而reset()函数只传一个参数，表示把这一位改成0。

s.reset();
s.reset(k);

• flip()函数

flip()函数与前两个函数不同，它的作用是将整个bitset容器按位取反。同上，其传进的参数表示把其中一位取反。

s.flip();
s.flip(k);

**PS：bitset能直接进行位运算，如：&，|，^,<<,>>,==/!= **

二，链表

1>链式前向星（邻接表）

struct Edge
{
    int nex, to;
} e[N <<1];
void add(int u, int v)
{
    e[++cnt].nex = head[u];
    head[u] = cnt;
    e[cnt].to = v;
}

2>舞蹈链

解决一类精确覆盖问题

模板题目为：给定一个N行M列的矩阵，矩阵中每个元素要么是1，要么是0

你需要在矩阵中挑选出若干行，使得对于矩阵的每一列j，在你挑选的这些行中，有且仅有一行的第j个元素为1

#include 
using namespace std;
#define re register int
#define ull unsigned long long
#define ll long long
#define inf 0x3f3f3f3f
#define N 1000010
#define mod 114514
#define lson rt <<1
#define rson rt <<1 | 1
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<\'0\'||ch>\'9\') {if (ch==\'-\') f=-1; ch=getchar();}
	while (ch>=\'0\' && ch <= \'9\') { x=(x<<1) + (x<<3) + (ll)ch-\'0\';ch=getchar();}
	return x*f;
}
int n, m, ans[1100],a[1100],l[250010],r[250010],las[1100];
int up[250010],down[250010],row[250010],col[250010];
int cnt,siz[1100];
void newlr(int u)
{
	r[l[u]]=l[r[u]]=u;
}
void newud(int u)
{
	down[up[u]]=up[down[u]]=u;
}
void dellr(int u)
{
	r[l[u]]=r[u];
	l[r[u]]=l[u];
}
void delud(int u)
{
	up[down[u]]=up[u];
	down[up[u]]=down[u];
}
void link(int lef,int rr,int uu,int dd,int rw,int dw)
{
	l[cnt]=lef; r[cnt]=rr;
	up[cnt]=uu; down[cnt]=dd;
	row[cnt]=rw; col[cnt]=dw;
}
void prep(int x)
{
	l[0]=r[0]=up[0]=down[0]=0;
	for (int i=1; i <= x; i++)
	{
		siz[i]=0;
		las[i]=i;
		cnt++;
		link(i-1,r[i-1],i,i,0,i);
		newlr(i);
	}
}
void add(int rw)
{
	if (a[0] == 0) return ;
	cnt++;
	link(cnt,cnt,las[a[1]],down[las[a[1]]],rw,a[1]);
	newud(cnt);
	siz[a[1]]++;las[a[1]]=cnt;
	for (int i=2;i<=a[0];i++)
	{
		cnt++;
		link(cnt-1,r[cnt-1],las[a[i]],down[las[a[i]]],rw,a[i]);
		newlr(cnt);newud(cnt);
		siz[a[i]]++;las[a[i]]=cnt;
	}
}
void del(int x)//因为节点序号1-m的节点的行数都为0，即虚拟节点，左右只用删除一次
{
	dellr(x);
	for (int i=up[x];i!=x;i=up[i])
	{
		for (int j=l[i];j!=i;j=l[j])
			delud(j),siz[col[j]]--;
	}
}
void back(int x)
{
	newlr(x);
	for (int i = up[x]; i!=x; i = up[i])
	{
		for (int j = l[i]; j!=i; j = l[j])
			newud(j),siz[col[j]]++;
	}
}
int dance(int step)
{
	if (!r[0])
	{
		for (int i=0;i

int main()
{
	n=read(),Q=read();
	for (int i=1;i<=n;i++) f[i][0]=read();
	for (int j=1;j<=18;j++)
		for (int i=1;i+(1<

int getfa(int x)
{
	if (x != dad[x])
	{
		int t = dad[x];
		dad[x] = getfa(dad[x]);
		value[x] += value[t];
	}
	return dad[x];
}

		int px = getfa(x);
		int py = getfa(y);
		if (px != py)
		{
			dad[px] = py;
			value[px] = -value[x] + value[y] + s;
		}

int n,k,dad[5000050],ans;
int getf(int x)
{
	return x==dad[x]?x:dad[x]=getf(dad[x]);
}
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=500100;i++) dad[i]=i;
	while (k--)
	{
		int a,b,ty;
		scanf("%d%d%d",&ty,&a,&b);
		int aa=a+n,bb=b+n;
		int aaa=a+2*n,bbb=b+2*n;
		if (a>n||b>n)
		{
			ans++;
			continue;
		}
		if (ty==1)
		{
			if (getf(aa)==getf(b)||getf(aaa)==getf(b))
			{
				ans++;
				continue;
			}
			dad[getf(a)]=getf(b);
			dad[getf(aa)]=getf(bb);
			dad[getf(aaa)]=getf(bbb);
		}
		if (ty==2)
		{
			if (a==b)
			{
				ans++;
				continue;
			}
			if (getf(a)==getf(b)||getf(aaa)==getf(b))
			{
				ans++;
				continue;
			}
			dad[getf(a)]=getf(bbb);
			dad[getf(aa)]=getf(b);
			dad[getf(aaa)]=getf(bb);
		}
	}
	printf("%d",ans);
	return 0;
}