Reincarnation

正因为梦易碎，才格外美好。

CF643G Choosing Ads

发表于 更新于 分类于
本文字数： 5.3k 阅读时长 ≈ 5 分钟

据说是 的前置知识……

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/contest/643/problem/G

形式化题意：给定一个长度为 的序列， 次操作和参数 ，维护以下操作：

  • 1 l r x 将 覆盖为 ；
  • 2 l r 求出 中出现次数超过了 的数。

对于操作 ，你可以输出不超过 个数，可以是错误答案，也可以重复答案，但正确答案必须包含其中。

数据范围：。

考虑到这里的 是针对全局的，所以我们可以抓住 来解决问题。

当 时，容易发现，这个区间内至多只有一个数满足条件，且必须出现次数超过一半，这个问题类似于我们学过的摩尔投票法求区间绝对众数的问题。

在上一个博客，我曾写过一篇介绍摩尔投票的博客：https://violeteternal.github.io/Eternity/题解/p2397/ ，所以这里也不过多解释。

然后我们扩展 到 ，容易发现，一个区间内可能存在答案的数只有 个，也至多能输出 个，所以，我们就类似于摩尔投票法那样记录 个数作为备选答案，然后输出，正不正确咱们也不知道。

然后考虑如何快速得到答案，毕竟是区间操作，容易想到线段树，而摩尔投票也支持结合律，所以可以通过线段树的子树合并得到答案，就解决了。重点实现在 merge 函数中。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// ----- Eternally question-----
// Problem: G. Choosing Ads
// Contest: Codeforces - VK Cup 2016 - Round 3
// URL: https://codeforces.com/contest/643/problem/G
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-01-26 09:44:03
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define fir first
#define sec second
using Pir=std::pair<int,int>;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
int N,Q,P,Val[MAXN];
struct Node
{
	int val[6],cnt[6];
	Node(){ std::memset(val,0,sizeof(val)),std::memset(cnt,0,sizeof(cnt)); }
};
inline Node newNode(int v)
{
	Node res;
	res.val[0]=v,res.cnt[0]=1;
	return res;
}
inline Node newNode(int v,int c)
{
	Node res;
	res.val[0]=v,res.cnt[0]=c;
	return res;
}
inline Node merge(Node a,Node b)
{
	Node c=a;
	for(int i=0;i<P;++i)
		if(b.cnt[i])
		{
			bool ok=0;
			for(int j=0;j<P;++j)
				if(c.val[j]==b.val[i])
				{
					c.cnt[j]+=b.cnt[i];
					ok=1;break;
				}
			if(!ok) for(int j=0;j<P;++j)
				if(!c.cnt[j])
				{
					c.val[j]=b.val[i];
					c.cnt[j]=b.cnt[i];
					ok=1;break;
				}
			if(ok) continue;
			int num=INF;
			for(int j=0;j<P;++j) checkMin(num,c.cnt[j]);
			if(num>=b.cnt[i])
			{
				for(int j=0;j<P;++j) c.cnt[j]-=b.cnt[i];
				continue;
			}
			bool rec=0;
			for(int j=0;j<P;++j)
			{
				if(c.cnt[j]==num&&(!rec))
				{
					c.val[j]=b.val[i];
					c.cnt[j]=b.cnt[i]-num;
					rec=1;
				}
				else c.cnt[j]-=num;
			}
		}
	return c;
}
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r,cov;
	Node val;
}Tr[MAXN<<2];
inline void pushUp(int p)
{ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
inline void pushDown(int p)
{
	if(Tr[p].cov==-INF) return ;
	Tr[ls].cov=Tr[rs].cov=Tr[p].cov;
	Tr[ls].val=newNode(Tr[p].cov,Tr[ls].r-Tr[ls].l+1);
	Tr[rs].val=newNode(Tr[p].cov,Tr[rs].r-Tr[rs].l+1);
	Tr[p].cov=-INF;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].cov=-INF;
	if(l==r) return Tr[p].val=newNode(Val[l]),void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyCov(int p,int l,int r,int x)
{
	if(l<=Tr[p].l&&Tr[p].r<=r)
	{
		Tr[p].val=newNode(x,Tr[p].r-Tr[p].l+1);
		Tr[p].cov=x;return ;
	}
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyCov(ls,l,r,x);
	if(mid<r) modifyCov(rs,l,r,x);
	pushUp(p);
}
Node querySum(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	Node res;
	if(l<=mid) res=merge(res,querySum(ls,l,r));
	if(mid<r) res=merge(res,querySum(rs,l,r));
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q,P);
	P=100/P;
	for(int i=1;i<=N;++i) read(Val[i]);
	build(1,1,N);
	for(int opt,ql,qr,qx;Q--;)
	{
		read(opt,ql,qr);
		if(opt==1)
		{
			read(qx);
			modifyCov(1,ql,qr,qx);
		}
		else
		{
			Node res=querySum(1,ql,qr);
			int cnt=std::min(P,qr-ql+1);
			write(cnt,' ');
			for(int i=0;i<cnt;++i) write(res.val[i],' ');
			puts("");
		}
	}
	return 0;
}
/*

*/

然后根据这奇妙的输出方式，我们可以进行乱搞，分块加随机化也是可以通过本题的。而根据本题的线段树合并区间绝对众数的思路，就可以为 提供一些思路了。

相关文章