「NOIP模拟赛by wulala」公主的朋友

2014年8月16日2,7640

出题人说：正解分块。。。

但是这不是和某次cf的dzy loves color一样么T T

修改的时候顺便查询，如果要修改的这一段宗教相同，打个标记并且统计答案后return

否则递归

复杂度我们可以这样想

因为如果修改1-n,但是宗教都不同，这样是每个都要递归到最下面，这样一次修改就要nlogn

但是这种情况并不会一直出现，询问完后1-n会被修改成同一种宗教，再把1-n变成不同的，又要额外修改n次

也就是说，每次修改，最多让后面的查询多一个logn

所以这样均摊复杂度是logn的

#include<iostream>
#include<cstdio>
#include<cstring>
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;
}
int n,m,T,ans;
struct seg{int l,r,v,tag;bool f;}t[400005];
void update(int k)
{
	if(t[k<<1].v==t[k<<1|1].v&&t[k<<1].f&&t[k<<1|1].f)
	{		
		t[k].v=t[k<<1].v;
		t[k].f=1;
	}
	else t[k].f=0;
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;
	if(l==r){t[k].v=read();t[k].f=1;return;}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	update(k);
}
void pushdown(int k)
{
	if(!t[k].tag||t[k].l==t[k].r)return;
	t[k<<1].tag=t[k<<1|1].tag=t[k].tag;
	t[k<<1].v=t[k<<1|1].v=t[k].tag;
	t[k<<1].f=t[k<<1|1].f=1;
	t[k].tag=0;
}
void solve(int k,int x,int y,int v)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==x&&y==r&&t[k].f)
	{
		if(v==t[k].v)ans+=r-l+1;
		else 
		{
			t[k].f=1;
			t[k].v=v;
			t[k].tag=v;
		}
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)solve(k<<1,x,y,v);
	else if(x>mid)solve(k<<1|1,x,y,v);
	else 
	{
		solve(k<<1,x,mid,v);
		solve(k<<1|1,mid+1,y,v);
	}
	update(k);
}
int que(int k,int x)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==r)return t[k].v;
	int mid=(l+r)>>1;
	if(x<=mid)return que(k<<1,x);
	else return que(k<<1|1,x);
}
int main()
{
	//freopen("friend.in","r",stdin);
	//freopen("friend.out","w",stdout);
	n=read();m=read();
	build(1,1,n);
	T=read();
	for(int i=1;i<=T;i++)
	{
		int x=read(),y=read();
		int tmp=que(1,x);
		ans=0;solve(1,x,y,tmp);
		printf("%d\n",ans-1);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

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;

}

int n,m,T,ans;

struct seg{int l,r,v,tag;bool f;}t[400005];

void update(int k)

{

if(t[k<<1].v==t[k<<1|1].v&&t[k<<1].f&&t[k<<1|1].f)

{

t[k].v=t[k<<1].v;

t[k].f=1;

}

else t[k].f=0;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;

if(l==r){t[k].v=read();t[k].f=1;return;}

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

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

update(k);

}

void pushdown(int k)

{

if(!t[k].tag||t[k].l==t[k].r)return;

t[k<<1].tag=t[k<<1|1].tag=t[k].tag;

t[k<<1].v=t[k<<1|1].v=t[k].tag;

t[k<<1].f=t[k<<1|1].f=1;

t[k].tag=0;

}

void solve(int k,int x,int y,int v)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==x&&y==r&&t[k].f)

{

if(v==t[k].v)ans+=r-l+1;

else

{

t[k].f=1;

t[k].v=v;

t[k].tag=v;

}

return;

}

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

if(y<=mid)solve(k<<1,x,y,v);

else if(x>mid)solve(k<<1|1,x,y,v);

else

{

solve(k<<1,x,mid,v);

solve(k<<1|1,mid+1,y,v);

}

update(k);

}

int que(int k,int x)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==r)return t[k].v;

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

if(x<=mid)return que(k<<1,x);

else return que(k<<1|1,x);

}

int main()

{

//freopen("friend.in","r",stdin);

//freopen("friend.out","w",stdout);

n=read();m=read();

build(1,1,n);

T=read();

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

{

int x=read(),y=read();

int tmp=que(1,x);

ans=0;solve(1,x,y,tmp);

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

}

return 0;

}

« 「BZOJ1576」[Usaco2009 Jan] 安全路经Travel 「ch52」还教室 »

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

「NOIP模拟赛by wulala」公主的朋友

分类目录

热门文章

Myfriends

近期评论