fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INFLL = (1LL<<60);
  5.  
  6. struct Node {
  7.     Node *l,*r;
  8.     int pr, sz;
  9.     ll val, mn, mx;
  10.     bool rev;
  11.     Node(ll v=0): l(nullptr), r(nullptr), pr((rand()<<16)^rand()), sz(1), val(v), mn(v), mx(v), rev(false) {}
  12. };
  13. int sz(Node* t){ return t? t->sz : 0; }
  14. void pull(Node* t){ if(!t) return; t->sz = 1 + sz(t->l) + sz(t->r); t->mn = t->val; t->mx = t->val;
  15.     if(t->l){ t->mn = min(t->mn, t->l->mn); t->mx = max(t->mx, t->l->mx); }
  16.     if(t->r){ t->mn = min(t->mn, t->r->mn); t->mx = max(t->mx, t->r->mx); }
  17. }
  18. void push(Node* t){ if(!t || !t->rev) return; t->rev = false; swap(t->l, t->r); if(t->l) t->l->rev ^= 1; if(t->r) t->r->rev ^= 1; }
  19.  
  20. Node* merge(Node* a, Node* b){
  21.     if(!a) return b; if(!b) return a;
  22.     push(a); push(b);
  23.     if(a->pr < b->pr){ a->r = merge(a->r, b); pull(a); return a; }
  24.     else { b->l = merge(a, b->l); pull(b); return b; }
  25. }
  26. void split(Node* t, int k, Node*& a, Node*& b){ // first k nodes -> a
  27.     if(!t){ a=b=nullptr; return; }
  28.     push(t);
  29.     int lsz = sz(t->l);
  30.     if(lsz >= k){
  31.         split(t->l, k, a, t->l);
  32.         pull(t);
  33.         b = t;
  34.     } else {
  35.         split(t->r, k - lsz - 1, t->r, b);
  36.         pull(t);
  37.         a = t;
  38.     }
  39. }
  40.  
  41. // treap helpers
  42. ll treap_range_min(Node*& root, int l, int r){
  43.     Node *a,*b,*c;
  44.     split(root, r, a, b);
  45.     split(a, l-1, c, a);
  46.     ll ans = (a? a->mn : INFLL);
  47.     a = merge(c, a);
  48.     root = merge(a, b);
  49.     return ans;
  50. }
  51. ll treap_range_max(Node*& root, int l, int r){
  52.     Node *a,*b,*c;
  53.     split(root, r, a, b);
  54.     split(a, l-1, c, a);
  55.     ll ans = (a? a->mx : -INFLL);
  56.     a = merge(c, a);
  57.     root = merge(a, b);
  58.     return ans;
  59. }
  60.  
  61. // HLD
  62. int N,Q;
  63. vector<vector<int>> adj;
  64. vector<int> parentv, depthv, heavy, head, pos, szv, invpos;
  65. int curPos;
  66. vector<ll> weightv;
  67.  
  68. int dfs1(int v,int p){
  69.     parentv[v]=p; depthv[v]=(p==-1?0:depthv[p]+1);
  70.     int size=1, maxc=0; heavy[v]=-1;
  71.     for(int to: adj[v]) if(to!=p){
  72.         int s = dfs1(to, v);
  73.         if(s>maxc){ maxc=s; heavy[v]=to; }
  74.         size += s;
  75.     }
  76.     szv[v]=size; return size;
  77. }
  78. void dfs2(int v,int h){
  79.     head[v]=h; pos[v]=curPos; invpos[curPos]=v; curPos++;
  80.     if(heavy[v]!=-1) dfs2(heavy[v], h);
  81.     for(int to: adj[v]) if(to!=parentv[v] && to!=heavy[v]) dfs2(to, to);
  82. }
  83. struct Seg { int l,r; bool rev; };
  84. vector<Seg> getPathSegments(int u,int v){
  85.     vector<Seg> up, down;
  86.     while(head[u] != head[v]){
  87.         if(depthv[head[u]] >= depthv[head[v]]){
  88.             up.push_back({pos[head[u]], pos[u], true});
  89.             u = parentv[head[u]];
  90.         } else {
  91.             down.push_back({pos[head[v]], pos[v], false});
  92.             v = parentv[head[v]];
  93.         }
  94.     }
  95.     if(pos[u] <= pos[v]) up.push_back({pos[u], pos[v], false});
  96.     else up.push_back({pos[v], pos[u], true});
  97.     for(int i=(int)down.size()-1;i>=0;--i) up.push_back(down[i]);
  98.     return up;
  99. }
  100.  
  101. int main(){
  102.     ios::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.     srand(1234567);
  105.     if(!(cin>>N>>Q)) return 0;
  106.     weightv.assign(N+1,0);
  107.     for(int i=1;i<=N;i++) cin>>weightv[i];
  108.     adj.assign(N+1,{});
  109.     for(int i=0;i<N-1;i++){ int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); }
  110.     parentv.assign(N+1,-1); depthv.assign(N+1,0); heavy.assign(N+1,-1);
  111.     head.assign(N+1,0); pos.assign(N+1,0); szv.assign(N+1,0); invpos.assign(N+1,0);
  112.     curPos = 1;
  113.     dfs1(1,-1);
  114.     dfs2(1,1);
  115.     Node* root = nullptr;
  116.     for(int i=1;i<=N;i++){
  117.         Node* nd = new Node(weightv[ invpos[i] ]);
  118.         root = merge(root, nd);
  119.     }
  120.  
  121.     while(Q--){
  122.         int type,u,v; cin>>type>>u>>v;
  123.         if(type==1){
  124.             auto segs = getPathSegments(u,v);
  125.             ll ans = INFLL;
  126.             for(auto &s: segs) ans = min(ans, treap_range_min(root, s.l, s.r));
  127.             cout<<ans<<"\n";
  128.         } else if(type==2){
  129.             auto segs = getPathSegments(u,v);
  130.             ll ans = -INFLL;
  131.             for(auto &s: segs) ans = max(ans, treap_range_max(root, s.l, s.r));
  132.             cout<<ans<<"\n";
  133.         } else {
  134.             auto segs_path = getPathSegments(u,v);
  135.             vector<Seg> segs_sorted = segs_path;
  136.             sort(segs_sorted.begin(), segs_sorted.end(), [](const Seg&a,const Seg&b){ return a.l < b.l; });
  137.             int m = segs_sorted.size();
  138.             vector<Node*> nonPath; nonPath.reserve(m+1);
  139.             vector<Node*> segsT; segsT.reserve(m);
  140.             Node* cur = root;
  141.             int prevR = 0; // <-- important: use prevR to index into current 'cur'
  142.             for(int i=0;i<m;i++){
  143.                 int l = segs_sorted[i].l;
  144.                 int r = segs_sorted[i].r;
  145.                 int len = r - l + 1;
  146.                 int kidx = l - prevR - 1; // CORRECT calculation
  147.                 Node *left, *rest;
  148.                 split(cur, kidx, left, rest);
  149.                 Node *mid, *right;
  150.                 split(rest, len, mid, right);
  151.                 nonPath.push_back(left);
  152.                 segsT.push_back(mid);
  153.                 cur = right;
  154.                 prevR = r;
  155.             }
  156.             nonPath.push_back(cur);
  157.             unordered_map<int,int> idx; idx.reserve(m*2+3);
  158.             for(int i=0;i<m;i++) idx[segs_sorted[i].l] = i;
  159.             Node* pathSeq = nullptr;
  160.             for(auto &s: segs_path){
  161.                 int id = idx[s.l];
  162.                 Node* t = segsT[id];
  163.                 if(s.rev) { if(t) t->rev ^= 1; }
  164.                 pathSeq = merge(pathSeq, t);
  165.             }
  166.             if(pathSeq) pathSeq->rev ^= 1;
  167.             Node* temp = pathSeq;
  168.             vector<Node*> newMidByL(m, nullptr);
  169.             for(int i=0;i<(int)segs_path.size();i++){
  170.                 auto &s = segs_path[i];
  171.                 int len = s.r - s.l + 1;
  172.                 Node *left, *right;
  173.                 split(temp, len, left, right);
  174.                 if(s.rev){ if(left) left->rev ^= 1; }
  175.                 int id = idx[s.l];
  176.                 newMidByL[id] = left;
  177.                 temp = right;
  178.             }
  179.             Node* res = nullptr;
  180.             for(int i=0;i<m;i++){
  181.                 res = merge(res, nonPath[i]);
  182.                 res = merge(res, newMidByL[i]);
  183.             }
  184.             res = merge(res, nonPath[m]);
  185.             root = res;
  186.         }
  187.     }
  188.     return 0;
  189. }
  190.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
8 4
2 4 1 4 7 5 2 3
1 2
1 3
2 4
2 5
3 6
3 7
3 8
2 6 4
1 4 1
3 7 2
1 6 8
stdout 
5
2
2
https://ideone.com/3L7neG
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!