[NOI2022] 众数 题解
题目描述
对于一个序列,定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入,在本题中请以题面中给出的定义为准。
一开始给定
n
n
n 个长度不一的正整数序列,编号为
1
∼
n
1 \sim n
1∼n,初始序列可以为空。这
n
n
n 个序列被视为存在,其他编号对应的序列视为不存在。 有
q
q
q 次操作,操作有以下类型:
- 1 x y 1 \ x \ y 1 x y:在 x x x 号序列末尾插入数字 y y y。保证 x x x 号序列存在,且 1 ≤ x , y ≤ n + q 1 \le x, y \le n + q 1≤x,y≤n+q。
- 2 x 2 \ x 2 x:删除 x x x 号序列末尾的数字,保证 x x x 号序列存在、非空,且 1 ≤ x ≤ n + q 1 \le x \le n + q 1≤x≤n+q。
- 3 m x 1 x 2 x m 3 \ m \ x_1 \ x_2 \ x_m 3 m x1 x2 xm:将 x 1 , x 2 , … , x m x_1, x_2, \ldots, x_m x1,x2,…,xm 号序列顺次拼接,得到一个新序列,并询问其众数。如果不存在满足上述条件的数,则返回 − 1 -1 −1。数据保证对于任意 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m, x i x_i xi 是一个仍然存在的序列, 1 ≤ x i ≤ n + q 1 \le x_i \le n + q 1≤xi≤n+q,且拼接得到的序列非空。注意:不保证 x 1 , … , x m {x_1, \ldots, x_m} x1,…,xm 互不相同,询问中的合并操作不会对后续操作产生影响。
- 4 x 1 x 2 x 3 4 \ x_1 \ x_2 \ x_3 4 x1 x2 x3:新建一个编号为 x 3 x_3 x3 的序列,其为 x 1 x_1 x1 号序列后顺次添加 x 2 x_2 x2 号序列中数字得到的结果,然后删除 x 1 , x 2 x_1, x_2 x1,x2 对应的序列。此时序列 x 3 x_3 x3 视为存在,而序列 x 1 , x 2 x_1, x_2 x1,x2 被视为不存在,在后续操作中也不会被再次使用。保证 1 ≤ x 1 , x 2 , x 3 ≤ n + q 1 \le x_1, x_2, x_3 \le n + q 1≤x1,x2,x3≤n+q、 x 1 ≠ x 2 x_1 \ne x_2 x1=x2、序列 x 1 , x 2 x_1, x_2 x1,x2 在操作前存在、且在操作前没有序列使用过编号 x 3 x_3 x3。
输入输出格式
输入格式
输入的第一行包含两个正整数
n
n
n 和
q
q
q,分别表示数列的个数和操作的次数,保证
n
≤
5
×
10
5
n \le 5 \times {10}^5
n≤5×105、
q
≤
5
×
10
5
q \le 5 \times {10}^5
q≤5×105。
接下来
n
n
n 行,第
i
i
i 行表示编号为
i
i
i 的数列。
每一行的第一个非负整数
l
i
l_i
li 表示初始第
i
i
i 号序列的数字个数,接下来有
l
i
l_i
li 个非负整数
a
i
,
j
a_{i,j}
ai,j 按顺序表示数列中的数字。
假定
C
l
=
∑
l
i
C_l = \sum l_i
Cl=∑li 代表输入序列长度之和,则保证
C
l
≤
5
×
10
5
C_l \le 5 \times {10}^5
Cl≤5×105、
a
i
,
j
≤
n
+
q
a_{i,j} \le n + q
ai,j≤n+q。
接下来
q
q
q 行,每行若干个正整数,表示一个操作,并按照题面描述中的格式输入。
假定
C
m
=
∑
m
C_m = \sum m
Cm=∑m 代表所有操作
3
3
3 需要拼接的序列个数之和,则保证
C
m
≤
5
×
10
5
C_m \le 5 \times {10}^5
Cm≤5×105。
输出格式
对于每次询问,一行输出一个整数表示对应的答案。
solution
这个题:我们可以不是很显然地知道:众数为中位数。。。。。
浅浅地证明一下啊:
若众数在最左边
∵众数为序列中出现次数严格大于一半的数字
∴ a [ 1 → e d ] = s a m e , e d − 1 + 1 ( l e n 众数 ) ≥ 1 2 l e n a l l a[1\to ed]=same,ed-1+1(len_{众数})≥\frac{1}{2}len_{all} a[1→ed]=same,ed−1+1(len众数)≥21lenall
∴ 1 ≤ m i d < e d 1≤mid<ed 1≤mid<ed
∴ a [ m i d ] = a [ 1 ] a[mid]=a[1] a[mid]=a[1]
即中位数=众数
若众数在最右边,同理可得中位数=众数
若在中间:
若众数为 a [ w ] a[w] a[w]
l e n > m i d len>mid len>mid
∴ a [ w → w + l e n ] = s a m e a[w\to w+len]=same a[w→w+len]=same
又∵ w + l e n ≤ n w+len≤n w+len≤n
∴ w < m i d w<mid w<mid
又因为 w + l e n > m i d w+len>mid w+len>mid
∴ a [ m i d ] = a [ w ] a[mid]=a[w] a[mid]=a[w]
综上所述,众数为中位数
证毕。
so,我们可以开一个权值线段树来统计序列中数的个数
用链表来存序列。。。。。。。。。。
权值线段树
权值线段树即一种线段树,以序列的数值为下标。
权值线段树维护一列数中数的个数。
也就是说,我们的权值线段树就是用线段树维护了一堆桶。
这就是权值线段树的概念。
权值线段树维护的是桶,按值域开空间,维护的是个数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e6+2;
int n;//初始 有多少链表
int q;//询问个数
int m;//询问3链表的个数
int que[N];// 询问3的第i个链表的id
int lst[N];//询问3的第i个链表的rt值
int lim;//总共有多少链表
int hd[N];//i链表的头头
int tl[N];//i链表的尾巴
int pre[N];//i的前面一个
int val[N];//第i个数的值
int tot;//加入数的id
ll sz[N];//i链表的size大小
int rt[N];//i链表在线段树上的rt
int lc[N],rc[N];//线段树i的左右儿子
int ttt;//线段树节点(动态开点)
ll sum[N];//i的个数(线段树)
int x,op,id,y;
void addlink(int id,int x){//在链表后加上x
if(!sz[id]) hd[id]=x;//x就是id链表的第一个元素(ta就是头头)
sz[id]++;//链表大小更新
pre[x]=tl[id];//x的前一个就是id链表之前的尾巴
tl[id]=x;//新尾巴
}
void dellink(int id){//删去链表末尾
sz[id]--;// 链表大小更新
if(!sz[id]) hd[id]=0;//id链表没了。。
tl[id]=pre[tl[id]];//尾巴就是尾巴的前一个
}
void link(int x,int y,int id){//链表合并
if(sz[x])hd[id]=hd[x];//id的头头就是x的头头
else hd[id]=hd[y];//但是如果xGG了话就是y的头头了
if(sz[y])tl[id]=tl[y];//id的尾巴就是y的尾巴
else tl[id]=tl[x];//但是如果yGG了话就是x的尾巴了
sz[id]=sz[x]+sz[y];//id的大小就是x和y加起来
if(hd[y]) pre[hd[y]]=tl[x];//xy首位拼接
}
void pushup(int p){
sum[p]=sum[lc[p]]+sum[rc[p]];//sum数组更新
}
void update(int &p,int l,int r,int w,ll v){
if(!p){
p=++ttt; //动态开点
} //懂?
if(l==r){//找到啦
sum[p]+=v;
return ;
}
int mid=(l+r)>>1;
if(w<=mid) update(lc[p],l,mid,w,v);//在左边
else update(rc[p],mid+1,r,w,v);//在右边
pushup(p);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return (x+y);//有一个已经GG了
if(l==r){//
sum[x]+=sum[y];
return x;
}
int mid=(l+r)>>1;
lc[x]=merge(lc[x],lc[y],l,mid);
rc[x]=merge(rc[x],rc[y],mid+1,r);
pushup(x);//合并合并 afasdfasd
return x;
}
ll getsum(int p,int l,int r,int L){//L出现的次数
if(!p) return 0;
if(l==r) return sum[p];//you got it!
int mid=(l+r)>>1;
if(L<=mid) return getsum(lc[p],l,mid,L);
return getsum(rc[p],mid+1,r,L);
}
int query(int l,int r,int k){//二分 中位数
if(l==r) return l;
ll tmp=0;
for(int i=1;i<=m;i++){
tmp+=sum[lc[lst[i]]];
}
int mid=(l+r)>>1;
if(tmp>=k){//在←
for(int i=1;i<=m;i++){
lst[i]=lc[lst[i]];
}
return query(l,mid,k);
}else{
for(int i=1;i<=m;i++){
lst[i]=rc[lst[i]];
}
return query(mid+1,r,k-tmp);
}
}
int main(){
scanf("%d%d",&n,&q);
lim=n+q;
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d",&x);
val[++tot]=x;
addlink(i,tot);
update(rt[i],1,lim,x,1);
}
}
while(q--){
scanf("%d",&op);
if(op==1){
scanf("%d%d",&id,&x);
val[++tot]=x;
addlink(id,tot);
//链表末尾加上x(val[tot])
update(rt[id],1,lim,x,1);
//cnt[x]+1
} else if(op==2){
scanf("%d",&id);
update(rt[id],1,lim,val[tl[id]],-1);
//cnt[val[链表id末尾tl[id]]]-1
dellink(id);
//删去链表末尾
} else if(op==3){
scanf("%d",&m);
ll all=0;//合并后数组长度
for(int i=1;i<=m;i++){
scanf("%d",&que[i]);//第i个数组
lst[i]=rt[que[i]];//第i个数组的头头
all+=sz[que[i]];//总长
}
int xx=query(1,lim,(all+1)>>1);
ll tmp=0;
//tmp:中位数xx出现的个数
for(int i=1;i<=m;i++){
tmp+=getsum(rt[que[i]],1,lim,xx);
//xx在第i个数组中出现的次数
}
if((tmp<<1)>all) printf("%d\n",xx);//ok啊
else printf("-1\n"); //不ok
} else{
scanf("%d%d%d",&x,&y,&id);
link(x,y,id);//合并两链表
rt[id]=merge(rt[x],rt[y],1,lim); //合并线段树
}
}
return 0;
}
完结撒花❀
★,°:.☆( ̄▽ ̄)/$:.°★ 。