「BZOJ3514」Codechef MARCH14 GERALD07加强版

2014年9月11日7,9413

Description

N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。

Input

第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。
接下来M行，代表图中的每条边。
接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor lastans和R xor lastans。

Output

K行每行一个整数代表该组询问的联通块个数。

Sample Input

3 5 4 0
1 3
1 2
2 1
3 2
2 2
2 3
1 5
5 5
1 2

Sample Output

2
1
3
1

HINT

对于100%的数据，1≤N、M、K≤200,000。

题解

wulala

葱娘说这是一个很巧妙的题。。
有一个比较猎奇的做法：首先把边依次加到图中，若当前这条边与图中的边形成了环，那么把这个环中最早加进来的边弹出去
并将每条边把哪条边弹了出去记录下来：ntr[i] = j，特别地，要是没有弹出边，ntr[i] = 0;
这个显然是可以用LCT来弄的对吧。
然后对于每个询问，我们的答案就是对l~r中ntr小于l的边求和，并用n减去这个值
正确性可以YY一下：
如果一条边的ntr >= l,那么显然他可以与从l ~ r中的边形成环，那么它对答案没有贡献
反之如果一条边的ntr < l那么它与从l ~ r中的边是不能形成环的，那么他对答案的贡献为-1
对于查询从l ~ r中有多少边的ntr小于l，我反正是用的函数式线段树

正是丧心病狂啊。。。为何一个小时能写完，蒟蒻做不到。。。

而且，我的常数不知道比wulala大到哪里去了，而且代码还很丑

还有。。。ntr这个数组名真是hentai啊

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define inf 1000000000
#define ll long long 
#define N 400005
#define M 200005
using namespace std;
inline int read()
{
    int 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*10+ch-'0';ch=getchar();}
    return x*f;
}
bool type;
int n,m,Q,lastans,top,tot,sz;
int s[N],st[M],root[M];
int c[N][2],fa[N],val[N],mn[N];
int sum[4000005],ls[4000005],rs[4000005];
bool rev[N];
struct edge{int u,v;}e[M];
bool isroot(int x)
{
	return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
}
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	mn[x]=x;
	if(val[mn[l]]<val[mn[x]])mn[x]=mn[l];
	if(val[mn[r]]<val[mn[x]])mn[x]=mn[r];	
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(rev[x])
	{
		rev[x]^=1;rev[l]^=1;rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
}
void rotate(int x)
{
	int y=fa[x],z=fa[y],l,r;
	if(c[y][0]==x)l=0;else l=1;r=l^1;
	if(!isroot(y))
	{
		if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;
	}
	fa[y]=x;fa[x]=z;fa[c[x][r]]=y;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x)
{
	top=0;s[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])
		s[++top]=fa[i];
	for(int i=top;i;i--)
		pushdown(s[i]);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	for(int t=0;x;t=x,x=fa[x])
	{
		splay(x);c[x][1]=t;update(x);
	}
}
void makeroot(int x)
{
	access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
	makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);access(y);splay(y);
	c[y][0]=fa[x]=0;
}
int find(int x)
{
	access(x);splay(x);
	while(c[x][0])x=c[x][0];
	return x;
}
int query(int x,int y)
{
	makeroot(x);access(y);splay(y);
	return mn[y];
}
void insert(int l,int r,int x,int &y,int val)
{
	y=++sz;
	sum[y]=sum[x]+1;
	if(l==r)return;
	ls[y]=ls[x];rs[y]=rs[x];
	int mid=(l+r)>>1;
	if(val<=mid)insert(l,mid,ls[x],ls[y],val);
	else insert(mid+1,r,rs[x],rs[y],val);
}
int query(int l,int r,int x,int y,int val)
{
	if(r==val)return sum[y]-sum[x];
	int mid=(l+r)>>1;
	if(val<=mid)return query(l,mid,ls[x],ls[y],val);
	else return sum[ls[y]]-sum[ls[x]]+query(mid+1,r,rs[x],rs[y],val);
}
void pre()
{
	tot=n;
	for(int i=1;i<=m;i++)
	{
		int u=e[i].u,v=e[i].v;
		if(u==v)
		{
			st[i]=i;continue;
		}
		if(find(u)==find(v))
		{
			int t=query(u,v),x=val[t];
			st[i]=x;
			cut(e[x].u,t);cut(e[x].v,t);
		}
		tot++;
		mn[tot]=tot;val[tot]=i;
		link(u,tot);link(v,tot);
	}
	for(int i=1;i<=m;i++)
		insert(0,m,root[i-1],root[i],st[i]);
}
void solve()
{
	for(int i=1;i<=Q;i++)
	{
		int l=read(),r=read();
		if(type)l^=lastans,r^=lastans;
		lastans=n-query(0,m,root[l-1],root[r],l-1);
		printf("%d\n",lastans);
	}
}
int main()
{
	n=read();m=read();Q=read();type=read();
	val[0]=inf;
	for(int i=1;i<=n;i++)mn[i]=i,val[i]=inf;
	for(int i=1;i<=m;i++)
		e[i].u=read(),e[i].v=read();
	pre();
	solve();
	return 0;
}

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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define inf 1000000000

#define ll long long

#define N 400005

#define M 200005

using namespace std;

inline int read()

{

int 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*10+ch-'0';ch=getchar();}

return x*f;

}

bool type;

int n,m,Q,lastans,top,tot,sz;

int s[N],st[M],root[M];

int c[N][2],fa[N],val[N],mn[N];

int sum[4000005],ls[4000005],rs[4000005];

bool rev[N];

struct edge{int u,v;}e[M];

bool isroot(int x)

{

return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;

}

void update(int x)

{

int l=c[x][0],r=c[x][1];

mn[x]=x;

if(val[mn[l]]<val[mn[x]])mn[x]=mn[l];

if(val[mn[r]]<val[mn[x]])mn[x]=mn[r];

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

if(rev[x])

{

rev[x]^=1;rev[l]^=1;rev[r]^=1;

swap(c[x][0],c[x][1]);

}

void rotate(int x)

{

int y=fa[x],z=fa[y],l,r;

if(c[y][0]==x)l=0;else l=1;r=l^1;

if(!isroot(y))

{

if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;

}

fa[y]=x;fa[x]=z;fa[c[x][r]]=y;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x)

{

top=0;s[++top]=x;

for(int i=x;!isroot(i);i=fa[i])

s[++top]=fa[i];

for(int i=top;i;i--)

pushdown(s[i]);

while(!isroot(x))

{

int y=fa[x],z=fa[y];

if(!isroot(y))

{

if(c[y][0]==x^c[z][0]==y)rotate(x);

else rotate(y);

}

rotate(x);

}

void access(int x)

{

for(int t=0;x;t=x,x=fa[x])

{

splay(x);c[x][1]=t;update(x);

}

void makeroot(int x)

{

access(x);splay(x);rev[x]^=1;

}

void link(int x,int y)

{

makeroot(x);fa[x]=y;

}

void cut(int x,int y)

{

makeroot(x);access(y);splay(y);

c[y][0]=fa[x]=0;

}

int find(int x)

{

access(x);splay(x);

while(c[x][0])x=c[x][0];

return x;

}

int query(int x,int y)

{

makeroot(x);access(y);splay(y);

return mn[y];

}

void insert(int l,int r,int x,int &y,int val)

{

y=++sz;

sum[y]=sum[x]+1;

if(l==r)return;

ls[y]=ls[x];rs[y]=rs[x];

int mid=(l+r)>>1;

if(val<=mid)insert(l,mid,ls[x],ls[y],val);

else insert(mid+1,r,rs[x],rs[y],val);

}

int query(int l,int r,int x,int y,int val)

{

if(r==val)return sum[y]-sum[x];

int mid=(l+r)>>1;

if(val<=mid)return query(l,mid,ls[x],ls[y],val);

else return sum[ls[y]]-sum[ls[x]]+query(mid+1,r,rs[x],rs[y],val);

}

void pre()

{

tot=n;

for(int i=1;i<=m;i++)

{

int u=e[i].u,v=e[i].v;

if(u==v)

{

st[i]=i;continue;

}

if(find(u)==find(v))

{

int t=query(u,v),x=val[t];

st[i]=x;

cut(e[x].u,t);cut(e[x].v,t);

}

tot++;

mn[tot]=tot;val[tot]=i;

link(u,tot);link(v,tot);

}

for(int i=1;i<=m;i++)

insert(0,m,root[i-1],root[i],st[i]);

}

void solve()

{

for(int i=1;i<=Q;i++)

{

int l=read(),r=read();

if(type)l^=lastans,r^=lastans;

lastans=n-query(0,m,root[l-1],root[r],l-1);

printf("%d\n",lastans);

}

int main()

{

n=read();m=read();Q=read();type=read();

val[0]=inf;

for(int i=1;i<=n;i++)mn[i]=i,val[i]=inf;

for(int i=1;i<=m;i++)

e[i].u=read(),e[i].v=read();

pre();

solve();

return 0;

}

« 「BZOJ3551」[ONTAK2010] Peaks加强版「BZOJ3282」Tree »

Flandre·Scarlet

ntr哪里hentai了。
不就是污嘛。

-D-Z-N-

路过这道题，也真是hentai啊……

hzwer.com _ Home | http://hzwer.com

「BZOJ3514」Codechef MARCH14 GERALD07加强版

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论