Wuyanru's blog
0%

[NOI2022] 众数

发表于 分类于 ，

vp NOI的时候做的，场上想了一会，打了一会，就切了。

然后挂了 分。

题目链接

题意

定义一个序列的众数是序列中出现次数严格大于一半的数字，没有这样的数字则为 。

现在有很多个队列，其中编号为 的队列初始是“存在的”，剩余的队列初始是“不存在”的。

初始时这些队列中的元素已知，元素总数为 。现在还有 个操作，操作有以下几种：

  1. 在队列 末尾插入一个 ，保证 号队列此时"存在"，。
  2. 删除队列 末尾的数字，保证 号队列此时"存在"且非空，。
  3. 给出 个队列编号 ，求出这些队列拼接起来后元素的众数，不保证 互不相同。
  4. 新建一个编号为 的队列，由 和 首尾拼接构成，并将 设为存在， 设为不存在。保证 初始存在， 不存在。

设 为操作 中 的和。

题解

首先我们来考虑如何维护这些队列。

首先 deque 启发式合并不行，会 MLE（宝贵经验。

我们发现，所有有关队列的操作，都只和队列的首尾有关。

那么我们可以直接使用双向链表存下这些队列。

操作 和操作 直接更改结尾，操作 直接把两个链表首尾拼起来。

接下来就只剩操作 。

首先我们可以很容易地知道最后队列的长度，只需要把这 个链表的元素数量加一起就好了。

假设总长度为 ，那么我们其实就是要找到出现次数 的数字。

维护一个链表中每一个数字的出现次数很简单，只需要一个 map 或 set 就够了。

但是我们需要合并信息，map 和 set 显然不可以。

我们可以比较容易想到，使用动态开点线段树维护每一个数字的出现次数，操作 只需要线段树合并就可以了。

对于操作 ，我们直接用一个数组存储来所有线段树的根，然后查询的过程中一起往下跳，每一次跳到数字总数更多的一遍，最后特判就好了。

链表合并不要写挂！

链表合并不要写挂！！

链表合并不要写挂！！！

代码

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
#include<cassert>
#include<cstdio>
using namespace std;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int ls[22000001];
int rs[22000001];
int c[22000001];
int root[1500001];
int tail[1000001];
int nx[2000001];
int lt[2000001];
int v[2000001];
int p[500001];
int n,m,k;
int tot;
int cnt;
ll siz;
inline void debug(int p)
{
    if(!p) return ;
    printf("%d ",v[p]);
    debug(nx[p]);
}
void add(int &p,int pl,int pr,int x,int y)
{
    if(!p) p=++tot;
    c[p]+=y;
    if(pl==pr) return ;
    int mid=(pl+pr)>>1;
    if(x<=mid) add(ls[p],pl,mid,x,y);
    else add(rs[p],mid+1,pr,x,y);
}
int merge(int u,int v,int pl,int pr)
{
    if(!u||!v) return u|v;
    if(pl==pr)
    {
        c[u]+=c[v];
        return u;
    }
    int mid=(pl+pr)>>1;
    ls[u]=merge(ls[u],ls[v],pl,mid);
    rs[u]=merge(rs[u],rs[v],mid+1,pr);
    c[u]=c[ls[u]]+c[rs[u]];
    return u;
}
int get(int pl,int pr)
{
    if(pl==pr)
    {
        ll num=0;
        for(int i=1;i<=k;i++) num+=c[p[i]];
        if(num>=siz) return pl;
        return -1;
    }
    int mid=(pl+pr)>>1;ll num=0;
    for(int i=1;i<=k;i++) num+=c[ls[p[i]]];
    if(num>=siz)
    {
        for(int i=1;i<=k;i++) p[i]=ls[p[i]];
        return get(pl,mid);
    }
    for(int i=1;i<=k;i++) p[i]=rs[p[i]];
    return get(mid+1,pr);
}
int main()
{
    n=read(),m=read(),cnt=n+m;
    for(int i=1;i<=n;i++)
    {
        int lst=i;k=read();
        for(int j=1;j<=k;j++)
        {
            v[++cnt]=read();
            nx[lst]=cnt,lt[cnt]=lst;
            add(root[i],0,n+m,v[cnt],1);
            lst=cnt;
        }
        tail[i]=lst;
        // debug(nx[i]);
        // printf("\n");
    }
    for(int i=1;i<=m;i++)
    {
        int op=read();
        if(op==1)
        {
            int x=read(),p=tail[x];
            v[++cnt]=read();
            nx[p]=cnt,lt[cnt]=p;
            tail[x]=cnt;
            add(root[x],0,n+m,v[cnt],1);
        }
        else if(op==2)
        {
            int x=read();
            add(root[x],0,n+m,v[tail[x]],-1);
            tail[x]=lt[tail[x]];
            nx[tail[x]]=0;
        }
        else if(op==3)
        {
            k=read(),siz=0;
            for(int j=1;j<=k;j++)
            {
                int u=read();
                p[j]=root[u];
                siz+=c[root[u]];
                if(nx[u]) assert(lt[nx[u]]==u);
            }
            siz=siz/2+1;
            printf("%d\n",get(0,n+m));
        }
        else
        {
            int x1=read(),x2=read(),x3=read();
            if(!nx[x1]&&!nx[x2]) tail[x3]=x3;
            else if(!nx[x1]) nx[x3]=nx[x2],tail[x3]=tail[x2],lt[nx[x3]]=x3;
            else if(!nx[x2]) nx[x3]=nx[x1],tail[x3]=tail[x1],lt[nx[x3]]=x3;
            else
            {
                nx[x3]=nx[x1],tail[x3]=tail[x2];
                nx[tail[x1]]=nx[x2];
                lt[nx[x2]]=tail[x1];
                lt[nx[x3]]=x3;
            }
            root[x3]=merge(root[x1],root[x2],0,n+m);
            // debug(nx[x3]);
            // printf("\n");
        }
    }
    return 0;
}

感谢观看！