「成都七中D6T1」初夏 - 中位数/线段树 | Bill Yang's Blog

「成都七中D6T1」初夏 - 中位数/线段树

题目大意

    依稀记得我似乎是在初夏退役的QAQ。
    给定一个长为$N$的序列,第$i$个数记为$A_i$。
    有$Q$次询问,每次询问一个区间是否有严格众数(出现次数大于一半),如果有请输出这个数,否则输出$-1$。

题目分析

首先,不难发现严格众数就是中位数,因此就变成了主席树维护区间中位数。

xyj发现了一种线段树+离线处理的方法。
不难发现,在线段树中,严格众数只可能在其两个儿子的任意一个众数中产生。

因此,我们先用线段树预处理每个结点的可能的严格众数,再将所有询问插入线段树拆成共$O(q\log n)$个区间。
接下来,我们判断对每个询问在这些可能的严格众数中真正的严格众数是谁,我们可以离线的枚举位置,将区间转化为$+1,-1$标记,统计每个数出现次数即可。

代码

主席树的代码就不贴了。

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=500005;

int n,q,a[maxn];
vector<int>pos[maxn];

struct Query {
int id,left,right,num,sum;
Query(int _id=0,int l=0,int r=0,int x=0,int s=0):id(_id),left(l),right(r),num(x),sum(s) {}
} Q[maxn*35];

int tot;
vector<int>Add[maxn],Del[maxn];

struct Segment_Tree {
struct Tree {
int left,right;
int num;
Tree(int l=0,int r=0,int x=-1):left(l),right(r),num(x) {}
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].num=a[Left];
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
int query(int x,int l,int r) {
return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l);
}
void push_up(int index) {
int suml=query(tree[ls].num,tree[index].left,tree[index].right),sumr=query(tree[rs].num,tree[index].left,tree[index].right);
if(suml>sumr)tree[index].num=tree[ls].num;
else tree[index].num=tree[rs].num;
}
void insert(int index,int Left,int Right,int id) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
Q[++tot]=Query(id,Left,Right,tree[index].num,0);
Del[Left-1].push_back(tot);
Add[Right].push_back(tot);
return;
}
insert(ls,Left,Right,id);
insert(rs,Left,Right,id);
}
} st;

int Hash[maxn],ans[maxn];

void solve() {
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
pos[a[i]].push_back(i);
}
st.build(1,1,n);
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int();
ans[i]=-1;
st.insert(1,x,y,i);
}
for(int i=0; i<=n; i++) {
if(i>0)Hash[a[i]]++;
for(int j=0; j<Del[i].size(); j++) {
Query& Now=Q[Del[i][j]];
Now.sum-=Hash[Now.num];
}
for(int j=0; j<Add[i].size(); j++) {
Query& Now=Q[Add[i][j]];
Now.sum+=Hash[Now.num];
}
}
for(int i=1; i<=tot; i++)
if(Q[i].sum>(Q[i].right-Q[i].left+1)/2)ans[Q[i].id]=Q[i].num;
for(int i=1; i<=q; i++)printf("%d\n" ,ans[i]);
return;
}

int main() {
n=Get_Int();
q=Get_Int();
solve();
return 0;
}

姥爷们赏瓶冰阔落吧~
0%