fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INFLL = (1LL<<62);
  5. struct Treap {
  6.     ll val, mn, mx;
  7.     int pr, sz;
  8.     bool rev;
  9.     Treap *l, *r;
  10.     Treap(ll v): val(v), mn(v), mx(v), pr(rand()), sz(1), rev(false), l(nullptr), r(nullptr) {}
  11. };
  12. int tsz(Treap* t){ return t? t->sz:0; }
  13. void pull(Treap* t){
  14.     if(!t) return;
  15.     t->sz = 1 + tsz(t->l) + tsz(t->r);
  16.     t->mn = t->val;
  17.     t->mx = t->val;
  18.     if(t->l){ t->mn = min(t->mn, t->l->mn); t->mx = max(t->mx, t->l->mx); }
  19.     if(t->r){ t->mn = min(t->mn, t->r->mn); t->mx = max(t->mx, t->r->mx); }
  20. }
  21. void apply_rev(Treap* t){
  22.     if(!t) return;
  23.     t->rev ^= 1;
  24. }
  25. void push(Treap* t){
  26.     if(!t || !t->rev) return;
  27.     t->rev = false;
  28.     swap(t->l, t->r);
  29.     if(t->l) t->l->rev ^= 1;
  30.     if(t->r) t->r->rev ^= 1;
  31. }
  32. Treap* mergeTreap(Treap* a, Treap* b){
  33.     if(!a) return b;
  34.     if(!b) return a;
  35.     if(a->pr < b->pr){
  36.         push(a);
  37.         a->r = mergeTreap(a->r, b);
  38.         pull(a);
  39.         return a;
  40.     } else {
  41.         push(b);
  42.         b->l = mergeTreap(a, b->l);
  43.         pull(b);
  44.         return b;
  45.     }
  46. }
  47. void splitTreap(Treap* t, int k, Treap*& a, Treap*& b){
  48.     if(!t){ a=b=nullptr; return; }
  49.     push(t);
  50.     if(tsz(t->l) >= k){
  51.         splitTreap(t->l, k, a, t->l);
  52.         pull(t);
  53.         b = t;
  54.     } else {
  55.         splitTreap(t->r, k - tsz(t->l) - 1, t->r, b);
  56.         pull(t);
  57.         a = t;
  58.     }
  59. }
  60. int N,Q;
  61. vector<vector<int>> adj;
  62. vector<int> parentv, depthv, heavy, head, pos, szv, invpos;
  63. int curPos=1;
  64. vector<ll> weightv;
  65. int dfs1(int v,int p){
  66.     parentv[v]=p;
  67.     depthv[v]= (p==-1?0:depthv[p]+1);
  68.     int size=1;
  69.     int maxc=0;
  70.     heavy[v]=-1;
  71.     for(int to: adj[v]){
  72.         if(to==p) continue;
  73.         int s = dfs1(to, v);
  74.         if(s>maxc){ maxc=s; heavy[v]=to; }
  75.         maxc = max(maxc, s);
  76.         size += s;
  77.     }
  78.     szv[v]=size;
  79.     return size;
  80. }
  81. void dfs2(int v,int h){
  82.     head[v]=h;
  83.     pos[v]=curPos;
  84.     invpos[curPos]=v;
  85.     curPos++;
  86.     if(heavy[v]!=-1) dfs2(heavy[v], h);
  87.     for(int to: adj[v]){
  88.         if(to==parentv[v] || to==heavy[v]) continue;
  89.         dfs2(to, to);
  90.     }
  91. }
  92. struct Seg { int l,r; bool rev; };
  93. vector<Seg> getPathSegments(int u,int v){
  94.     vector<Seg> up, down;
  95.     while(head[u] != head[v]){
  96.         if(depthv[head[u]] >= depthv[head[v]]){
  97.             up.push_back({pos[head[u]], pos[u], true});
  98.             u = parentv[head[u]];
  99.         } else {
  100.             down.push_back({pos[head[v]], pos[v], false});
  101.             v = parentv[head[v]];
  102.         }
  103.     }
  104.     if(pos[u] <= pos[v]) up.push_back({pos[u], pos[v], false});
  105.     else up.push_back({pos[v], pos[u], true});
  106.     for(int i=(int)down.size()-1;i>=0;--i) up.push_back(down[i]);
  107.     return up;
  108. }
  109. Treap* root = nullptr;
  110. ll range_min(int l,int r){
  111.     Treap *a,*b,*c;
  112.     splitTreap(root, r, a, b);
  113.     splitTreap(a, l-1, c, a);
  114.     ll ans = (a? a->mn : INFLL);
  115.     a = mergeTreap(c, a);
  116.     root = mergeTreap(a, b);
  117.     return ans;
  118. }
  119. ll range_max(int l,int r){
  120.     Treap *a,*b,*c;
  121.     splitTreap(root, r, a, b);
  122.     splitTreap(a, l-1, c, a);
  123.     ll ans = (a? a->mx : -INFLL);
  124.     a = mergeTreap(c, a);
  125.     root = mergeTreap(a, b);
  126.     return ans;
  127. }
  128. int main(){
  129.     ios::sync_with_stdio(false);
  130.     cin.tie(nullptr);
  131.     cin>>N>>Q;
  132.     weightv.assign(N+1,0);
  133.     for(int i=1;i<=N;i++) cin>>weightv[i];
  134.     adj.assign(N+1, {});
  135.     for(int i=0;i<N-1;i++){
  136.         int u,v; cin>>u>>v;
  137.         adj[u].push_back(v);
  138.         adj[v].push_back(u);
  139.     }
  140.     parentv.assign(N+1,-1);
  141.     depthv.assign(N+1,0);
  142.     heavy.assign(N+1,-1);
  143.     head.assign(N+1,0);
  144.     pos.assign(N+1,0);
  145.     szv.assign(N+1,0);
  146.     invpos.assign(N+2,0);
  147.     dfs1(1,-1);
  148.     dfs2(1,1);
  149.     root = nullptr;
  150.     for(int i=1;i<=N;i++){
  151.         Treap* node = new Treap(weightv[ invpos[i] ]);
  152.         root = mergeTreap(root, node);
  153.     }
  154.     while(Q--){
  155.         int type,u,v;
  156.         cin>>type>>u>>v;
  157.         if(type==1){
  158.             auto segs = getPathSegments(u,v);
  159.             ll ans = INFLL;
  160.             for(auto &s: segs){
  161.                 ans = min(ans, range_min(s.l, s.r));
  162.             }
  163.             cout<<ans<<"\n";
  164.         } else if(type==2){
  165.             auto segs = getPathSegments(u,v);
  166.             ll ans = -INFLL;
  167.             for(auto &s: segs){
  168.                 ans = max(ans, range_max(s.l, s.r));
  169.             }
  170.             cout<<ans<<"\n";
  171.         } else if(type==3){
  172.             auto pathSegs = getPathSegments(u,v);
  173.             int k = pathSegs.size();
  174.             vector<pair<int,int>> ranges;
  175.             ranges.reserve(k);
  176.             for(auto &s: pathSegs) ranges.push_back({s.l, s.r});
  177.             vector<pair<int,int>> uniq = ranges;
  178.             sort(uniq.begin(), uniq.end());
  179.             uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
  180.             int m = uniq.size();
  181.             vector<Treap*> nonPath;
  182.             vector<Treap*> segsT;
  183.             Treap* cur = root;
  184.             int removed = 0;
  185.             for(int i=0;i<m;i++){
  186.                 int l = uniq[i].first;
  187.                 int r = uniq[i].second;
  188.                 int len = r - l + 1;
  189.                 int kidx = l - 1 - removed;
  190.                 Treap *left, *rest;
  191.                 splitTreap(cur, kidx, left, rest);
  192.                 Treap *mid, *right;
  193.                 splitTreap(rest, len, mid, right);
  194.                 nonPath.push_back(left);
  195.                 segsT.push_back(mid);
  196.                 cur = right;
  197.                 removed += len;
  198.             }
  199.             nonPath.push_back(cur);
  200.             unordered_map<int,int> idxmap;
  201.             for(int i=0;i<m;i++) idxmap[ uniq[i].first ] = i;
  202.             vector<Treap*> seqT;
  203.             seqT.reserve(k);
  204.             for(auto &ps: pathSegs){
  205.                 int id = idxmap[ps.l];
  206.                 Treap* tnode = segsT[id];
  207.                 if(ps.rev) apply_rev(tnode);
  208.                 seqT.push_back(tnode);
  209.             }
  210.             vector<Treap*> newSeq;
  211.             newSeq.resize(k);
  212.             for(int i=0;i<k;i++){
  213.                 Treap* tmp = seqT[k-1 - i];
  214.                 apply_rev(tmp);
  215.                 newSeq[i] = tmp;
  216.             }
  217.             for(int i=0;i<k;i++){
  218.                 auto &ps = pathSegs[i];
  219.                 int id = idxmap[ps.l];
  220.                 Treap* tnode = newSeq[i];
  221.                 if(ps.rev) apply_rev(tnode);
  222.                 segsT[id] = tnode;
  223.             }
  224.             Treap* res = nullptr;
  225.             for(int i=0;i<m;i++){
  226.                 res = mergeTreap(res, nonPath[i]);
  227.                 res = mergeTreap(res, segsT[i]);
  228.             }
  229.             res = mergeTreap(res, nonPath[m]);
  230.             root = res;
  231.         }
  232.     }
  233.     return 0;
  234. }
  235.  
Success #stdin #stdout 0.01s 5320KB
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/YecX6z
language:
C++14 (gcc 8.3)
created:
12 hours 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!