【CF643G】Choosing Ads(线段树)

点此看题面

  • 给定一个长度为\(n\)的序列和一个整数\(p\)。
  • 要求支持两种操作,区间赋值;询问区间中出现次数至少占\(p\%\)的数,可以输出至多\(\lfloor\frac{100}p\rfloor\)个数,可以包含错解,但必须有正确的解。
  • \(n\le1.5\times10^5,20\le p\le100\)

前置:一个经典的简单题

一个很简单的问题,给定一个序列,求出其中出现超过一半的数。(要求不开数组)

这时候我们就考虑,用这个数的出现次数减去其余所有数的出现次数是为正的。

因此,我们可以把它看成一种格斗,确定一个数,血量就是它当前的出现次数。

然后每加入一个数,如果和这个数一样就将血量加\(1\),如果不一样就将血量减\(1\)。

当血量减至\(0\)的时候这个数就死了,我们就需要把它换成一个新数。

(说实话,这道题应该是我刚上\(BZOJ\)时做的第一道题,至今都给我留有很深的印象,这个套路我也一直都很想再度使用,今天终于有了机会。)

扩展:区间的合并

现在我们把上面这个问题扩展一下,想要用线段树来维护这个格斗过程,实现区间查询。

然后我们发现,实际上完全可以让两个区间分别格斗出一个数来,如果这两个数相同就合并血量,否则保留血量大的并将它的血量减去小的血量。

扩展:多个数的格斗

回到这道题,相当于我们现在已经解决了\(p\ge 51\)时的部分。(区间赋值显然就把这个区间格斗出的数设为赋值的数,血量设为区间长度即可)

而当\(p\)很小的时候,可能有多个数,其实不妨,只要把这\(\lfloor\frac {100}p\rfloor\)个数维护下来即可。

具体地,就是用右区间格斗出的每个数去打左区间格斗出的每个数。

如果有相同直接合并血量,如果左区间的数还未到\(\lfloor\frac{100}p\rfloor\)个直接加入。

否则找到左区间中所有数和这个数中血量最少的那个,把其余数血量都减少它的血量,再把这个血量最少的数删去。

尽管这样的合并是\(\lfloor\frac{100}p\rfloor^2\)的,但毕竟\(\lfloor\frac{100}p\rfloor\le5\),随便过。

代码:\(O(nlogn\lfloor\frac{100}p\rfloor^2)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 150000
#define K 5
using namespace std;
int n,p,a[N+5];struct Data
{
	int k,V[K],C[K];I Data() {k=0,memset(V,0,sizeof(V)),memset(C,0,sizeof(C));}
	I friend Data operator + (Data x,Data y)//合并
	{
		for(RI i=0,j;i^y.k;++i)//枚举右区间每个数去打左区间
		{
			for(j=0;j^x.k&&x.V[j]^y.V[i];++j);if(j^x.k) {x.C[j]+=y.C[i];continue;}//如果存在相同直接合并血量
			if(x.k^(100/p)) {x.V[x.k]=y.V[i],x.C[x.k++]=y.C[i];continue;}//如果左区间未满直接加入
			for(j=0;j^x.k;++j) x.C[j]<y.C[i]&&(swap(x.V[j],y.V[i]),swap(x.C[j],y.C[i]),0);//找到血量最小的
			for(j=0;j^x.k;++j) x.C[j]-=y.C[i];//把其他数的血量全减去该数血量
		}return x;
	}
};
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void write(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
	I void print(Con Data& v) {write(v.k),pc(' ');for(RI i=0;i^v.k;++i) write(v.V[i]),pc(' ');pc('\n');}
}using namespace FastIO;
class SegmentTree
{
	private:
		#define PT CI l=1,CI r=n,CI rt=1
		#define LT l,mid,rt<<1
		#define RT mid+1,r,rt<<1|1
		#define PU() (V[rt]=V[rt<<1]+V[rt<<1|1])
		#define PD() (F[rt]&&(T(rt<<1,F[rt],mid-l+1),T(rt<<1|1,F[rt],r-mid),F[rt]=0))
		#define T(x,v,c) (V[x].k=1,V[x].V[0]=F[x]=v,V[x].C[0]=c)//格斗出的数设为v,血量设为区间长度c
		Data V[N<<2];int F[N<<2];
	public:
		I void B(PT) {if(l==r) return (void)T(rt,a[l],1);RI mid=l+r>>1;B(LT),B(RT),PU();}
		I void U(CI L,CI R,CI v,PT)//区间赋值
		{
			if(L<=l&&r<=R) return (void)T(rt,v,r-l+1);RI mid=l+r>>1;PD();
			L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0),PU();
		}
		I Data Q(CI L,CI R,PT)//区间询问
		{
			if(L==l&&r==R) return V[rt];RI mid=l+r>>1;PD();if(R<=mid) return Q(L,R,LT);
			if(L>mid) return Q(L,R,RT);return Q(L,mid,LT)+Q(mid+1,R,RT);
		}
}S;
int main()
{
	RI Qt,i,op,x,y,v;for(read(n,Qt,p),i=1;i<=n;++i) read(a[i]);S.B();
	W(Qt--) read(op,x,y),op==1?(read(v),S.U(x,y,v)):print(S.Q(x,y));return clear(),0;
}
上一篇:1028 List Sorting (25 分)(排序)


下一篇:CF1500C Matrix Sorting(拓扑排序)