Traffic Lights

题目描述

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$.

题意概述

一条长为$s$的公路上有$n$个红绿灯。第$i$个红绿灯在距离起点$x_i$的位置上,周期是$r_i$单位时间红灯加$g_i$单位时间绿灯,第一次从绿灯变成红灯的时刻是$d_i$。一辆车以速度$v_0$从起点开到终点,途中不能停顿。求在$v_{\min} \le v_0 \le v_{\max}$且闯过的红灯数最少的情况下,$v_0$的最大值。
数据范围:$1 \le n \lt 20000, \; 1 \le s \le 20000, \; 10 \le v_{\min} \le v_{\max} \le 50$。

算法分析

把速度看成数轴,那么每个红绿灯可以对应到数轴上的若干个区间——即若$v_0 \in [l, r]$,则经过这个红绿灯时闯了红灯。
由于题目的特殊限制($10 \le r_i, g_i \le 20, \; 10 \le v_{\min} \le v_0 \le v_{\max} \le 50$),这样的区间不会太多,可以把它们都求出来。问题转化成求数轴上一个点使得覆盖它的区间数最少。离散化后模拟即可。

代码

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

Dynamic Rankings

题目描述

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.
Your task is to write a program for this computer, which

  • 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$.

题意概述

有一个长度为$N$的数列。有$M$次操作,每次操作询问数列第$i$项到第$j$项之间的第$k$小值,或者将第$i$项修改为$t$。
数据范围:$1 \le N \le 50000, \; 1 \le M \le 10000$。
内存限制:$32$M。

算法分析

对于这种询问区间第$k$小值的题目,很容易想到主席树。但由于主席树是一种类似前缀和的结构,一次修改操作需要修改$O(N)$棵线段树。这显然不是我们所希望的。
既然主席树类似前缀和,那么就可以借用维护前缀和的工具——树状数组。把树状数组的每个节点看成一棵线段树,这样一次修改操作就只需要修改$O(\log N)$棵线段树,时间复杂度为$O(\log^2N)$。而询问操作需要先把该询问在树状数组上用到的节点提取出来(有$O(\log N)$个),然后利用类似主席树的方法二分,时间复杂度也是$O(\log^2N)$。
但是!这题的内存限制非常小,接受不了$O((N+M)\log^2N)$的空间复杂度。再考虑主席树,它的空间复杂度是$O(N\log N)$的。因此可以对原序列建立静态的主席树,对修改操作利用树状数组维护,这样空间复杂度降至$O(N\log N+M\log^2N)$,可以通过。

代码

/*
 * 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
        bit_add(q[i].i, mp[a[q[i].i]], -1),
            bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1);
    }
  }
  return 0;
}

Sum of Medians

题目描述

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.

题意概述

有一个初始为空的集合。有三种操作:①向集合中加入一个元素,保证操作前这个元素不存在;②从集合中删除一个元素,保证操作前这个元素存在;③询问集合中元素排序后下标模$5$余$3$的元素之和。共有$n$次操作。
数据范围:$1 \le n \le 10^5$。

算法分析1

直接用平衡树来维护。对于每个节点储存它子树的大小以及它子树排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。显然,一个节点的左子树可以直接更新当前节点,而右子树则需根据左子树的大小进行处理后再更新当前节点。

代码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;
}

算法分析2

将操作离线,并将所有操作数离散化,用线段树来维护离散后的区间。和平衡树类似,对于每个节点储存区间内的元素个数以及区间内的元素排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。更新操作也大同小异。