## 题目描述

The main street of Berland’s capital is a segment with length $s$. The main street has traffic lights installed along it. The traffic lights have been functioning since time immemorial, cyclically changing colors from red to green and vice versa. Each traffic light can be described by four numbers $x_i, r_i, g_i, d_i$, which stand for:

• $x_i$ – the distance from the beginning of the street to the traffic light ($1 \le x_i \lt s$),
• $r_i$ – the duration of the red light illumination ($10 \le r_i \le 20$),
• $g_i$ – the duration of the green light illumination ($10 \le g_i \le 20$),
• $d_i$ – the minimum non-negative moment of time when the traffic light changes the light from green to red ($0 \le d_i \lt r_i+g_i$).

Each traffic light retains its light cycle from the ancient past.
The King of Berland asked the transport minister to customize the traffic lights according to a “green wave” principle. That means that if you start driving from the beginning of the street at the recommended speed, you can drive through the entire street without stopping, that is, you pass each traffic light when it has the green light on.
Now it is time to show the “green wave” to the King, but the work is not even started yet. You may assume that the King starts driving at the moment of time $0$ from the beginning of the street. So the minister decided to choose some speed $v_0$ and tell the king that the “green wave” works specifically for this speed. Moreover, they can switch any number of traffic lights to the “always green” mode. The minister’ aim is to ensure that if the King drives through the street at the recommended speed $v_0$ he encounters no red traffic light. Driving exactly at the moment when the colors are changed is not considered driving through the red light.
Any transport’s maximum speed is limited in Berland: it should not exceed $v_{\max}$. On the other hand, the King will be angry if the recommended speed is less than $v_{\min}$. Thus, the minister should choose such value of $v_0$, which satisfies the inequation $v_{\min} \le v_0 \le v_{\max}$.
Help the minister to find such $v_0$ value, that the number of traffic lights to switch to the “always green” mode is minimum. If $v_0$ is not uniquely defined, choose the maximum possible value of $v_0$.

## 代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 20005;
static double const EPS = 1e-12;

int pm(double const &n) {
return fabs(n) < EPS ? 0 : n < 0 ? -1 : 1;
}

std::bitset<N> ans, cur;
struct Query {
int id, op;
double x;
friend bool operator<(Query const &a, Query const &b) {
return pm(a.x - b.x) ? !~pm(a.x - b.x) : a.op < b.op;
}
} itv[N * 100];

int main() {
int n, s, vmn, vmx, top = 0;
scanf("%d%d%d%d", &n, &s, &vmn, &vmx);
for (int i = 0, x, r, g, d; i < n; ++i) {
scanf("%d%d%d%d", &x, &r, &g, &d);
if (d > g) {
double l = 1. * x / (d - g);
itv[top++] = (Query){i, 1, l};
}
for (;; d += r + g) {
double l = 1. * x / (d + r), r = d ? 1. * x / d : 1e9;
if (pm(r - vmn) < 1) {
break;
}
if (pm(vmx - l) < 1) {
continue;
}
itv[top++] = (Query){i, 1, l}, itv[top++] = (Query){i, -1, r};
}
}
itv[top++] = (Query){n, 1, 0. + vmx};
std::sort(itv, itv + top);
int ac = n, cc = 0;
double vc = 0;
for (int i = 0; i < n; ++i) {
ans.set(i);
}
for (int i = 0; i < top && pm(itv[i].x - vmx) < 1; ++i) {
if (itv[i].op == 1) {
if (cc <= ac && pm(vmn - itv[i].x) < 1) {
ans = cur, ac = cc, vc = itv[i].x;
}
if (itv[i].id < n) {
cur.set(itv[i].id), ++cc;
}
} else {
cur.reset(itv[i].id), --cc;
}
}
printf("%.10lf\n%d\n", vc, ac);
for (int i = 0; i < n; ++i) {
if (ans.test(i)) {
printf("%d ", i + 1);
}
}
puts("");
return 0;
}


## 题目描述

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.

• Reads $N$ numbers from the input.
• Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.

## 代码

/*
* Beware of Bigfoot!
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>

static int const N = 60005;
static int const NM = 2000000;
int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N];
struct Query {
int o, i, j, k;
} q[N];
struct SegmentTree {
int ch[2], sum;
} nd[NM];

int create(int rt = 0) { return nd[++nn] = nd[rt], nn; }

int arr_insert(int rt, int p) {
rt = create(rt), ++nd[rt].sum;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum,
cur = nd[cur].ch[b];
b ? L = MID + 1 : R = MID;
}
return rt;
}

void bit_insert(int &rt, int p, int v) {
if (rt == 0)
rt = create();
nd[rt].sum += v;
int L = 0, R = N;
for (int cur = rt; L < R;) {
int MID = L + R >> 1, b = p > MID;
if (nd[cur].ch[b] == 0)
nd[cur].ch[b] = create();
nd[nd[cur].ch[b]].sum += v;
int tmp = nd[cur].ch[b];
cur = tmp, b ? L = MID + 1 : R = MID;
}
}

int bit_add(int p, int v, int c) {
for (; p <= n; p += p & -p)
bit_insert(bit_rt[p], v, c);
}

int main() {
int T;
scanf("%d", &T);
for (; T--;) {
std::map<int, int> mp;
memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), mp[a[i]] = 0;
for (int i = 1; i <= m; ++i) {
char c;
scanf(" %c", &c);
if (c == 'Q')
q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
else
q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0;
}
int cnt = 0;
for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
rec[cnt] = it->first, it->second = cnt++;
for (int i = 1; i <= n; ++i)
arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]);
for (int i = 1; i <= m; ++i) {
if (q[i].o == 0) {
std::vector<int> a, b;
a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]);
for (int p = q[i].i - 1; p; p -= p & -p)
a.push_back(bit_rt[p]);
for (int p = q[i].j; p; p -= p & -p)
b.push_back(bit_rt[p]);
int L = 0, R = N;
for (; L < R;) {
int sum = 0;
for (int i = 0; i < a.size(); ++i)
sum -= nd[nd[a[i]].ch[0]].sum;
for (int i = 0; i < b.size(); ++i)
sum += nd[nd[b[i]].ch[0]].sum;
int MID = L + R >> 1;
if (sum < q[i].k) {
L = MID + 1, q[i].k -= sum;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[1];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[1];
} else {
R = MID;
for (int i = 0; i < a.size(); ++i)
a[i] = nd[a[i]].ch[0];
for (int i = 0; i < b.size(); ++i)
b[i] = nd[b[i]].ch[0];
}
}
printf("%d\n", rec[L]);
} else
}
}
return 0;
}


## 题目描述

In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it’s the third largest element for a group of five). To increase the algorithm’s performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.
A sum of medians of a sorted $k$-element set $S={a_1, a_2, \ldots, a_k}$, where $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_k$, will be understood by as $\sum_{i \bmod 5=3} a_i$.
The $\bmod$ operator stands for taking the remainder, that is $x \bmod y$ stands for the remainder of dividing $x$ by $y$.
To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

## 代码1

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long n, x;
string o;
struct treap {
int tot, root;
struct node_type {
int child[2], rank;
long long val, size, mod[5];
} node[100001];
void update(int t) {
node[t].size = node[node[t].child[0]].size + node[node[t].child[1]].size + 1;
for (int i = 0; i < 5; ++i)
node[t].mod[i] = node[node[t].child[0]].mod[i] + node[node[t].child[1]].mod[(i + 99999 - node[node[t].child[0]].size) % 5];
node[t].mod[(node[node[t].child[0]].size + 1) % 5] += node[t].val;
}
void rotate(int &t, int dire) {
int p = node[t].child[!dire];
node[t].child[!dire] = node[p].child[dire], node[p].child[dire] = t;
update(t), update(p), t = p;
}
void insert(int &t, long long val) {
if (!t) {
t = ++tot, node[t].rank = ((rand() & ((1 << 16) - 1)) << 10) ^ rand(), node[t].val = node[t].mod[1] = val, node[t].size = 1;
return;
}
++node[t].size;
if (val < node[t].val) {
insert(node[t].child[0], val);
if (node[node[t].child[0]].rank > node[t].rank) rotate(t, 1);
} else {
insert(node[t].child[1], val);
if (node[node[t].child[1]].rank > node[t].rank) rotate(t, 0);
}
update(t);
}
void remove(int &t, long long val) {
if (!node[t].child[0] && !node[t].child[1]) { t = 0; return; }
if (val == node[t].val) {
if (node[node[t].child[0]].rank > node[node[t].child[1]].rank) rotate(t, 1);
else rotate(t, 0);
}
if (val < node[t].val) remove(node[t].child[0], val);
else remove(node[t].child[1], val);
update(t);
}
long long query() { return node[root].mod[3]; }
} tree;
int main()
{
srand(time(NULL));
cin >> n;
while (n--) {
cin >> o;
if (o[0] == 'a') { cin >> x; tree.insert(tree.root, x); }
else if (o[0] == 'd') { cin >> x; tree.remove(tree.root, x); }
else cout << tree.query() << endl;
}
return 0;
}