[NOI2022] 众数 题解

题目描述

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。
一开始给定 $n$ 个长度不一的正整数序列，编号为 $1\sim n$，初始序列可以为空。这 $n$ 个序列被视为存在，其他编号对应的序列视为不存在。 有 $q$ 次操作，操作有以下类型:

• $1xy$：在 $x$ 号序列末尾插入数字 $y$。保证 $x$ 号序列存在，且 $1\le x,y\le n+q$。
• $2x$：删除 $x$ 号序列末尾的数字，保证 $x$ 号序列存在、非空，且 $1\le x\le n+q$。
• $3m{x}_1{x}_2{x}_m$：将 $x_1,x_2,\dots ,x_m$ 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 $-1$。数据保证对于任意 $1\le i\le m$，$x_i$ 是一个仍然存在的序列，$1\le x_i\le n+q$，且拼接得到的序列非空。注意：不保证 $x_1,\dots ,x_m$ 互不相同，询问中的合并操作不会对后续操作产生影响。
• $4x_1{x}_2{x}_3$：新建一个编号为 $x_3$ 的序列，其为 $x_1$ 号序列后顺次添加 $x_2$ 号序列中数字得到的结果，然后删除 $x_1,x_2$ 对应的序列。此时序列 $x_3$ 视为存在，而序列 $x_1,x_2$ 被视为不存在，在后续操作中也不会被再次使用。保证 $1\le x_1,x_2,x_3\le n+q$、$x_1\ne x_2$、序列 $x_1,x_2$ 在操作前存在、且在操作前没有序列使用过编号 $x_3$。

输入输出格式

输入格式

输入的第一行包含两个正整数 $n$ 和 $q$，分别表示数列的个数和操作的次数，保证 $n\le 5\times {10}^5$、$q\le 5\times {10}^5$。
接下来 $n$ 行，第 $i$ 行表示编号为 $i$ 的数列。
每一行的第一个非负整数 $l_i$ 表示初始第 $i$ 号序列的数字个数，接下来有 $l_i$ 个非负整数 $a_{i,j}$ 按顺序表示数列中的数字。
假定 $C_l=\sum l_i$ 代表输入序列长度之和，则保证 $C_l\le 5\times {10}^5$、$a_{i,j}\le n+q$。
接下来 $q$ 行，每行若干个正整数，表示一个操作，并按照题面描述中的格式输入。
假定 $C_m=\sum m$ 代表所有操作 $3$ 需要拼接的序列个数之和，则保证 $C_m\le 5\times {10}^5$。

输出格式

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

solution

这个题：我们可以不是很显然地知道：众数为中位数。。。。。

浅浅地证明一下啊：

若众数在最左边

∵众数为序列中出现次数严格大于一半的数字

∴$a[1\to ed]=same，ed-1+1(le{n}_{众数})\ge \frac{1}{2}le{n}_{all}$

∴$1\le mid<ed$

∴$a[mid]=a[1]$

即中位数=众数

若众数在最右边，同理可得中位数=众数

若在中间：

若众数为$a[w]$

$len>mid$

∴$a[w\to w+len]=same$

又∵$w+len\le n$

∴$w<mid$

又因为$w+len>mid$

∴$a[mid]=a[w]$

综上所述，众数为中位数

证毕。

so，我们可以开一个权值线段树来统计序列中数的个数

用链表来存序列。。。。。。。。。。

权值线段树

权值线段树即一种线段树，以序列的数值为下标。
权值线段树维护一列数中数的个数。

也就是说，我们的权值线段树就是用线段树维护了一堆桶。

这就是权值线段树的概念。

权值线段树维护的是桶，按值域开空间，维护的是个数。

#include
#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;
}
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

完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。