YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制：2000MS 内存限制：524288KB

难度：\(6.5\)

题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\)，有 \(m\) 次操作。格式如下：

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

输入格式

第一行两个正整数 \(n,m\)，表示序列长度和操作次数。

第二行 \(n\) 个正整数，第 \(i\) 个数为 \(a_i\)，表示序列初始值。

接下来 \(m\) 行每行四个正整数，表示操作，含义如题目所示。

输出格式

对于每个询问，输出一行一个正整数表示答案。

样例 1 输入

10 5
1 1 2 3 4 5 3 3 2 3
2 1 3 1
1 2 3 1
2 1 3 2
1 1 10 3
2 1 10 3

10 5

1 1 2 3 4 5 3 3 2 3

2 1 3 1

1 2 3 1

2 1 3 2

1 1 10 3

2 1 10 3

样例 1 输出

2
0
10

数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq n,m \leq 2000\) 。

对于 \(50\%\) 的数据，\(1 \leq n,m \leq 100000\) 。

对于另外 \(10\%\) 的数据，没有 \(1\) 操作。

对于 \(100\%\) 的数据，\(1 \leq n,m,a_i,x \leq 400000\)，\(1 \leq l \leq r \leq n\)，保证数据不是纯随机生成。

考场上看到区间推平一眼 ODT，然而底下数据保证不随机www

然后第二眼就是分块，\(n \leq 400000\) 这能过？

不管了，先打了www

然后脑补了一个分块，修改时中间打标记，端点暴力修改，查询暴力块内二分，是 \(O(n \sqrt n \log n)\) 的。

然后很神奇的过了？？？

某同学也写了一个分块，然而他只拿了 \(50pts\) wwwwww

神奇常数wwwwww最大点才1.29s比正解还快wwwwwwwwwwwwwwwww

然后被全询问 \([1,n]\) 卡掉了）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>

#define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE
	char __B[1<<15],*__S=__B,*__T=__B;
	#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)
#endif
inline int getnum()
{
	register char c=0;
	while(!(c>='0' && c<='9'))
		c=getchar();
	register int a=0;
	while(c>='0' && c<='9')
		a=a*10+c-'0',c=getchar();
	return a;
}

int BlockSize,BlockNum;
int _bpos[405050],_bleft[655],_bright[655];
#define GetBlockPos(_p) (_bpos[_p])
#define GetBlockLeft(_w) (_bleft[_w])
#define GetBlockRight(_w) (_bright[_w])
#define GetBlockLen(_w) (GetBlockRight(_w)-GetBlockLeft(_w)+1)
/*#define GetBlockPos(_p_) (((_p_)-1)/BlockSize+1)
#define GetBlockLeft(_w_) (((_w_)-1)*BlockSize+1)
#define GetBlockRight(_w_) _min((_w_)*BlockSize,N)*/

int a[405050];
int bnum[655][655],bnums[655][655],samenum[655];
#define GetAprCnt(_arr,_lbd,_ubd,_x) (std::upper_bound(&(_arr)[_lbd],&(_arr)[_ubd],_x)-std::lower_bound(&(_arr)[_lbd],&(_arr)[_ubd],_x))
#define GetAprCntO(_arr,_lbd,_ubd,_x) (std::count(&(_arr)[_lbd],&(_arr)[_ubd],_x))

int main()
{
//freopen("sqrt.in","r",stdin);freopen("sqrt.out","w",stdout);
	register int N=getnum(),M=getnum();
	for(register int i=1;i<=N;i++)
		a[i]=getnum();
	
	BlockSize=__builtin_sqrt(N),BlockNum=N/BlockSize+(N%BlockSize!=0);
	_bleft[1]=1,_bright[BlockNum]=N;
	for(register int i=1,tb=1;i<=N;i++)
	{
		_bpos[i]=tb;
		if(i%BlockSize == 0)
			_bright[tb++]=i,_bleft[tb]=i+1;
	}
	
	for(register int i=1;i<=BlockNum;i++)
	{
		for(register int j=GetBlockLeft(i),sj=j;j<=GetBlockRight(i);j++)
			bnum[i][j-sj+1]=a[j];
		memcpy(&bnums[i],&bnum[i],sizeof(bnums[0]));
		std::sort(&bnums[i][1],&bnums[i][GetBlockLen(i)+1]);
	}
	
	for(register int lp=1;lp<=M;lp++)
	{
		register int opt=getnum(),l=getnum(),r=getnum(),x=getnum();
		register int lpos=GetBlockPos(l),rpos=GetBlockPos(r),nl,nr;
		if(opt==1)
		{
			if(lpos==rpos)
			{
				if(samenum[lpos])
				{
					for(register int j=1;j<=GetBlockLen(lpos);j++)
						bnum[lpos][j]=samenum[lpos];
					samenum[lpos]=0;
				}
				nl=l-GetBlockLeft(lpos)+1,nr=r-GetBlockLeft(lpos)+1;
				for(register int i=nl;i<=nr;i++)
					bnum[lpos][i]=x;
				memcpy(&bnums[lpos],&bnum[lpos],sizeof(bnums[0]));
				std::sort(&bnums[lpos][1],&bnums[lpos][GetBlockLen(lpos)+1]);
			}
			else
			{
				if(samenum[lpos])
				{
					for(register int j=1;j<=GetBlockLen(lpos);j++)
						bnum[lpos][j]=samenum[lpos];
					samenum[lpos]=0;
				}
				nl=l-GetBlockLeft(lpos)+1;
				for(register int i=nl;i<=GetBlockLen(lpos);i++)
					bnum[lpos][i]=x;
				memcpy(&bnums[lpos],&bnum[lpos],sizeof(bnums[0]));
				std::sort(&bnums[lpos][1],&bnums[lpos][GetBlockLen(lpos)+1]);
				
				if(samenum[rpos])
				{
					for(register int j=1;j<=GetBlockLen(rpos);j++)
						bnum[rpos][j]=samenum[rpos];
					samenum[rpos]=0;
				}
				nr=r-GetBlockLeft(rpos)+1;
				for(register int i=1;i<=nr;i++)
					bnum[rpos][i]=x;
				memcpy(&bnums[rpos],&bnum[rpos],sizeof(bnums[0]));
				std::sort(&bnums[rpos][1],&bnums[rpos][GetBlockLen(rpos)+1]);
				
				for(register int i=lpos+1;i<=rpos-1;i++)
					samenum[i]=x;
			}
		}
		else
		{
			if(lpos==rpos)
			{
				if(samenum[lpos])
					printf("%d\n",(samenum[lpos]==x ? r-l+1 : 0));
				else
					nl=l-GetBlockLeft(lpos)+1,nr=r-GetBlockLeft(lpos)+1,
					printf("%d\n",GetAprCntO(bnum[lpos],nl,nr+1,x));
			}
			else
			{
				register int ans=0;
				
				if(samenum[lpos])
					ans+=(samenum[lpos]==x ? GetBlockRight(lpos)-l+1 : 0);
				else
					nl=l-GetBlockLeft(lpos)+1,
					ans+=GetAprCntO(bnum[lpos],nl,GetBlockLen(lpos)+1,x);
				
				if(samenum[rpos])
					ans+=(samenum[rpos]==x ? r-GetBlockLeft(rpos)+1 : 0);
				else
					nr=r-GetBlockLeft(rpos)+1,
					ans+=GetAprCntO(bnum[rpos],1,nr+1,x);
				
				for(register int i=lpos+1;i<=rpos-1;i++)
					if(samenum[i])
						ans+=(samenum[i]==x ? GetBlockLen(i) : 0);
					else
						ans+=GetAprCnt(bnums[i],1,GetBlockLen(i)+1,x);
				
				printf("%d\n",ans);
			}
		}
	}
	
	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

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <algorithm>

#define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE

char __B[1<<15],*__S=__B,*__T=__B;

#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)

#endif

inline int getnum()

{

while(!(c>='0' && c<='9'))

c=getchar();

while(c>='0' && c<='9')

a=a*10+c-'0',c=getchar();

return a;

}

int BlockSize,BlockNum;

int _bpos[405050],_bleft[655],_bright[655];

#define GetBlockPos(_p) (_bpos[_p])

#define GetBlockLeft(_w) (_bleft[_w])

#define GetBlockRight(_w) (_bright[_w])

#define GetBlockLen(_w) (GetBlockRight(_w)-GetBlockLeft(_w)+1)

/*#define GetBlockPos(_p_) (((_p_)-1)/BlockSize+1)

#define GetBlockLeft(_w_) (((_w_)-1)*BlockSize+1)

#define GetBlockRight(_w_) _min((_w_)*BlockSize,N)*/

int a[405050];

int bnum[655][655],bnums[655][655],samenum[655];

#define GetAprCnt(_arr,_lbd,_ubd,_x) (std::upper_bound(&(_arr)[_lbd],&(_arr)[_ubd],_x)-std::lower_bound(&(_arr)[_lbd],&(_arr)[_ubd],_x))

#define GetAprCntO(_arr,_lbd,_ubd,_x) (std::count(&(_arr)[_lbd],&(_arr)[_ubd],_x))

int main()

{

//freopen("sqrt.in","r",stdin);freopen("sqrt.out","w",stdout);

for(register int i=1;i<=N;i++)

a[i]=getnum();

BlockSize=__builtin_sqrt(N),BlockNum=N/BlockSize+(N%BlockSize!=0);

_bleft[1]=1,_bright[BlockNum]=N;

for(register int i=1,tb=1;i<=N;i++)

{

_bpos[i]=tb;

if(i%BlockSize == 0)

_bright[tb++]=i,_bleft[tb]=i+1;

}

for(register int i=1;i<=BlockNum;i++)

{

for(register int j=GetBlockLeft(i),sj=j;j<=GetBlockRight(i);j++)

bnum[i][j-sj+1]=a[j];

memcpy(&bnums[i],&bnum[i],sizeof(bnums[0]));

std::sort(&bnums[i][1],&bnums[i][GetBlockLen(i)+1]);

}

for(register int lp=1;lp<=M;lp++)

{

if(opt==1)

{

if(lpos==rpos)

{

if(samenum[lpos])

{

for(register int j=1;j<=GetBlockLen(lpos);j++)

bnum[lpos][j]=samenum[lpos];

samenum[lpos]=0;

}

nl=l-GetBlockLeft(lpos)+1,nr=r-GetBlockLeft(lpos)+1;

for(register int i=nl;i<=nr;i++)

bnum[lpos][i]=x;

memcpy(&bnums[lpos],&bnum[lpos],sizeof(bnums[0]));

std::sort(&bnums[lpos][1],&bnums[lpos][GetBlockLen(lpos)+1]);

}

else

{

if(samenum[lpos])

{

for(register int j=1;j<=GetBlockLen(lpos);j++)

bnum[lpos][j]=samenum[lpos];

samenum[lpos]=0;

}

nl=l-GetBlockLeft(lpos)+1;

for(register int i=nl;i<=GetBlockLen(lpos);i++)

bnum[lpos][i]=x;

memcpy(&bnums[lpos],&bnum[lpos],sizeof(bnums[0]));

std::sort(&bnums[lpos][1],&bnums[lpos][GetBlockLen(lpos)+1]);

if(samenum[rpos])

{

for(register int j=1;j<=GetBlockLen(rpos);j++)

bnum[rpos][j]=samenum[rpos];

samenum[rpos]=0;

}

nr=r-GetBlockLeft(rpos)+1;

for(register int i=1;i<=nr;i++)

bnum[rpos][i]=x;

memcpy(&bnums[rpos],&bnum[rpos],sizeof(bnums[0]));

std::sort(&bnums[rpos][1],&bnums[rpos][GetBlockLen(rpos)+1]);

for(register int i=lpos+1;i<=rpos-1;i++)

samenum[i]=x;

}

else

{

if(lpos==rpos)

{

if(samenum[lpos])

printf("%d\n",(samenum[lpos]==x ? r-l+1 : 0));

else

nl=l-GetBlockLeft(lpos)+1,nr=r-GetBlockLeft(lpos)+1,

printf("%d\n",GetAprCntO(bnum[lpos],nl,nr+1,x));

}

else

{

if(samenum[lpos])

ans+=(samenum[lpos]==x ? GetBlockRight(lpos)-l+1 : 0);

else

nl=l-GetBlockLeft(lpos)+1,

ans+=GetAprCntO(bnum[lpos],nl,GetBlockLen(lpos)+1,x);

if(samenum[rpos])

ans+=(samenum[rpos]==x ? r-GetBlockLeft(rpos)+1 : 0);

else

nr=r-GetBlockLeft(rpos)+1,

ans+=GetAprCntO(bnum[rpos],1,nr+1,x);

for(register int i=lpos+1;i<=rpos-1;i++)

if(samenum[i])

ans+=(samenum[i]==x ? GetBlockLen(i) : 0);

else

ans+=GetAprCnt(bnums[i],1,GetBlockLen(i)+1,x);

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

}

return 0;

}

然后结束一看，正解就是 ODT）

由于 ODT 修改复杂度是对的，所以修改时可以用 ODT，查询时就不能了。

所以对每种颜色都开一个线段树（标记永久化比打 \(tag\) 快很多，特别是动态开点）维护这个颜色出现在哪些区间里，查询时直接在线段树里查就行了。

修改时用 ODT 遍历每个需要修改的区间，在各自的线段树上删去原区间后，加入新区间即可。

时间复杂度 \(O(m \log^2 n)\)。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <set>

#define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_))
#define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE
	char __B[1<<15],*__S=__B,*__T=__B;
	#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)
#endif
inline int getnum()
{
	register char c=0;
	while(!(c>='0' && c<='9'))
		c=getchar();
	register int a=0;
	while(c>='0' && c<='9')
		a=a*10+c-'0',c=getchar();
	return a;
}

#define _TSIZE 30505050
int cnt,lson[_TSIZE],rson[_TSIZE],sum[_TSIZE],tag[_TSIZE];
int root[405050];

int ML,MR,MV;
void ModifyTree(int&o,register int l,register int r)
{
	if(!o)
		o=++cnt;
	if(l>=ML && r<=MR)
	{
		sum[o]+=MV*(r-l+1),tag[o]+=MV;
		return;
	}
	register int mid=(l+r)>>1;
	if(ML<=mid)
		ModifyTree(lson[o],l,mid);
	if(MR>mid)
		ModifyTree(rson[o],mid+1,r);
	sum[o]=sum[lson[o]]+sum[rson[o]]+tag[o]*(r-l+1);
}

int _Qret,QL,QR;
void QueryTree(register int o,register int l,register int r)
{
	if(!o)
		return;
	if(l>=QL && r<=QR)
	{
		_Qret+=sum[o];
		return;
	}
	register int mid=(l+r)>>1;
	if(QL<=mid)
		QueryTree(lson[o],l,mid);
	if(QR>mid)
		QueryTree(rson[o],mid+1,r);
	_Qret+=(_min(r,QR)-_max(l,QL)+1)*tag[o];
}

struct _seg
{
	int l,r,val;
	bool operator < (const _seg&o)const
	{
		return l < o.l;
	}
};
typedef std::set<_seg>::iterator _tit;
std::set<_seg>tree;

inline _tit split(register int pos)
{
	_tit it=tree.lower_bound((_seg){pos,-1,0});
	if(it!=tree.end() && it->l==pos)
		return it;
	--it;
	
	register int l=it->l,r=it->r,val=it->val;
	tree.erase(it);
	
	tree.insert((_seg){l,pos-1,val});
	return tree.insert((_seg){pos,r,val}).first;
}

int main()
{
	register int N=getnum(),M=getnum();
	for(register int i=1,a;i<=N;i++)
		a=getnum(),
		tree.insert((_seg){i,i,a}),
		ML=MR=i,MV=1,ModifyTree(root[a],1,N);
	tree.insert((_seg){N+1,N+1,0});
	
	for(register int i=1;i<=M;i++)
	{
		register int opt=getnum(),l=getnum(),r=getnum(),x=getnum();
		if(opt==1)
		{
			_tit itr=split(r+1),itl=split(l),titl=itl;
			for(;itl!=itr;++itl)
				ML=itl->l,MR=itl->r,MV=-1,ModifyTree(root[itl->val],1,N);
			tree.erase(titl,itr);
			tree.insert((_seg){l,r,x});
			ML=l,MR=r,MV=1,ModifyTree(root[x],1,N);
		}
		else
		{
			_Qret=0,QL=l,QR=r,QueryTree(root[x],1,N);
			printf("%d\n",_Qret);
		}
	}
	
	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 <cstdlib>

#include <cstring>

#include <climits>

#include <set>

#define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_))

#define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE

char __B[1<<15],*__S=__B,*__T=__B;

#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)

#endif

inline int getnum()

{

while(!(c>='0' && c<='9'))

c=getchar();

while(c>='0' && c<='9')

a=a*10+c-'0',c=getchar();

return a;

}

#define _TSIZE 30505050

int cnt,lson[_TSIZE],rson[_TSIZE],sum[_TSIZE],tag[_TSIZE];

int root[405050];

int ML,MR,MV;

void ModifyTree(int&o,register int l,register int r)

{

if(!o)

o=++cnt;

if(l>=ML && r<=MR)

{

sum[o]+=MV*(r-l+1),tag[o]+=MV;

return;

}

if(ML<=mid)

ModifyTree(lson[o],l,mid);

if(MR>mid)

ModifyTree(rson[o],mid+1,r);

sum[o]=sum[lson[o]]+sum[rson[o]]+tag[o]*(r-l+1);

}

int _Qret,QL,QR;

void QueryTree(register int o,register int l,register int r)

{

if(!o)

return;

if(l>=QL && r<=QR)

{

_Qret+=sum[o];

return;

}

if(QL<=mid)

QueryTree(lson[o],l,mid);

if(QR>mid)

QueryTree(rson[o],mid+1,r);

_Qret+=(_min(r,QR)-_max(l,QL)+1)*tag[o];

}

struct _seg

{

int l,r,val;

bool operator < (const _seg&o)const

{

return l < o.l;

}

};

typedef std::set<_seg>::iterator _tit;

std::set<_seg>tree;

inline _tit split(register int pos)

{

_tit it=tree.lower_bound((_seg){pos,-1,0});

if(it!=tree.end() && it->l==pos)

return it;

--it;

tree.erase(it);

tree.insert((_seg){l,pos-1,val});

return tree.insert((_seg){pos,r,val}).first;

}

int main()

{

for(register int i=1,a;i<=N;i++)

a=getnum(),

tree.insert((_seg){i,i,a}),

ML=MR=i,MV=1,ModifyTree(root[a],1,N);

tree.insert((_seg){N+1,N+1,0});

for(register int i=1;i<=M;i++)

{

if(opt==1)

{

_tit itr=split(r+1),itl=split(l),titl=itl;

for(;itl!=itr;++itl)

ML=itl->l,MR=itl->r,MV=-1,ModifyTree(root[itl->val],1,N);

tree.erase(titl,itr);

tree.insert((_seg){l,r,x});

ML=l,MR=r,MV=1,ModifyTree(root[x],1,N);

}

else

{

_Qret=0,QL=l,QR=r,QueryTree(root[x],1,N);

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

}

return 0;

}

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

题目描述

输入格式

输出格式

样例 1 输入

样例 1 输出

数据规模与约定

发表回复 取消回复

发表回复取消回复