翻车笔记_ KPI [线段树, 权值线段树, 动态区间第k大]

需要注意一些细节

懵逼的 题目

传送至 HDU

扯淡的 题解

case打成canse错了整整两页显得非常开心

怀疑人生.jpg

啊…总的来说是一道很简单的权值线段树裸题...@丁虚高
比起逆序对就是多了一个出队(修改值为0就好了)…
然后二分找中位数…
cx(le, ri, k)可以返回在[le, ri]区间中第k大的数(离散化后的值)
设区间中点为mi = (le + ri) >> 1
如果在区间[le, mi]中比mi小的数(b[LS(dq)].zh)大于等于给定的k, 那么说明区间内第k大的数肯定在左子区间内, 否则左区间内比zh[k]小的数不足k个, 则说明zh[k]一定在右子区间才能满足是区间的第k

没了, 注意两个细节:

  • Case不是Canse23333333333
  • 初始化, 注意输入的值可能为0, 所以不能把输入的数组初始化为0, 而且输入数组是一定要初始化的, 因为有的时间点没有in不会覆盖之前的值

还有…这个题真的很值得吐槽啊!!! QAQ

这里写图片描述

注: 按照第一次出场顺序分别为 张飞, 赵云, 关羽, 马超, 黄忠

GG

沙茶的 代码

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
// HDU5249

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define MAXN (10000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct node
{
int le;
int ri;
int zh;
} b[MAXN << 2];

int n;
int dqn;
char srs[MAXN][20];
int srx[MAXN], c[MAXN];

void init();
void solve();
void js(int, int, int);
void xg(int, int, int);
int cx(int, int, int);
int cx2(int, int, int, int);
bool cmp(int, int);
int main()
{
#define DEBUG

#ifdef DEBUG
freopen("in.in", "r", stdin);
freopen("wa.out", "w", stdout);
#endif
// ios::sync_with_stdio(false);
// cin.tie(NULL);
int ca = 0;
while (~scanf("%d", &dqn))
{
printf("Case #%d:\n", ++ca);
// cout << "Case #" << ++ca << ":" << endl;
init();
solve();
}
return 0;
}
void init()
{
memset(srx, -1, sizeof(srx));
memset(c, 0x7f, sizeof(c));
c[0] = 0;
for (int i = 1; i <= dqn; i++)
{
scanf("%s", srs[i]);
// cin >> srs[i];
if (srs[i][0] == 'i')
{
// cin >> srx[i];
scanf("%d", &srx[i]);
c[++c[0]] = srx[i];
}
}
n = c[0];
sort(c + 1, c + n + 1, cmp);
n = unique(c + 1, c + n + 1) - c - 1;
for (int i = 1; i <= dqn; i++)
{
if (srx[i] >= 0)
srx[i] = lower_bound(c + 1, c + n + 1, srx[i]) - c;
}
js(1, 1, n);
}
void solve()
{
queue<int> q;
for (int i = 1; i <= dqn; i++)
{
if (srs[i][0] == 'i')
{
q.push(srx[i]);
xg(1, srx[i], 1);
}
else if (srs[i][0] == 'q')
cout << c[cx2(1, 1, n, q.size() / 2 + 1)] << endl;
else if (srs[i][0] == 'o')
{
xg(1, q.front(), -1);
q.pop();
}
}
}
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri, b[dq].zh = 0;
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
void xg(int dq, int wz, int zh)
{
if (b[dq].le == b[dq].ri && b[dq].le == wz)
{
b[dq].zh += zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz, zh);
else
xg(RS(dq), wz, zh);
// (wz <= mi) ? (xg(LS(dq), wz, zh)) : (xg(RS(dq), wz, zh));
b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
/*int cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
int mi = (b[dq].le + b[dq].ri) >> 1;
// return ((ri <= mi) ? cx(LS(dq), le, ri) : ((le > mi) ? cx(RS(dq), le, ri) : (cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri))))
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}*/
int cx2(int dq, int le, int ri, int k)
{
if (le == ri)
return ri;
int mi = /*(le + ri) >> 1*/(b[dq].le + b[dq].ri) >> 1;
int x = /*cx(1, le, mi)*/b[LS(dq)].zh;
if (k > x)
return cx2(RS(dq), mi + 1, ri, k - x);
else
return cx2(LS(dq), le, mi, k);
}
bool cmp(int x, int y)
{
return x < y;
}

/*
6
in 874
query
out
in 24622
in 12194
query
*/

By 心态略崩的 Cansult