作者归档：Eurce

[POJ 3368]

说好的RMQ问题，结果又用线段树A了…

题意是：一个长度为n(1<=n<=100000)的非递减序列，共q(1<=1<=100000)次询问，求下标(l,h)范围内出现最频繁的元素的次数。一开始照着RMQ问题想，还看了个ST算法（O(NlgN)预处理，O(1)在线查询），结果也没想明白怎么用。又回头想了下，发现线段树是可以用的。由于序列非递减，连续的相同元素压缩成一个点作为线段树叶结点，记录元素在原数组中的下标范围；树分叉结点则保存子树下最频繁次数值，插入时则是按照压缩后的点编号进行处理，由此建树O(NlgN)，每次查询是O(lgN)。

#include<cstdio>
#include<cstring>

int n,q,a[100001],b[100000][2],bl,ml;

struct node
{
	int l,h,d;
	node *lc,*rc;
}mem[200000],*root;

void ins(int e,int L,int R,node *p)
{
	if(L==R)
	{
		p->l=b[e][0];
		p->h=b[e][1];
		p->d=p->h-p->l+1;
		return;
	}
	int m=L+R>>1;
	if(!p->lc)
	{
		p->lc=&mem[ml++];
		p->lc->l=p->lc->h=0;
		p->lc->lc=p->lc->rc=0;
		p->lc->d=0;
		p->rc=&mem[ml++];
		p->rc->l=p->rc->h=0;
		p->rc->lc=p->rc->rc=0;
		p->rc->d=0;
	}
	if(e<=m)
	{
		ins(e,L,m,p->lc);
		if(p->lc->l) p->l=p->lc->l;
		if(p->lc->d>p->d) p->d=p->lc->d;
	}
	else
	{
		ins(e,m+1,R,p->rc);
		if(p->rc->h) p->h=p->rc->h;
		if(p->rc->d>p->d) p->d=p->rc->d;
	}
}

int que(int l,int h,node *p)
{
	if(!p->lc) return h-l+1;
	if(l==p->l&&h==p->h) return p->d;
	int m=p->lc->h;
	if(h<=m) return que(l,h,p->lc);
	if(l>m) return que(l,h,p->rc);
	int a=que(l,m,p->lc),b=que(m+1,h,p->rc);
	return a>b?a:b;
}

bool input()
{
	ml=bl=0;
	int i,j,k,L,R;
	if(scanf("%d%d",&n,&q)!=2) return 0;
	for(i=0;i<n;i++) scanf("%d",a+i);
	a[n++]=100001;
	for(i=1,k=0;i<n;i++)
	{
		if(a[i]!=a[i-1])
		{
			b[bl][0]=k+1;
			b[bl][1]=i;
			k=i;
			bl++;
		}
	}
	root=&mem[ml++];
	root->l=root->h=root->d=0;
	root->lc=root->rc=0;
	L=0;
	R=bl-1;
	for(i=0;i<bl;i++) ins(i,L,R,root);
	return 1;
}

void solve()
{
	int l,h;
	while(q--)
	{
		scanf("%d%d",&l,&h);
		printf("%d\n",que(l,h,root));
	}
}

int main()
{
	while(input()) solve();
	return 0;
}

#include<cstdio>

#include<cstring>

int n,q,a[100001],b[100000][2],bl,ml;

struct node

{

int l,h,d;

node *lc,*rc;

}mem[200000],*root;

void ins(int e,int L,int R,node *p)

{

if(L==R)

{

p->l=b[e][0];

p->h=b[e][1];

p->d=p->h-p->l+1;

return;

}

int m=L+R>>1;

if(!p->lc)

{

p->lc=&mem[ml++];

p->lc->l=p->lc->h=0;

p->lc->lc=p->lc->rc=0;

p->lc->d=0;

p->rc=&mem[ml++];

p->rc->l=p->rc->h=0;

p->rc->lc=p->rc->rc=0;

p->rc->d=0;

}

if(e<=m)

{

ins(e,L,m,p->lc);

if(p->lc->l) p->l=p->lc->l;

if(p->lc->d>p->d) p->d=p->lc->d;

}

else

{

ins(e,m+1,R,p->rc);

if(p->rc->h) p->h=p->rc->h;

if(p->rc->d>p->d) p->d=p->rc->d;

}

int que(int l,int h,node *p)

{

if(!p->lc) return h-l+1;

if(l==p->l&&h==p->h) return p->d;

int m=p->lc->h;

if(h<=m) return que(l,h,p->lc);

if(l>m) return que(l,h,p->rc);

int a=que(l,m,p->lc),b=que(m+1,h,p->rc);

return a>b?a:b;

}

bool input()

{

ml=bl=0;

int i,j,k,L,R;

if(scanf("%d%d",&n,&q)!=2) return 0;

for(i=0;i<n;i++) scanf("%d",a+i);

a[n++]=100001;

for(i=1,k=0;i<n;i++)

{

if(a[i]!=a[i-1])

{

b[bl][0]=k+1;

b[bl][1]=i;

k=i;

bl++;

}

root=&mem[ml++];

root->l=root->h=root->d=0;

root->lc=root->rc=0;

L=0;

R=bl-1;

for(i=0;i<bl;i++) ins(i,L,R,root);

return 1;

}

void solve()

{

int l,h;

while(q--)

{

scanf("%d%d",&l,&h);

printf("%d\n",que(l,h,root));

}

int main()

{

while(input()) solve();

return 0;

}

[POJ 1151]

发表回复

Atlantis

本来是属于线段树的，但数据范围太小，硬是用暴力A掉了 -____-##

相比之前的好题……本题简直可以用“丑陋”来形容……比起线段树的运用和构思算法本身，更麻烦的反而是坐标离散化，而且由于POJ本身的问题，G++对double处理有缺陷（后来发现是输入用%lf输出用%f），转用C++后，对STL的编译又和G++的不一样……结果就是写好程序后各种卡编译错误……

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;

int n,a[201],el,t,xl,yl;
double sum,x[200],y[200];

struct node
{
	double e;
	int i;
	bool operator < (const node &p) const
	{
		return e<p.e;
	}
};

struct edge
{
	double x1,x2,y;
	int x1i,x2i,yi,c;
	bool operator < (const edge &p) const
	{
		return y<p.y;
	}
}e[200];

inline void adde(double x1,double y1,double x2,double y2)
{
	e[el].x1=x1; e[el].x2=x2; e[el].y=y1; e[el].c=1; el++;
	e[el].x1=x1; e[el].x2=x2; e[el].y=y2; e[el].c=-1; el++;
	x[xl++]=x1; x[xl++]=x2;
	y[yl++]=y1; y[yl++]=y2;
}

int main()
{
	int i,j,k,l;
	double x1,y1,x2,y2;
	node p;
	while(~scanf("%d",&n)&&n)
	{
		el=0;
		sum=0;
		xl=yl=0;
		set<node>SX,SY;
		set<node>::iterator sit;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			adde(x1,y1,x2,y2);
		}
		sort(e,e+el);
		sort(x,x+xl);
		sort(y,y+yl);
		for(i=j=1;i<xl;i++)
			if(x[i]!=x[i-1]) x[j++]=x[i];
		xl=j;
		for(i=0;i<xl;i++)
		{
			p.e=x[i];
			p.i=i;
			SX.insert(p);
		}
		for(i=j=1;i<yl;i++)
			if(y[i]!=y[i-1]) y[j++]=y[i];
		yl=j;
		for(i=0;i<yl;i++)
		{
			p.e=y[i];
			p.i=i;
			SY.insert(p);
		}
		for(i=0;i<el;i++)
		{
			p.e=e[i].x1;
			e[i].x1i=SX.find(p)->i;
			p.e=e[i].x2;
			e[i].x2i=SX.find(p)->i;
			p.e=e[i].y;
			e[i].yi=SY.find(p)->i;
		}
		memset(a,0,sizeof a);
		for(i=0;i<el&&e[i].yi==e[0].yi;i++)
		{
			a[e[i].x1i]+=e[i].c;
			a[e[i].x2i]-=e[i].c;
		}
		while(i<el)
		{
			y1=y[e[i-1].yi];
			y2=y[e[i].yi];
			for(j=k=0;j<=xl;j++)
			{
				if(a[j])
				{
					k+=a[j];
					if(k-a[j]==0) x1=x[j];
					else if(k==0)
					{
						x2=x[j];
						sum+=(x2-x1)*(y2-y1);
					}
				}
			}
			for(l=e[i].yi;i<el&&e[i].yi==l;i++)
			{
				a[e[i].x1i]+=e[i].c;
				a[e[i].x2i]-=e[i].c;
			}
		}
		printf("Test case #%d\n",++t);
		printf("Total explored area: %.2lf\n",sum);
		puts("");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include<cstdio>

#include<cstring>

#include<set>

#include<algorithm>

using namespace std;

int n,a[201],el,t,xl,yl;

double sum,x[200],y[200];

struct node

{

double e;

int i;

bool operator < (const node &p) const

{

return e<p.e;

}

};

struct edge

{

double x1,x2,y;

int x1i,x2i,yi,c;

bool operator < (const edge &p) const

{

return y<p.y;

}

}e[200];

inline void adde(double x1,double y1,double x2,double y2)

{

e[el].x1=x1; e[el].x2=x2; e[el].y=y1; e[el].c=1; el++;

e[el].x1=x1; e[el].x2=x2; e[el].y=y2; e[el].c=-1; el++;

x[xl++]=x1; x[xl++]=x2;

y[yl++]=y1; y[yl++]=y2;

}

int main()

{

int i,j,k,l;

double x1,y1,x2,y2;

node p;

while(~scanf("%d",&n)&&n)

{

el=0;

sum=0;

xl=yl=0;

set<node>SX,SY;

set<node>::iterator sit;

for(i=0;i<n;i++)

{

scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

adde(x1,y1,x2,y2);

}

sort(e,e+el);

sort(x,x+xl);

sort(y,y+yl);

for(i=j=1;i<xl;i++)

if(x[i]!=x[i-1]) x[j++]=x[i];

xl=j;

for(i=0;i<xl;i++)

{

p.e=x[i];

p.i=i;

SX.insert(p);

}

for(i=j=1;i<yl;i++)

if(y[i]!=y[i-1]) y[j++]=y[i];

yl=j;

for(i=0;i<yl;i++)

{

p.e=y[i];

p.i=i;

SY.insert(p);

}

for(i=0;i<el;i++)

{

p.e=e[i].x1;

e[i].x1i=SX.find(p)->i;

p.e=e[i].x2;

e[i].x2i=SX.find(p)->i;

p.e=e[i].y;

e[i].yi=SY.find(p)->i;

}

memset(a,0,sizeof a);

for(i=0;i<el&&e[i].yi==e[0].yi;i++)

{

a[e[i].x1i]+=e[i].c;

a[e[i].x2i]-=e[i].c;

}

while(i<el)

{

y1=y[e[i-1].yi];

y2=y[e[i].yi];

for(j=k=0;j<=xl;j++)

{

if(a[j])

{

k+=a[j];

if(k-a[j]==0) x1=x[j];

else if(k==0)

{

x2=x[j];

sum+=(x2-x1)*(y2-y1);

}

for(l=e[i].yi;i<el&&e[i].yi==l;i++)

{

a[e[i].x1i]+=e[i].c;

a[e[i].x2i]-=e[i].c;

}

printf("Test case #%d\n",++t);

printf("Total explored area: %.2lf\n",sum);

puts("");

}

return 0;

}

[POJ 2352]

发表回复

Stars

继续线段树+树状数组练手题。

这题先对某坐标轴方向排序后，便能将二维降为一维处理了。没太大难度。

线段树：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ml,cnt[15000];

struct star
{
	int x,y;
	bool operator <(const star &p) const
	{
		if(y<p.y) return 1;
		if(y>p.y) return 0;
		if(x<p.x) return 1;
		return 0;
	}
}s[15000];

struct node
{
	bool b;
	int d;
	node *l,*r;
}mem[64000],*root;

inline void ins(int i)
{
	int L=0,R=32000,m,lev=0;
	node *p=root;
	while(1)
	{
		m=L+R>>1;
		p->d++;
		if(L==R)
		{
			lev+=p->d-1;
			cnt[lev]++;
			break;
		}
		if(p->b)
		{
			p->b=0;
			p->l=&mem[ml++];
			p->l->b=1;
			p->l->d=0;
			p->r=&mem[ml++];
			p->r->b=1;
			p->r->d=0;
		}
		if(i<=m)
		{
			R=m;
			p=p->l;
		}
		else
		{
			lev+=p->l->d;
			L=m+1;
			p=p->r;
		}
	}
}

int main()
{
	int i,j,k;
	while(~scanf("%d",&n))
	{
		ml=0;
		root=&mem[ml++];
		root->b=1;
		root->d=0;
		memset(cnt,0,sizeof cnt);
		for(i=0;i<n;i++) scanf("%d%d",&s[i].x,&s[i].y);
		sort(s,s+n);
		for(i=0;i<n;i++) ins(s[i].x);
		for(i=0;i<n;i++) printf("%d\n",cnt[i]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,ml,cnt[15000];

struct star

{

int x,y;

bool operator <(const star &p) const

{

if(y<p.y) return 1;

if(y>p.y) return 0;

if(x<p.x) return 1;

return 0;

}

}s[15000];

struct node

{

bool b;

int d;

node *l,*r;

}mem[64000],*root;

inline void ins(int i)

{

int L=0,R=32000,m,lev=0;

node *p=root;

while(1)

{

m=L+R>>1;

p->d++;

if(L==R)

{

lev+=p->d-1;

cnt[lev]++;

break;

}

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->l->b=1;

p->l->d=0;

p->r=&mem[ml++];

p->r->b=1;

p->r->d=0;

}

if(i<=m)

{

R=m;

p=p->l;

}

else

{

lev+=p->l->d;

L=m+1;

p=p->r;

}

int main()

{

int i,j,k;

while(~scanf("%d",&n))

{

ml=0;

root=&mem[ml++];

root->b=1;

root->d=0;

memset(cnt,0,sizeof cnt);

for(i=0;i<n;i++) scanf("%d%d",&s[i].x,&s[i].y);

sort(s,s+n);

for(i=0;i<n;i++) ins(s[i].x);

for(i=0;i<n;i++) printf("%d\n",cnt[i]);

}

return 0;

}

树状数组：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,c[32002],cnt[15000];

struct star
{
	int x,y;
	bool operator < (const star &p) const
	{
		if(y<p.y) return 1;
		if(y>p.y) return 0;
		if(x<p.x) return 1;
		return 0;
	}
}a[15000];

inline void add(int x)
{
	int i;
	for(i=1;x<32002;i<<=1)
	{
		if(x&i)
		{
			c[x]++;
			x+=i;
		}
	}
}

inline int que(int x)
{
	int i,sum=0;
	for(i=1;x;i<<=1)
	{
		if(x&i)
		{
			sum+=c[x];
			x-=i;
		}
	}
	return sum;
}

int main()
{
	int i,j,k;
	while(~scanf("%d",&n))
	{
		memset(c,0,sizeof c);
		memset(cnt,0,sizeof cnt);
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&a[i].x,&a[i].y);
			a[i].x++;
			a[i].y++;
		}
		sort(a,a+n);
		for(i=0;i<n;i++)
		{
			add(a[i].x);
			cnt[que(a[i].x)-1]++;
		}
		for(i=0;i<n;i++) printf("%d\n",cnt[i]);
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,c[32002],cnt[15000];

struct star

{

int x,y;

bool operator < (const star &p) const

{

if(y<p.y) return 1;

if(y>p.y) return 0;

if(x<p.x) return 1;

return 0;

}

}a[15000];

inline void add(int x)

{

int i;

for(i=1;x<32002;i<<=1)

{

if(x&i)

{

c[x]++;

x+=i;

}

inline int que(int x)

{

int i,sum=0;

for(i=1;x;i<<=1)

{

if(x&i)

{

sum+=c[x];

x-=i;

}

return sum;

}

int main()

{

int i,j,k;

while(~scanf("%d",&n))

{

memset(c,0,sizeof c);

memset(cnt,0,sizeof cnt);

for(i=0;i<n;i++)

{

scanf("%d%d",&a[i].x,&a[i].y);

a[i].x++;

a[i].y++;

}

sort(a,a+n);

for(i=0;i<n;i++)

{

add(a[i].x);

cnt[que(a[i].x)-1]++;

}

for(i=0;i<n;i++) printf("%d\n",cnt[i]);

}

return 0;

}

[POJ 1195]

发表回复

Mobile phones

二维树状数组。

推出一维的后便很易想出二维解法了，单次更新/查询的时间复杂度升为O(lgN*lgN)，因此还是可以接受的。

久违的1A。。。

int s,c[1025][1025];

void add()
{
	int i,j,x,y,yy,a;
	scanf("%d%d%d",&x,&y,&a);
	++x; ++y;
	for(i=1;x<=s;i<<=1)
	{
		if(x&i)
		{
			for(j=1,yy=y;yy<=s;j<<=1)
			{
				if(yy&j)
				{
					c[x][yy]+=a;
					yy+=j;
				}
			}
			x+=i;
		}
	}
}

int val(int x,int y)
{
	int i,j,k=0,yy;
	for(i=1;x;i<<=1)
	{
		if(x&i)
		{
			for(j=1,yy=y;yy;j<<=1)
			{
				if(yy&j)
				{
					k+=c[x][yy];
					yy-=j;
				}
			}
			x-=i;
		}
	}
	return k;
}

void que()
{
	int l,b,r,t;
	scanf("%d%d%d%d",&l,&b,&r,&t);
	printf("%d\n",val(r+1,t+1)-val(l,t+1)-val(r+1,b)+val(l,b));
}

int main()
{
	int i;
	while(~scanf("%*d%d",&s))
	{
		memset(c,0,sizeof c);
		while(scanf("%d",&i))
		{
			if(i==1) add();
			else if(i==2) que();
			else break;
		}
	}
	return 0;
}

int s,c[1025][1025];

void add()

{

int i,j,x,y,yy,a;

scanf("%d%d%d",&x,&y,&a);

++x; ++y;

for(i=1;x<=s;i<<=1)

{

if(x&i)

{

for(j=1,yy=y;yy<=s;j<<=1)

{

if(yy&j)

{

c[x][yy]+=a;

yy+=j;

}

x+=i;

}

int val(int x,int y)

{

int i,j,k=0,yy;

for(i=1;x;i<<=1)

{

if(x&i)

{

for(j=1,yy=y;yy;j<<=1)

{

if(yy&j)

{

k+=c[x][yy];

yy-=j;

}

x-=i;

}

return k;

}

void que()

{

int l,b,r,t;

scanf("%d%d%d%d",&l,&b,&r,&t);

printf("%d\n",val(r+1,t+1)-val(l,t+1)-val(r+1,b)+val(l,b));

}

int main()

{

int i;

while(~scanf("%*d%d",&s))

{

memset(c,0,sizeof c);

while(scanf("%d",&i))

{

if(i==1) add();

else if(i==2) que();

else break;

}

return 0;

}

[POJ 3321]

发表回复

Apple Tree

树状数组例题。

“用DFS求出树结点对应的区间范围”比较难想……后面的区间值修改和查询都比较简单了。分别用了线段树和树状数组进行了求解。

线段树：

#include<cstdio>
#include<cstring>

int n,m,hd[100000],b[100000],nt[100000][2],el,t,ml;
char s[2];

struct edge
{
	int j,p;
}e[200000];

struct node
{
	bool b;
	int sum;
	node *l,*r;
}mem[400000],*root;

inline void adde(int i,int j)
{
	e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

void dfs(int i)
{
	int j,k,l;
	nt[i][0]=t++;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		b[j]=1;
		dfs(j);
	}
	nt[i][1]=t++;
}

void add(int e,int c)
{
	int L=0,R=t,m;
	node *p=root;
	while(1)
	{
		p->sum+=c;
		if(L==R) break;
		m=L+R>>1;
		if(p->b)
		{
			p->b=0;
			p->l=&mem[ml++];
			p->r=&mem[ml++];
			p->l->b=p->r->b=1;
			p->l->sum=p->r->sum=0;
		}
		if(e<=m)
		{
			R=m;
			p=p->l;
		}
		else
		{
			L=m+1;
			p=p->r;
		}
	}
}

int que(int l,int r,int L,int R,node *p)
{
	int m=L+R>>1;
	if(p->b||l==L&&r==R) return p->sum;
	if(r<=m) return que(l,r,L,m,p->l);
	if(l>m) return que(l,r,m+1,R,p->r);
	return que(l,m,L,m,p->l)+que(m+1,r,m+1,R,p->r);
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d",&n))
	{
		el=t=ml=0;
		root=&mem[ml++];
		root->b=1;
		root->sum=0;
		memset(hd,-1,sizeof hd);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&j,&k);
			adde(j-1,k-1);
		}
		memset(b,0,sizeof b);
		b[0]=1;
		dfs(0);
		--t;
		for(i=0;i<n;i++)
			add(nt[i][0],1);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s%d",s,&i);
			--i;
			if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1],0,t,root));
			else
			{
				if(b[i]) add(nt[i][0],-1);
				else add(nt[i][0],1);
				b[i]^=1;
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include<cstdio>

#include<cstring>

int n,m,hd[100000],b[100000],nt[100000][2],el,t,ml;

char s[2];

struct edge

{

int j,p;

}e[200000];

struct node

{

bool b;

int sum;

node *l,*r;

}mem[400000],*root;

inline void adde(int i,int j)

{

e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

void dfs(int i)

{

int j,k,l;

nt[i][0]=t++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

b[j]=1;

dfs(j);

}

nt[i][1]=t++;

}

void add(int e,int c)

{

int L=0,R=t,m;

node *p=root;

while(1)

{

p->sum+=c;

if(L==R) break;

m=L+R>>1;

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->r=&mem[ml++];

p->l->b=p->r->b=1;

p->l->sum=p->r->sum=0;

}

if(e<=m)

{

R=m;

p=p->l;

}

else

{

L=m+1;

p=p->r;

}

int que(int l,int r,int L,int R,node *p)

{

int m=L+R>>1;

if(p->b||l==L&&r==R) return p->sum;

if(r<=m) return que(l,r,L,m,p->l);

if(l>m) return que(l,r,m+1,R,p->r);

return que(l,m,L,m,p->l)+que(m+1,r,m+1,R,p->r);

}

int main()

{

int i,j,k,l;

while(~scanf("%d",&n))

{

el=t=ml=0;

root=&mem[ml++];

root->b=1;

root->sum=0;

memset(hd,-1,sizeof hd);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

memset(b,0,sizeof b);

b[0]=1;

dfs(0);

--t;

for(i=0;i<n;i++)

add(nt[i][0],1);

scanf("%d",&m);

while(m--)

{

scanf("%s%d",s,&i);

--i;

if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1],0,t,root));

else

{

if(b[i]) add(nt[i][0],-1);

else add(nt[i][0],1);

b[i]^=1;

}

return 0;

}

树状数组：

#include<cstdio>
#include<cstring>

int n,m,hd[100000],el,b[100000],nt[100000][2],t,c[200001];
char s[2];

struct edge
{
	int j,p;
}e[200000];

inline void adde(int i,int j)
{
	e[el].j=j; e[el].p=hd[i]; hd[i]=el++;
	e[el].j=i; e[el].p=hd[j]; hd[j]=el++;
}

void dfs(int i)
{
	int j,l;
	nt[i][0]=t++;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		b[j]=1;
		dfs(j);
	}
	nt[i][1]=t++;
}

inline void add(int e,int d)
{
	int i;
	for(i=1;e<t;i<<=1)
	{
		if(e&i)
		{
			c[e]+=d;
			e+=i;
		}
	}
}

inline int val(int e)
{
	int i,j;
	for(i=1,j=0;e;i<<=1)
	{
		if(e&i)
		{
			j+=c[e];
			e-=i;
		}
	}
	return j;
}

inline int que(int l,int r)
{
	return val(r)-val(l-1);
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d",&n))
	{
		el=0;
		t=1;
		memset(hd,-1,sizeof hd);
		memset(c,0,sizeof c);
		for(i=1;i<n;i++)
		{
			scanf("%d%d",&j,&k);
			adde(j-1,k-1);
		}
		memset(b,0,sizeof b);
		b[0]=1;
		dfs(0);
		for(i=0;i<n;i++) add(nt[i][0],1);
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s%d",s,&i);
			--i;
			if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1]));
			else
			{
				if(b[i]) add(nt[i][0],-1);
				else add(nt[i][0],1);
				b[i]^=1;
			}
		}
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int n,m,hd[100000],el,b[100000],nt[100000][2],t,c[200001];

char s[2];

struct edge

{

int j,p;

}e[200000];

inline void adde(int i,int j)

{

e[el].j=j; e[el].p=hd[i]; hd[i]=el++;

e[el].j=i; e[el].p=hd[j]; hd[j]=el++;

}

void dfs(int i)

{

int j,l;

nt[i][0]=t++;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

b[j]=1;

dfs(j);

}

nt[i][1]=t++;

}

inline void add(int e,int d)

{

int i;

for(i=1;e<t;i<<=1)

{

if(e&i)

{

c[e]+=d;

e+=i;

}

inline int val(int e)

{

int i,j;

for(i=1,j=0;e;i<<=1)

{

if(e&i)

{

j+=c[e];

e-=i;

}

return j;

}

inline int que(int l,int r)

{

return val(r)-val(l-1);

}

int main()

{

int i,j,k,l;

while(~scanf("%d",&n))

{

el=0;

t=1;

memset(hd,-1,sizeof hd);

memset(c,0,sizeof c);

for(i=1;i<n;i++)

{

scanf("%d%d",&j,&k);

adde(j-1,k-1);

}

memset(b,0,sizeof b);

b[0]=1;

dfs(0);

for(i=0;i<n;i++) add(nt[i][0],1);

scanf("%d",&m);

while(m--)

{

scanf("%s%d",s,&i);

--i;

if(s[0]=='Q') printf("%d\n",que(nt[i][0],nt[i][1]));

else

{

if(b[i]) add(nt[i][0],-1);

else add(nt[i][0],1);

b[i]^=1;

}

return 0;

}

[POJ 2104]

发表回复

K-th Number

划分树。

题意是，给一个长度为n的数组，之后有m次询问，每次询问为三元组（l,r,k），问数组中第l到第r个元素间第k小的元素是什么。

又是一题很有意思的题目，常规解法的时间复杂度在这里是完全不可行的，必须预先建树后才能O(lgN)地回答每次询问。但看了划分树的建树思想后还是推了很久。

划分树是基于线段树的，其基本思想在于父节点上[L,R]区间上[l,r]中的第k小元素，如何O(1）时间地递推到左子树或右子树中，这样总共O(lgN)次后便能得到答案。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,a[100000],b[100000],sa[100000],el[2000000],ml,ell;

struct node
{
	int s;
	node *l,*r;
}mem[2000000],*root;

void init(int L,int R,node *p)
{
	int m=L+R>>1,e=0,i,j,k;
	p->s=ell;
	for(i=L;i<=R;i++)
	{
		e+=a[i]<=sa[m]?1:0;
		el[ell++]=e;
	}
	for(i=j=L,k=m+1;i<=R;i++)
	{
		if(a[i]<=sa[m]) b[j++]=a[i];
		else b[k++]=a[i];
	}
	memcpy(a+L,b+L,4*(R-L+1));
	if(L==R) return;
	p->l=&mem[ml++];
	p->r=&mem[ml++];
	init(L,m,p->l);
	init(m+1,R,p->r);
}

inline int calc(int l,int r,int k)
{
	int m,L=0,R=n-1,f;
	node *p=root;
	while(L!=R)
	{
		m=L+R>>1;
		if(!l) f=el[p->s+r];
		else f=el[p->s+r]-el[p->s+l-1];
		if(k<=f)
		{
			if(l) l=el[p->s+l-1];
			r=el[p->s+r]-1;
			p=p->l;
			R=m;
		}
		else
		{
			k-=f;
			if(l) l=l-el[p->s+l-1];
			r=r-el[p->s+r];
			p=p->r;
			L=m+1;
		}
	}
	return sa[L];
}

int main()
{
	int i,j,k;
	while(~scanf("%d%d",&n,&m))
	{
		ml=ell=0;
		root=&mem[ml++];
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sa[i]=a[i];
		}
		sort(sa,sa+n);
		init(0,n-1,root);
		while(m--)
		{
			scanf("%d%d%d",&i,&j,&k);
			printf("%d\n",calc(i-1,j-1,k));
		}
	}
	return 0;
}

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,a[100000],b[100000],sa[100000],el[2000000],ml,ell;

struct node

{

int s;

node *l,*r;

}mem[2000000],*root;

void init(int L,int R,node *p)

{

int m=L+R>>1,e=0,i,j,k;

p->s=ell;

for(i=L;i<=R;i++)

{

e+=a[i]<=sa[m]?1:0;

el[ell++]=e;

}

for(i=j=L,k=m+1;i<=R;i++)

{

if(a[i]<=sa[m]) b[j++]=a[i];

else b[k++]=a[i];

}

memcpy(a+L,b+L,4*(R-L+1));

if(L==R) return;

p->l=&mem[ml++];

p->r=&mem[ml++];

init(L,m,p->l);

init(m+1,R,p->r);

}

inline int calc(int l,int r,int k)

{

int m,L=0,R=n-1,f;

node *p=root;

while(L!=R)

{

m=L+R>>1;

if(!l) f=el[p->s+r];

else f=el[p->s+r]-el[p->s+l-1];

if(k<=f)

{

if(l) l=el[p->s+l-1];

r=el[p->s+r]-1;

p=p->l;

R=m;

}

else

{

k-=f;

if(l) l=l-el[p->s+l-1];

r=r-el[p->s+r];

p=p->r;

L=m+1;

}

return sa[L];

}

int main()

{

int i,j,k;

while(~scanf("%d%d",&n,&m))

{

ml=ell=0;

root=&mem[ml++];

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

sa[i]=a[i];

}

sort(sa,sa+n);

init(0,n-1,root);

while(m--)

{

scanf("%d%d%d",&i,&j,&k);

printf("%d\n",calc(i-1,j-1,k));

}

return 0;

}

[POJ 2482]

发表回复

Stars in Your Window

这题前面竟然是一封情信，字里行间都饱含作者的深情……于是又搜了下kinfkong，是位中大的前辈哦，都31岁结婚了。他博客里的文章也挺有意思的……

扯远了，回到题目本身吧。题面是：在二维平面上有N颗星星，各有一个亮度值c，问如果用一个长W宽H的矩形来括住某些星星，如何使窗口内星星亮度和最大。

说实在的，题目本身也出得非常巧妙。解题需要两次利用区间值求和的思想，即在[a,b]区间上加c，相当于在顺序遍历的基础上在a点加c，b+1点减c。第一次是在y轴方向上，若在(x,y)点处有一颗星星亮度为c，则在(x,y+H)上增加一颗亮度为-c的星星。这样，由y=0向上更新线段亮度值，便能将矩形区域求最大和转换成线段求最大和。第二次则是在x轴方向上的，对横坐标x亮度为c的星星，增加一颗x+W处亮度为-c的星星，这样便能进一步将线段最大和转换成点最大值。由此，便能利用线段树在每次插入星星的同时O(lgN)地更新最大亮度值了。

#include<cstdio>
#include<algorithm>
using namespace std;

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star
{
	LL w,h,c;
	bool operator < (const star &p) const
	{
		if(h==p.h&&w==p.w) return c<p.c;
		if(h==p.h) return w<p.w;
		return h<p.h;
	}
}s[20001];

struct node
{
	LL sm,ld,rd,mx;
	bool b;
	node *l,*r;
}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)
{
	if(L==R)
	{
		e+=p->sm;
		p->sm=p->ld=p->rd=p->mx=e;
		return;
	}
	LL m=L+R>>1;
	if(p->b)
	{
		p->b=0;
		p->l=&mem[ml++];
		p->l->b=1;
		p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;
		p->r=&mem[ml++];
		p->r->b=1;
		p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;
	}
	if(i<=m) ins(i,e,L,m,p->l);
	else ins(i,e,m+1,R,p->r);
	p->sm=p->l->sm+p->r->sm;
	p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;
	p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;
	p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;
	p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;
}

int main()
{
	LL i,j,k,L,R;
	while(~scanf("%lld%lld%lld",&n,&W,&H))
	{
		ml=sl=mx=wl=0;
		L=0x7fffffff;
		R=0;
		root=&mem[ml++];
		root->sm=root->ld=root->rd=root->mx=0;
		root->b=1;
		while(n--)
		{
			scanf("%lld%lld%lld",&i,&j,&k);
			w[wl++]=i;
			L=i<L?i:L;
			R=(i+W)>R?(i+W):R;
			s[sl].w=i; s[sl].h=j; s[sl].c=k;
			sl++;
			s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;
			sl++;
		}
		sort(s,s+sl);
		sort(w,w+wl);
		for(i=j=1;i<wl;i++)
			if(w[i]!=w[j-1]) w[j++]=w[i];
		wl=j;
		for(i=0;i<sl;i++)
		{
			ins(s[i].w,s[i].c,L,R,root);
			ins(s[i].w+W,-s[i].c,L,R,root);
			mx=root->mx>mx?root->mx:mx;
		}
		printf("%lld\n",mx);
	}
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define LL long long

LL n,W,H,sl,ml,mx,w[10000],wl;

struct star

{

LL w,h,c;

bool operator < (const star &p) const

{

if(h==p.h&&w==p.w) return c<p.c;

if(h==p.h) return w<p.w;

return h<p.h;

}

}s[20001];

struct node

{

LL sm,ld,rd,mx;

bool b;

node *l,*r;

}mem[1000000],*root;

void ins(LL i,LL e,LL L,LL R,node *p)

{

if(L==R)

{

e+=p->sm;

p->sm=p->ld=p->rd=p->mx=e;

return;

}

LL m=L+R>>1;

if(p->b)

{

p->b=0;

p->l=&mem[ml++];

p->l->b=1;

p->l->sm=p->l->ld=p->l->rd=p->l->mx=0;

p->r=&mem[ml++];

p->r->b=1;

p->r->sm=p->r->ld=p->r->rd=p->r->mx=0;

}

if(i<=m) ins(i,e,L,m,p->l);

else ins(i,e,m+1,R,p->r);

p->sm=p->l->sm+p->r->sm;

p->ld=p->l->ld>p->l->sm+p->r->ld?p->l->ld:p->l->sm+p->r->ld;

p->rd=p->r->rd>p->r->sm+p->l->rd?p->r->rd:p->r->sm+p->l->rd;

p->mx=p->l->mx>p->r->mx?p->l->mx:p->r->mx;

p->mx=p->mx>p->l->rd+p->r->ld?p->mx:p->l->rd+p->r->ld;

}

int main()

{

LL i,j,k,L,R;

while(~scanf("%lld%lld%lld",&n,&W,&H))

{

ml=sl=mx=wl=0;

L=0x7fffffff;

R=0;

root=&mem[ml++];

root->sm=root->ld=root->rd=root->mx=0;

root->b=1;

while(n--)

{

scanf("%lld%lld%lld",&i,&j,&k);

w[wl++]=i;

L=i<L?i:L;

R=(i+W)>R?(i+W):R;

s[sl].w=i; s[sl].h=j; s[sl].c=k;

sl++;

s[sl].w=i; s[sl].h=j+H; s[sl].c=-k;

sl++;

}

sort(s,s+sl);

sort(w,w+wl);

for(i=j=1;i<wl;i++)

if(w[i]!=w[j-1]) w[j++]=w[i];

wl=j;

for(i=0;i<sl;i++)

{

ins(s[i].w,s[i].c,L,R,root);

ins(s[i].w+W,-s[i].c,L,R,root);

mx=root->mx>mx?root->mx:mx;

}

printf("%lld\n",mx);

}

return 0;

}

不过题目分类里写得这题属于“静态二叉检索树”。。。。这个暂时还没想出来该怎么写。。。

[POJ 2750]

发表回复

Potted Flower

分类表里最后一道线段树了。

题意大概是：有一个环，环上有N个整数，求在每次更新环上某个值后，环（除整个环外）任意弧上最大的整数和。

乍看下去，虽然提示是用线段树，但还是想了很久也没思路。再看了下输入规模，N最大10^5，更新次数M也是10^5，于是单次更新的处理时间只能是O(lgN)的。这样便能看出来是每次更新都在线段树上作O(lgN)深度的线段信息更新，再由根结点信息得到结果。

这里由左右子结点得到父结点信息的题推关系还是挺麻烦的……要考虑左连续区间最值和对应的最右元素位置，右连续区间最值和对应的最左元素位置，以及区间中任意子连续区间上的最值，再加上区间上全部整数和，总共是6个量。

这里要记录左右最值区间对应边界位置是因为，最后在根结点处计算时是可以将最右和最左看作连续的（环的性质），这样如果子结点上左右区间有重叠时，直接相加便会出错了，因此记录边界便能在仅当左右区间不重叠时才计算值。

另外这题要求不能取整个环上所有元素，因此实际上求的是最小弧，再用全部整数和减去最小值便能得到最大弧了。

#include<cstdio>
#include<cstring>

int n,m,d[100000],ml;

struct node
{
	int s,ld,rd,md,lr,rl;
	node *l,*r;
}mem[200000],*root;

void ins(int L,int R,node *p,int i=-1)
{
	int m=L+R>>1;
	if(L==R)
	{
		p->s=d[m];
		p->ld=p->rd=p->md=d[m];
		p->lr=p->rl=m;
		return;
	}
	if(i==-1)
	{
		p->l=&mem[ml++];
		p->r=&mem[ml++];
		ins(L,m,p->l);
		ins(m+1,R,p->r);
	}
	else if(i<=m) ins(L,m,p->l,i);
	else ins(m+1,R,p->r,i);
	p->s=p->l->s+p->r->s;
	if(p->l->ld<=p->l->s+p->r->ld)
	{
		p->ld=p->l->ld;
		p->lr=p->l->lr;
	}
	else
	{
		p->ld=p->l->s+p->r->ld;
		p->lr=p->r->lr;
	}
	if(p->r->rd<=p->r->s+p->l->rd)
	{
		p->rd=p->r->rd;
		p->rl=p->r->rl;
	}
	else
	{
		p->rd=p->r->s+p->l->rd;
		p->rl=p->l->rl;
	}
	p->md=p->l->rd+p->r->ld;
	p->md=p->md<p->l->md?p->md:p->l->md;
	p->md=p->md<p->r->md?p->md:p->r->md;
}

inline int calc(int i)
{
	ins(0,n-1,root,i);
	int e=root->md,m=n-1>>1;
	e=e<root->l->ld+root->r->rd?e:root->l->ld+root->r->rd;
	if(root->r->lr<root->r->rl)
		e=e<root->l->s+root->r->ld+root->r->rd?e:root->l->s+root->r->ld+root->r->rd;
	if(root->l->lr<root->l->rl)
		e=e<root->r->s+root->l->ld+root->l->rd?e:root->r->s+root->l->ld+root->l->rd;
	return root->s-e;
}

int main()
{
	int i,j;
	while(~scanf("%d",&n))
	{
		ml=0;
		root=&mem[ml++];
		for(i=0;i<n;i++) scanf("%d",&d[i]);
		scanf("%d",&m);
		ins(0,n-1,root);
		while(m--)
		{
			scanf("%d%d",&i,&j);
			d[i-1]=j;
			printf("%d\n",calc(i-1));
		}
	}
	return 0;
}

#include<cstdio>

#include<cstring>

int n,m,d[100000],ml;

struct node

{

int s,ld,rd,md,lr,rl;

node *l,*r;

}mem[200000],*root;

void ins(int L,int R,node *p,int i=-1)

{

int m=L+R>>1;

if(L==R)

{

p->s=d[m];

p->ld=p->rd=p->md=d[m];

p->lr=p->rl=m;

return;

}

if(i==-1)

{

p->l=&mem[ml++];

p->r=&mem[ml++];

ins(L,m,p->l);

ins(m+1,R,p->r);

}

else if(i<=m) ins(L,m,p->l,i);

else ins(m+1,R,p->r,i);

p->s=p->l->s+p->r->s;

if(p->l->ld<=p->l->s+p->r->ld)

{

p->ld=p->l->ld;

p->lr=p->l->lr;

}

else

{

p->ld=p->l->s+p->r->ld;

p->lr=p->r->lr;

}

if(p->r->rd<=p->r->s+p->l->rd)

{

p->rd=p->r->rd;

p->rl=p->r->rl;

}

else

{

p->rd=p->r->s+p->l->rd;

p->rl=p->l->rl;

}

p->md=p->l->rd+p->r->ld;

p->md=p->md<p->l->md?p->md:p->l->md;

p->md=p->md<p->r->md?p->md:p->r->md;

}

inline int calc(int i)

{

ins(0,n-1,root,i);

int e=root->md,m=n-1>>1;

e=e<root->l->ld+root->r->rd?e:root->l->ld+root->r->rd;

if(root->r->lr<root->r->rl)

e=e<root->l->s+root->r->ld+root->r->rd?e:root->l->s+root->r->ld+root->r->rd;

if(root->l->lr<root->l->rl)

e=e<root->r->s+root->l->ld+root->l->rd?e:root->r->s+root->l->ld+root->l->rd;

return root->s-e;

}

int main()

{

int i,j;

while(~scanf("%d",&n))

{

ml=0;

root=&mem[ml++];

for(i=0;i<n;i++) scanf("%d",&d[i]);

scanf("%d",&m);

ins(0,n-1,root);

while(m--)

{

scanf("%d%d",&i,&j);

d[i-1]=j;

printf("%d\n",calc(i-1));

}

return 0;

}

[POJ 3678]

发表回复

Katu Puzzle

很神奇的2-SAT问题。找了一篇赵爽的《2-SAT解法浅析》。作者是高中生啊，查了下却发现是05年交大ACM总冠军队的成员……Orz

题目抽象出来后就不难做了，建一个含2*N个点的有向图，边由逻辑运算给出，边(u,v)表示选了u点则必须选v。编号为i的点对应图中i*2和i*2+1的两个点，分别表示i点取值为1、0。点A、B间由逻辑运算生成的边如下：

A & B == 1: 增加边(A*2+1,A*2)和(B*2+1,B*2);

A & B == 0: 增加边(A*2,B*2+1)和(B*2,A*2+1);

A | B == 1: 增加边(B*2+1,A*2)和(A*2+1,B*2);

A | B == 0: 增加边(A*2,A*2+1)和(B*2,B*2+1);

A ^ B == 1: 增加边(A*2,B*2+1)、(B*2+1,A*2)、(A*2+1,B*2)和(B*2,A*2+1);

A ^ B == 0: 增加边(A*2,B*2)、(B*2,A*2)、(A*2+1,B*2+1)和(B*2+1,A*2+1);

建好图后求强连通分量。最后判断是否对所有的i=0:N-1,是否有i*2和i*2+1不在同一强连通分量中，若成立则原问题有解，否则无解。

这里被 A & B == 1 和 A | B == 0 卡了一下……不可取的点直接引入必败边的做法非常巧妙……

同样分别使用了两次DFS和tarjan来求强连通分量，代码分别如下：

#include<cstdio>
#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000],v[2000],vl;
char s[4];
int xa,xb,c;

struct edge
{
	int j,p;
}e[4000000],er[4000000];

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

inline void adde()
{
	int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;
	if(s[0]=='A')
	{
		if(c==1)
		{
			e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;
			er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
		}
		else
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
	else if(s[0]=='O')
	{
		if(c==1)
		{
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
		}
		else
		{
			e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
		}
	}
	else
	{
		if(c==1)
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
		else
		{
			e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
}

void DFS(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(b[j]) continue;
		DFS(j);
	}
	v[vl++]=i;
}

void DFSr(int i)
{
	int j,k,l;
	b[i]=1;
	for(l=hdr[i];l!=-1;l=er[l].p)
	{
		j=er[l].j;
		if(b[j]) continue;
		un(i,j);
		DFSr(j);
	}
}

int chk()
{
	int i;
	for(i=0;i<n;i++)
		if(fi(i*2)==fi(i*2+1)) return 0;
	return 1;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		el=erl=vl=0;
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(f,-1,sizeof f);
		while(m--)
		{
			scanf("%d%d%d%s",&xa,&xb,&c,s);
			adde();
		}
		memset(b,0,sizeof b);
		for(i=0;i<2*n;i++)
			if(!b[i]) DFS(i);
		memset(b,0,sizeof b);
		for(i=vl-1;i>-1;i--)
			if(!b[v[i]]) DFSr(v[i]);
		puts(chk()?"YES":"NO");
	}
	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

#include<cstdio>

#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000],v[2000],vl;

char s[4];

int xa,xb,c;

struct edge

{

int j,p;

}e[4000000],er[4000000];

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

inline void adde()

{

int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;

if(s[0]=='A')

{

if(c==1)

{

e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;

er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

}

else

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else if(s[0]=='O')

{

if(c==1)

{

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

}

else

{

e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

}

else

{

if(c==1)

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else

{

e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

void DFS(int i)

{

int j,k,l;

b[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(b[j]) continue;

DFS(j);

}

v[vl++]=i;

}

void DFSr(int i)

{

int j,k,l;

b[i]=1;

for(l=hdr[i];l!=-1;l=er[l].p)

{

j=er[l].j;

if(b[j]) continue;

un(i,j);

DFSr(j);

}

int chk()

{

int i;

for(i=0;i<n;i++)

if(fi(i*2)==fi(i*2+1)) return 0;

return 1;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

el=erl=vl=0;

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(f,-1,sizeof f);

while(m--)

{

scanf("%d%d%d%s",&xa,&xb,&c,s);

adde();

}

memset(b,0,sizeof b);

for(i=0;i<2*n;i++)

if(!b[i]) DFS(i);

memset(b,0,sizeof b);

for(i=vl-1;i>-1;i--)

if(!b[v[i]]) DFSr(v[i]);

puts(chk()?"YES":"NO");

}

return 0;

}

#include<cstdio>
#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000];
int st[2000],sl,stb[2000],low[2000];
char s[4];
int xa,xb,c;

struct edge
{
	int j,p;
}e[4000000],er[4000000];

int fi(int i)
{
	if(f[i]<0) return i;
	else return f[i]=fi(f[i]);
}

inline void un(int a,int b)
{
	int fa=fi(a),fb=fi(b);
	if(fa==fb) return;
	int na=f[fa],nb=f[fb];
	if(na<nb)
	{
		f[fa]+=nb;
		f[fb]=fa;
	}
	else
	{
		f[fb]+=na;
		f[fa]=fb;
	}
}

inline void adde()
{
	int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;
	if(s[0]=='A')
	{
		if(c==1)
		{
			e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;
			er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
		}
		else
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
	else if(s[0]=='O')
	{
		if(c==1)
		{
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
		}
		else
		{
			e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
			er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
		}
	}
	else
	{
		if(c==1)
		{
			e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
		else
		{
			e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;
			e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;
			er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;
			er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;
			e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;
			e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;
			er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;
			er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;
		}
	}
}

void tarjan(int i,int d)
{
	int j,k,l;
	b[i]=1;
	stb[i]=1;
	st[sl++]=i;
	low[i]=d;
	for(l=hd[i];l!=-1;l=e[l].p)
	{
		j=e[l].j;
		if(!b[j])
		{
			tarjan(j,d+1);
			low[i]=low[j]<low[i]?low[j]:low[i];
		}
		else if(stb[j]) low[i]=low[j]<low[i]?low[j]:low[i];
	}
	if(low[i]==d)
	{
		while(1)
		{
			sl--;
			un(i,st[sl]);
			if(st[sl]==i) break;
		}
	}
}

int chk()
{
	int i;
	for(i=0;i<n;i++)
		if(fi(i*2)==fi(i*2+1)) return 0;
	return 1;
}

int main()
{
	int i,j,k,l;
	while(~scanf("%d%d",&n,&m))
	{
		el=erl=0;
		memset(hd,-1,sizeof hd);
		memset(hdr,-1,sizeof hdr);
		memset(f,-1,sizeof f);
		while(m--)
		{
			scanf("%d%d%d%s",&xa,&xb,&c,s);
			adde();
		}
		sl=0;
		memset(b,0,sizeof b);
		for(i=0;i<2*n;i++)
		{
			memset(stb,0,sizeof stb);
			if(!b[i]) tarjan(i,1);
		}
		puts(chk()?"YES":"NO");
	}
	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

#include<cstdio>

#include<cstring>

int n,m,hd[2000],hdr[2000],el,erl,b[2000],f[2000];

int st[2000],sl,stb[2000],low[2000];

char s[4];

int xa,xb,c;

struct edge

{

int j,p;

}e[4000000],er[4000000];

int fi(int i)

{

if(f[i]<0) return i;

else return f[i]=fi(f[i]);

}

inline void un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb) return;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

inline void adde()

{

int a0=xa*2,a1=xa*2+1,b0=xb*2,b1=xb*2+1;

if(s[0]=='A')

{

if(c==1)

{

e[el].j=a0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=b0; e[el].p=hd[b1]; hd[b1];el++;

er[erl].j=a1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

er[erl].j=b1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

}

else

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else if(s[0]=='O')

{

if(c==1)

{

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

}

else

{

e[el].j=a1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=b1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

er[erl].j=b0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

}

else

{

if(c==1)

{

e[el].j=b1; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a0; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b0; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a1; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

else

{

e[el].j=b0; e[el].p=hd[a0]; hd[a0]=el++;

e[el].j=a0; e[el].p=hd[b0]; hd[b0]=el++;

er[erl].j=a0; er[erl].p=hdr[b0]; hdr[b0]=erl++;

er[erl].j=b0; er[erl].p=hdr[a0]; hdr[a0]=erl++;

e[el].j=b1; e[el].p=hd[a1]; hd[a1]=el++;

e[el].j=a1; e[el].p=hd[b1]; hd[b1]=el++;

er[erl].j=a1; er[erl].p=hdr[b1]; hdr[b1]=erl++;

er[erl].j=b1; er[erl].p=hdr[a1]; hdr[a1]=erl++;

}

void tarjan(int i,int d)

{

int j,k,l;

b[i]=1;

stb[i]=1;

st[sl++]=i;

low[i]=d;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].j;

if(!b[j])

{

tarjan(j,d+1);

low[i]=low[j]<low[i]?low[j]:low[i];

}

else if(stb[j]) low[i]=low[j]<low[i]?low[j]:low[i];

}

if(low[i]==d)

{

while(1)

{

sl--;

un(i,st[sl]);

if(st[sl]==i) break;

}

int chk()

{

int i;

for(i=0;i<n;i++)

if(fi(i*2)==fi(i*2+1)) return 0;

return 1;

}

int main()

{

int i,j,k,l;

while(~scanf("%d%d",&n,&m))

{

el=erl=0;

memset(hd,-1,sizeof hd);

memset(hdr,-1,sizeof hdr);

memset(f,-1,sizeof f);

while(m--)

{

scanf("%d%d%d%s",&xa,&xb,&c,s);

adde();

}

sl=0;

memset(b,0,sizeof b);

for(i=0;i<2*n;i++)

{

memset(stb,0,sizeof stb);

if(!b[i]) tarjan(i,1);

}

puts(chk()?"YES":"NO");

}

return 0;

}

[codeforces] 杀入Div. 1!

发表回复

各种磕绊过后……终于我也Candidate Master啦！附送链接：eurce01

从#184开始……一场没算分，一场C题sort用了greater_equal导致TLE，一场电脑被A没做之后……终于我也Rating 1742啦！！

其实Div. 2的题还是挺轻松的……各种水题虐虐也能加分，不过也是#189开始才过了D题，结果直接Rank 17了。

但貌似这种难度的题才相当于Div. 1的B题啊……目测接下来还是狂跪的节奏……

无论如何还是bless自己一下吧……