Data Structure Problem

题目链接

题意

要求实现一种数据结构，能够：
插入一个二元点对
删除还存在的第$r$个点对
查询现有数据结构中两个二元点对点积最小

思路

首先点积无论最大还是最小一定在凸包上（证明待补?).
由于数据随机，凸包上的店的个数期望是$log(n)$个，所以删除一个点的概率是$\frac{log(n)}{n}$.
我们维护这个凸包，如果删除了这上面的元素，我们就暴力重建凸包。
还有一个数据结构维护已插入的点，如平衡树。
存档凸包模板。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const int N = 1e6 + 5;
int X[N], Y[N];

namespace Treap
{
    ll seed = 17124057;
    #define ls(x) treap[x].child[0]
    #define rs(x) treap[x].child[1]
    int cur = 0;
    ll Rand()
    {
        return seed = seed * 48271 % 2147483647;
    }
    int rt;
    void init()
    {
        rt = cur = 0;
    }
    struct node
    {
        int val, key, child[2], size;
    }treap[N];
    void pushup(int root)
    {
        treap[root].size = treap[ls(root)].size + treap[rs(root)].size + 1;
    }

    void split(int root, int& x, int& y, int val)
    {
        if (!root)
        {
            x = y = 0;
            return;
        }
        if (treap[root].val <= val)
        {
            x = root;
            split(rs(root), rs(x), y, val);
        }
        else
        {
            y = root;
            split(ls(root), x, ls(y), val);
        }
        pushup(root);
    }

    void merge(int &root, int x, int y)
    {
        if (!x || !y)
        {
            root = x + y;
            return;
        }
        if (treap[x].key < treap[y].key)
        {
            root = x;
            merge(rs(root), rs(x), y); 
        }
        else
        {
            root = y;
            merge(ls(root), x, ls(y));
        }
        pushup(root);
    }

    void insert(int& root, int val)
    {
        int x = 0, y = 0, z = ++cur;
        treap[z].val = val;
        treap[z].size = 1;
        ls(z) = rs(z) = 0;
        treap[z].key = Rand();
        split(root, x, y, val);
        merge(x, x, z);
        merge(root, x, y);
    }

    void del(int& root, int val)
    {
        int x = 0, y = 0, z = 0;
        split(root, x, y, val);
        split(x, x, z, val - 1);
        merge(z, ls(z), rs(z));
        merge(x, x, z);
        merge(root, x, y);
    }

    int query_rank(int& root, int val)
    {
        int x = 0, y = 0;
        split(root, x, y, val - 1);
        int ans = treap[x].size + 1;
        merge(root, x, y);
        return ans;
    }

    int query_value(int root, int rnk)
    {
        while (treap[ls(root)].size + 1 != rnk)
        {
            if (treap[ls(root)].size >= rnk)
            {
                root = ls(root);
            }
            else
            {
                rnk -= treap[ls(root)].size + 1;
                root = rs(root);
            }
        }
        return treap[root].val;
    }

    int pre_val(int& root, int val)
    {
        int x = 0, y = 0;
        split(root, x, y, val - 1);
        int ans, tmp = x;
        while (rs(tmp))
        tmp = rs(tmp);
        ans = treap[tmp].val;
        merge(root, x, y);
        return ans;
    }

    int suf_val(int& root, int val)
    {
        int x = 0, y = 0;
        split(root, x, y, val);
        int ans, tmp = y;
        while (ls(tmp))
        tmp = ls(tmp);
        ans = treap[tmp].val;
        merge(root, x, y);
        return ans;
    }
}//namespace Treap

namespace ConvexHull
{
    struct point
    {
        int x, y;
        int id;
        point(int _x = 0, int _y = 0, int _id = 0): x(_x), y(_y), id(_id) {}
        bool operator < (const point &v) const
        {
            return x < v.x || (x == v.x && y < v.y);
        }
        point operator - (const point &v) const
        {
            return point(x - v.x, y - v.y);
        }
    };
    inline ll cross (const point& a, const point& b, const point& c)
    {
        point p = a - c, q = b - c;
        return 1ll * p.x * q.y - 1ll * p.y * q.x;
    }
    vector<int> arr;
    void clear()
    {
        arr.clear();
    }
    void go()
    {
        vector<point> s;
        for (auto &i : arr)
            s.push_back(point(X[i], Y[i], i));
        if ((int)s.size() > 2)
        {
            sort(s.begin(), s.end());
            vector<point> ret(s.size() * 2);
            int sz = 0;
            for (int i = 0; i < s.size(); i++)
            {
                while (sz > 1 && cross(ret[sz - 1], s[i], ret[sz - 2]) < 0)
                    sz--;
                ret[sz++] = s[i];
            }
            int k = sz;
            for (int i = (ll)s.size() - 2; i >= 0; i--)
            {
                while (sz > k && cross(ret[sz - 1], s[i], ret[sz - 2]) < 0)
                    sz--;
                ret[sz++] = s[i];
            }
            ret.resize(sz - ((int)s.size() > 1));
            s = ret;
        }
        arr.clear();
        for (auto &p : s)
            arr.push_back(p.id);
    }
    void insert(int index)
    {
        arr.push_back(index);
        go();
    }
    void dfs(int rtt)
    {
        if (!rtt)
            return;
        arr.push_back(Treap::treap[rtt].val);
        dfs(Treap::ls(rtt));
        dfs(Treap::rs(rtt));
    }
    void erase(int index)
    {
        if (find(arr.begin(), arr.end(), index) != arr.end())
        {
            dbg("found on hull");
            arr.clear();
            dfs(Treap::rt);
            go();
        }
    }
}//namespace ConvexHull

const unsigned mul = 20190812;

class Magic {
public:
  Magic(unsigned state): state(state), ans(0) {}

  unsigned long long retrieve() {
    unsigned modulo = 0x7fffffff;
    state = ((unsigned long long) state * mul + ans) % modulo;
    unsigned high = state;
    state = ((unsigned long long) state * mul + ans) % modulo;
    return high * modulo + state;
  }

  int retrieve(int a, int b) {
    assert (a <= b);
    return (int) (retrieve() % (b - a + 1)) + a;
  }

  void submit(unsigned k) {
    ans = ans * mul + k;
  }

  unsigned retrieveAns() {
    return ans;
  }

private:
  unsigned state, ans;
};

class DataStructure {
public:
  DataStructure() {
    // The data structure is initially empty, until it's not.
    // Implement your initialization here.
    index = 0;
    ConvexHull::clear();
    Treap::init();
  }
  void add(int x, int y) {
    // Add a 2D point (x, y) to the DS.
    // Implement your add here.
    index++;
    dbg("add", index, x, y);
    X[index] = x;
    Y[index] = y;
    Treap::insert(Treap::rt, index);
    ConvexHull::insert(index);
  }
  void erase(int r) {
    // Erase the r-th added point, of all the points that
    // have still not been erased.
    // Implement your erase here.
    dbg("erase", r);
    assert(Treap::cur != 0);
    r = Treap::query_value(Treap::rt, r);
    Treap::del(Treap::rt, r);
    ConvexHull::erase(r);
  }
  int size() {
    // Return how many points are still in the DS
    return Treap::treap[Treap::rt].size;
  }
  pair<unsigned, unsigned> query() {
    // find two points p_i, p_j in the DS (not necessarily distinct),
    // such that the dot product of these two <p_i, p_j> (i <= j)
    // the smallest among all. Return (i, j).
    // If the DS is empty for now, return (0, 0).
    // Implement your query here.
    // If there are multiple (i, j) satisfying the condition, output the lexicographically smallest pair.
    ll ans = 9E18;
    pair<unsigned, unsigned> best = {0, 0};
    for (auto &i : ConvexHull::arr)
        for (auto &j : ConvexHull::arr)
        {
            ll dot_product = 1ll * X[i] * X[j] + 1ll * Y[i] * Y[j];
            if (dot_product < ans)
            {
                ans = dot_product;
                best = {i, j};
            }
        }
    if (best.first > best.second)
        swap(best.first, best.second);
    return best;
  }
private:
    int index;
};

template <class T>
void read(T& ret)
{
    ret = 0;
    char c;
    while ((c = getchar()) > '9' || c < '0');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + c - '0';
        c = getchar();
    }
}
char s[N];
int main() {
  const int lim = 1E9;
  int q;
  read(q);
  for (int k = 0; k < q; ++k) {
    unsigned state;
    read(state);
       scanf("%s", s);
    int len = strlen(s);
    DataStructure ds;
    Magic magic(state);
    for (int i = 0; i < len; i++) {
      char c = s[i];
      if (c == 'a') {
        // add one point
        int x = magic.retrieve(-lim, lim);
        int y = magic.retrieve(-lim, lim);
        ds.add(x, y);
      } else if (c == 'e') {
        // select the lucky point
        unsigned pos = magic.retrieve(1, ds.size());
        ds.erase((int)pos);
      } else if (c == 'q') {
        // query global minimum
        auto best = ds.query();
        magic.submit(best.first);
        magic.submit(best.second);
      }
    }
    printf("%u\n", magic.retrieveAns());
  }
  return 0;
}