fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(ac) ac.begin(),ac.end()
  4. #define task "tet"
  5. const int N=2e5+1;
  6. struct node {
  7.     int mval, len;
  8.     node() {
  9.         mval=0;
  10.         len=0;
  11.     }
  12.     node(int x, int y): mval(x), len(y) {}
  13.     bool operator ==(const node o) const {return o.mval==mval && o.len==len;}
  14. };
  15. vector <int> g[N];
  16. int pos[N], a[N], A[N], head[N], par[N], rmq[N][19], n,q, high[N], sz[N], cur_pos, up[N], down[N];
  17. node pf[N];
  18. node it;
  19. void dfs(int u) {
  20.     sz[u]=1;
  21.     for(auto v:g[u]) if(v!=par[u]) {
  22.         par[v]=u, high[v]=high[u]+1;
  23.         dfs(v), sz[u]+=sz[v];
  24.     }
  25.     return;
  26. }
  27. void hld(int u, int h) {
  28.     head[u]=h, pos[u]=++cur_pos, A[cur_pos]=u;
  29.     int x=0;
  30.     if(pf[h].mval==0) pf[h].mval=u;
  31.     pf[h].len=u;
  32.     for(auto v:g[u]) if(v!=par[u] && sz[v]>sz[x]) x=v;
  33.     if(x) hld(x,h);
  34.     for(auto v:g[u]) if(v!=par[u] && v!=x) hld(v,v);
  35.     return;
  36. }
  37. int lca(int u, int v) {
  38.     while(head[u]!=head[v]) {
  39.         if(high[head[u]]>high[head[v]]) u=par[head[u]];
  40.         else v=par[head[v]];
  41.     }
  42.     return high[u]>high[v]?v:u;
  43. }
  44. void pre_calc(int &u, int &v, int f[]) {
  45.     stack <int> stk;
  46.     for(int i=u;i<=v;i++) {
  47.         while(stk.size() && a[A[stk.top()]]<=a[A[i]]) stk.pop();
  48.         if(stk.empty()) f[i]=1;
  49.         else f[i]=f[stk.top()]+1;
  50.         stk.emplace(i);
  51.     }
  52.     return;
  53. }
  54. int get_max(int &l, int &r) {
  55.     int k=31-__builtin_clz(r-l+1);
  56.     return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
  57. }
  58. int get_pos_low(int lo ,int hi, int w) {
  59.     int posi=-1;
  60.     int in=hi;
  61.     while(lo<=hi) {
  62.         int mid=(lo+hi)>>1;
  63.         if(get_max(mid,in)>w) lo=mid+1, posi=mid;
  64.         else hi=mid-1;
  65.     }
  66.     return posi;
  67. }
  68. int get_pos_up(int lo, int hi, int w) {
  69.     int posi=-1;
  70.     int in=lo;
  71.     while(lo<=hi) {
  72.         int mid=(lo+hi)>>1;
  73.         if(get_max(in,mid)>w) hi=mid-1, posi=mid;
  74.         else lo=mid+1;
  75.     }
  76.     return posi;
  77. }
  78. node calc(int u, int v, int w, int type) {
  79.     if(type>0) {
  80.         int pid=get_pos_low(u,v,w);
  81.         if(pid==-1) return it;
  82.         if(type==2) return {get_max(u,v),down[pid]};
  83.         int pid_=get_pos_low(u,v,get_max(u,v)-1);
  84.         return {a[A[pid_]],down[pid]-down[pid_]+1};
  85.     }
  86.     int pid=get_pos_up(u,v,w);
  87.     if(pid==-1) return it;
  88.     int pid_=get_pos_up(u,v,get_max(u,v)-1);
  89.     return {a[A[pid_]],up[pid]-up[pid_]+1};
  90. }
  91. int solve(int u, int v) {
  92.     int ans=0,cur_val=0;
  93.     int lc=lca(u,v);
  94.     int ok=1;
  95.     while(head[u]!=head[lc]) {
  96.         auto e=calc(pos[head[u]],pos[u],cur_val,ok);
  97.         if(e.len) ans+=e.len, cur_val=max(cur_val,e.mval);
  98.         u=par[head[u]], ok=2;
  99.     }
  100.     auto e=calc(pos[lc],pos[u],cur_val,1);
  101.     if(e.len) ans+=e.len, cur_val=max(cur_val,e.mval);
  102.     stack <node> stk;
  103.     while(head[v]!=head[lc]) {
  104.         stk.emplace(node{head[v],v});
  105.         v=par[head[v]];
  106.     }
  107.     if(v!=lc) {
  108.         e=calc(pos[lc]+1,pos[v],cur_val,0);
  109.         if(e.len) ans+=e.len, cur_val=max(cur_val,e.mval);
  110.     }
  111.     while(stk.size()) {
  112.         node d=stk.top(); stk.pop();
  113.         e=calc(pos[d.mval],pos[d.len],cur_val,0);
  114.         if(e.len) ans+=e.len, cur_val=max(cur_val,e.mval);
  115.     }
  116.     return ans;
  117. }
  118. int32_t main() {
  119.     ios::sync_with_stdio(false);
  120.     cin.tie(0), cout.tie(0);
  121.     cin >> n >> q;
  122.     for(int i=1;i<=n;i++) cin >> a[i];
  123.     for(int i=1;i<n;i++) {
  124.         int u,v; cin >> u >> v;
  125.         g[u].emplace_back(v);
  126.         g[v].emplace_back(u);
  127.     }
  128.     dfs(1), hld(1,1);
  129.     int pre_ans=0;
  130.     for(int i=1;i<=n;i++) rmq[i][0]=a[A[i]];
  131.     for(int j=1;j<19;j++) {
  132.         for(int i=1;i+(1<<j)-1<=n;i++) rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
  133.     }
  134.     for(int i=1;i<=n;i++) {
  135.         if(pf[i]==it) continue;
  136.         int p1=pos[pf[i].mval], p2=pos[pf[i].len];
  137.         pre_calc(p1,p2,down);
  138.         stack <int> stk;
  139.         for(int j=p2;j>=p1;j--) {
  140.             while(stk.size() && a[A[stk.top()]]<=a[A[j]]) stk.pop();
  141.             if(stk.empty()) up[j]=1;
  142.             else up[j]=up[stk.top()]+1;
  143.             stk.emplace(j);
  144.         }
  145.     }
  146.     while(q--) {
  147.         int x,y; cin >> x >> y;
  148.         x+=pre_ans, y+=pre_ans;
  149.         while(x>=n) x-=n;
  150.         while(y>=n) y-=n;
  151.         cout << (pre_ans=solve(x+1,y+1)) << '\n';
  152.     }
  153.     return 0;
  154. }
  155.  
Success #stdin #stdout 0.01s 15300KB
comments (?)
stdin 
6 3
2 4 2 1 3 1
1 3
2 3
3 4
5 3
6 5
5 1
0 3
5 1
stdout 
3
2
1
https://ideone.com/iGDs0R
language:
C++ (gcc 8.3)
created:
17 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!