SHARE
TWEET

Untitled

a guest Mar 25th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 400100, vc = 3 * maxn;
  6.  
  7. typedef struct edge {
  8.     int u, v, bt, et = -1;
  9.  
  10.     edge() {}
  11.  
  12.     edge(int u, int v, int bt) : u(u), v(v), bt(bt) {}
  13. };
  14.  
  15. int p[vc], sz[vc], nm[vc];
  16. stack<pair<int, pair<bool, int> > > st;
  17.  
  18. int getp(int x) {
  19.     if (p[x] == -1)
  20.         return x;
  21.     return getp(p[x]);
  22. }
  23.  
  24. void merges(int u, int v) {
  25.     u = getp(u);
  26.     v = getp(v);
  27.     if (u == v) {
  28.         st.push({-1, {-1, -1}});
  29.         return;
  30.     }
  31.     if (sz[u] < sz[v])
  32.         swap(u, v);
  33.     st.push({v, {(sz[u] == sz[v]), nm[u]}});
  34.     if (sz[v] == sz[u])
  35.         ++sz[u];
  36.     p[v] = u;
  37.     nm[u] = max(nm[v], nm[u]);
  38. }
  39.  
  40. void unmerge() {
  41.     int v = st.top().first, fg = st.top().second.first, stn = st.top().second.second;
  42.     st.pop();
  43.     if (v == -1)
  44.         return;
  45.     int u = p[v];
  46.     sz[u] -= fg;
  47.     nm[u] = stn;
  48.     p[v] = -1;
  49. }
  50.  
  51. int lb[4 * maxn], rb[4 * maxn];
  52. vector<int> t[4 * maxn];
  53. vector<edge> ed;
  54.  
  55. void build(int x, int cl, int cr) {
  56.     lb[x] = cl;
  57.     rb[x] = cr;
  58.     if (cr - cl == 1)
  59.         return;
  60.     build(2 * x, cl, (cl + cr) / 2);
  61.     build(2 * x + 1, (cl + cr) / 2, cr);
  62. }
  63.  
  64. int up(int x, int pos) {
  65.     while (1) {
  66.         for (int i = 0; i < t[x].size(); i++)
  67.             unmerge();
  68.         if (lb[x] <= pos && pos < rb[x])
  69.             return x;
  70.         x /= 2;
  71.     }
  72. }
  73.  
  74. int down(int x, int pos) {
  75.     for (int i = 0; i < t[x].size(); i++)
  76.         merges(ed[t[x][i]].u, ed[t[x][i]].v);
  77.     if (rb[x] - lb[x] == 1)
  78.         return x;
  79.     if ((lb[x] + rb[x]) / 2 <= pos)
  80.         return down(2 * x + 1, pos);
  81.     return down(2 * x, pos);
  82. }
  83.  
  84. void add_edge(int x, int cl, int cr, int _l, int _r, int i) {
  85.     if (_r <= cl || cr <= _l)
  86.         return;
  87.     if (_l <= cl && cr <= _r) {
  88.         t[x].push_back(i);
  89.         return;
  90.     }
  91.     add_edge(2 * x, cl, (cl + cr) / 2, _l, _r, i);
  92.     add_edge(2 * x + 1, (cl + cr) / 2, cr, _l, _r, i);
  93. }
  94.  
  95. int main(){
  96.     cin.tie(0);
  97.     cout.tie(0);
  98.     ios_base::sync_with_stdio(0);
  99.     int n, m;
  100.     cin >> n >> m;
  101.     vector<int> a(m);
  102.     for (int i = 0; i < m; i++) {
  103.         cin >> a[i];
  104.     }
  105.     for (int i = 0; i < n; i++) {
  106.         p[i] = -1; sz[i] = 1; nm[i] = -1;
  107.     }
  108.     for (int i = n; i < n + 2 * m; i++) {
  109.         p[i] = -1; sz[i] = 1; nm[i] = -1;
  110.     }
  111.     vector<int> lws(n);
  112.     for (int i = 0; i < n; i++)
  113.         lws[i] = i;
  114.     int nt = n;
  115.     pair<int, int> pr[m];
  116.     for (int i = 0; i < m; i++) {
  117.         --a[i];
  118.         pr[i] = {lws[a[i]], lws[a[i] + 1]};
  119.         ed.push_back(edge(lws[a[i]], nt + 2 * i + 1, 0));
  120.         ed.push_back(edge(lws[a[i] + 1], nt + 2 * i, 0));
  121.         lws[a[i]] = nt + 2 * i;
  122.         lws[a[i] + 1] = nt + 2 * i + 1;
  123.     }
  124.     for (int i = 0; i < n; i++)
  125.         nm[lws[i]] = i;
  126.     int pes = ed.size();
  127.     int q;
  128.     cin >> q;
  129.     vector<pair<int, int> > ans;
  130.     int cnt = 0;
  131.     for (int i = 0; i < q; i++) {
  132.         char cd;
  133.         int x;
  134.         cin >> cd >> x;
  135.         if (cd == 'A') {
  136.             --x;
  137.             if (a[x] == -1)
  138.                 continue;
  139.             a[x] = -1;
  140.             ++cnt;
  141.             ed.push_back(edge(pr[x].first, nt + 2 * x, cnt));
  142.             ed.push_back(edge(pr[x].second, nt + 2 * x + 1, cnt));
  143.             int e1 = 2 * x;
  144.             int e2 = 2 * x + 1;
  145.             ed[e1].et = cnt;
  146.             ed[e2].et = cnt;
  147.         } else {
  148.             ans.push_back({cnt, x});
  149.         }
  150.     }
  151.     build(1, 0, maxn);
  152.     for (int i = 0; i < ed.size(); i++) {
  153.         if (ed[i].et == -1) {
  154.             ed[i].et = maxn;
  155.             if (ed[i].bt == 0) {
  156.                 merges(ed[i].u, ed[i].v);
  157.                 continue;
  158.             }
  159.         }
  160.         add_edge(1, 0, maxn, ed[i].bt, ed[i].et, i);
  161.     }
  162.     int ls = 1;
  163.     for (int i = 0; i < ans.size(); i++) {
  164.         if (i != 0)
  165.             ls = up(ls, ans[i].first);
  166.         ls = down(ls, ans[i].first);
  167.         int gg = getp(ans[i].second - 1);
  168.         cout << nm[gg] + 1 << '\n';
  169.     }
  170.     exit(0);
  171. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top