API tools faq
paste
willy108

NEW TEMPLATE OTZ

willy108
Feb 18th, 2021 (edited)
435
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 28.76 KB | None | 0 0
raw download clone embed print report
  1. //this is not my code. source below
  2. //https://cses.fi/problemset/hack/1737/entry/1714867/
  3. //if you wrote this, you are orz
  4.  
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <algorithm>
  8. #include <queue>
  9. #include <stack>
  10. #include <string>
  11. #include <vector>
  12. #include <cmath>
  13. #include <map>
  14. #include <set>
  15. #include <string.h>
  16. #include <stdlib.h>
  17. #include <assert.h>
  18. #include<ext/pb_ds/assoc_container.hpp>
  19. #include<ext/pb_ds/tree_policy.hpp>
  20.  
  21. using namespace std;
  22. using namespace __gnu_pbds;
  23. template <typename T>
  24. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  25. // vector push_back push front top empty pop make_pair long long insert begin end  
  26. #define int long long
  27. typedef long long ll;
  28. typedef vector<int> vi;
  29. typedef vector<pair <int,int> > vpi;
  30. typedef vector<long long> vll;
  31. typedef pair<int,int> pi;
  32. typedef pair<ll,ll> pll;
  33. void display(vi &a){for(int z : a)cout << z << " ";cout << endl;}
  34. #define trace(x) cerr<<__FUNCTION__<<":"<<__LINE__<<": "#x" = "<<x<<endl;
  35. #define F first
  36. #define ln '\n'
  37. #define S second
  38. #define PB push_back
  39. #define MP make_pair
  40. #define B begin()
  41. #define RB rbegin()
  42. #define E end()
  43. #define RE rend()
  44. #define Z size()
  45. #define REP(i,a,b) for (int i = a; i < b; i++)
  46. #define L length()
  47. #define show(a) cerr << " *** " << a << endl;
  48. #define show1(a) cerr << " /// " << a << endl;
  49. #define valid(a,b,c) (a >= b && a < c ? 1 : 0)
  50. int dx[4] = {0,0,1,-1};
  51. int dy[4] = {1,-1,0,0};
  52. const int mod = (int)1e9 + 7;
  53. const ll INF64 = 3e18;
  54. void smxl(ll &a, ll b){if (a < b)a=b;}
  55. void smnl(ll &a, ll b){if (a > b)a=b;}
  56. void adsl(ll &a, ll b){a += b;if (a >= mod)a -= mod;}
  57. void misl(ll &a, ll b){a -= b;if (a >= mod)a -= mod; if (a < 0)a += mod;}
  58. void smx(ll &a, ll b){if (a < b)a=b;}
  59. void smn(ll &a, ll b){if (a > b)a=b;}
  60. void ads(ll &a, ll b){a += b;if (a >= mod)a -= mod;}
  61. void mis(ll &a, ll b){a -= b;if (a >= mod)a -= mod; if (a < 0)a += mod;}
  62. ll gcd(ll a, ll b) {return (b==0? a:gcd(b,a%b));}
  63. ll egcd(ll a, ll b, ll & x, ll & y) {if (a == 0){x = 0;y = 1;return b;}ll x1, y1;ll d = egcd(b % a, a, x1, y1);x = y1 - (b / a) * x1;y = x1;return d;}
  64. ll mbinp(ll a, ll b){a %= mod;if (b == 0)return 1;ll ans = mbinp(a, b/2);ll tmp = (ans * ans) % mod;if (b % 2)return ((tmp * a) % mod);return ((tmp) % mod);}
  65. ll binp(ll a, ll b){if (b == 0)return 1;ll ans = binp(a, b/2);ll tmp = (ans * ans);if (b % 2)return ((tmp * a));return ((tmp));}
  66. long long C(int n, int m){ll ret=1;for(int i=1;i<=m;i++){ret*=(n-i+1);ret/=i;}return ret;}
  67. long long overbinp(long long a, int b){long long res = 1;while (b){if (b & 1){if (res < INF64 / a) res *= a;else return INF64;}if (b > 1){if (a < INF64 / a) a *= a;else return INF64;}b >>= 1;}return res;}
  68. //DSU
  69. class DSU{
  70.   vi par;
  71.   vi siize;
  72.   public:
  73.     DSU(int n)
  74.     {
  75.       par.resize(n);
  76.       siize.resize(n);
  77.       REP(i,0,n)
  78.       {
  79.         par[i]=i;
  80.         siize[i]=1;
  81.       }
  82.     }
  83.   public:
  84.     int get(int x)
  85.     {
  86.       return (x == par[x] ? x : par[x] = get(par[x]));
  87.     }
  88.   public:
  89.     void merge(int a, int b)
  90.     {
  91.       int x = get(a);
  92.       int y = get(b);
  93.       if (x == y)return;
  94.       if (siize[x] < siize[y])swap(x,y);par[y] = x;siize[x] += siize[y];
  95.     }
  96. };
  97. class BinaryLift{
  98.     vector<vi> binlift;
  99.     int n;
  100.     public:
  101.         BinaryLift(vi rnk, vi par){
  102.             n = (int)par.Z;
  103.             binlift.resize(n);
  104.             REP(i,0,n)
  105.                 binlift[i].resize(20);
  106.             REP(i,0,n)
  107.                 binlift[i][0] = par[i];
  108.             REP(j,1,20)
  109.                 REP(i,0,n)
  110.                 {
  111.                     if ((1 <<j) <rnk[i])
  112.                         binlift[i][j]=binlift[binlift[i][j-1]][j-1];
  113.                     else
  114.                         binlift[i][j]=-1;
  115.                 }
  116.         }
  117.     public:
  118.         int get_kth_ancestor(int x, int k)
  119.         {
  120.             int pt = x;
  121.             for (int i = 19; i >= 0; i--)
  122.             {
  123.                 if (pt==-1)
  124.                     exit(0);
  125.                 if (k&(1<<i))
  126.                     pt=binlift[pt][i];
  127.             }
  128.             return pt;
  129.         }
  130.     public:
  131.         int get_th_ancestor(int x, int k)
  132.         {
  133.             int pt = x;
  134.             for (int i = 19; i >= 0; i--)
  135.             {
  136.                 if (k&(1<<i))
  137.                     pt=binlift[pt][i];
  138.             }
  139.             return pt;
  140.         }
  141. };
  142. class SparseTable2D{
  143.   vector<vector< vector<vi > > > sparse;
  144.   vector<vi> inp;
  145.   int m,n;
  146.   private: int lg2(int x){
  147.         int out = 0;
  148.         while((1 << out) <= x)
  149.             out++;
  150.         return out-1;
  151.     }
  152.   public:
  153.     int rmin(int x1, int y1, int x2, int y2)
  154.     {
  155.       int lenx = x2-x1+1;
  156.       int lx = lg2(lenx)+1;
  157.       int leny = y2-y1+1;
  158.       int ly = lg2(leny)+1;
  159.       return min(min(sparse[lx][x1][ly][y1],sparse[lx][x1][ly][y2+1-(1<<ly)]),min(sparse[lx][x2+1-(1<<lx)][ly][y1],sparse[lx][x2+1-(1<<lx)][ly][y2+1-(1<<ly)]));
  160.     }
  161.   public:
  162.     SparseTable2D(vector<vi> input, string param){
  163.       n = input.Z;
  164.       m = input[0].Z;
  165.       inp = input;
  166.       if (param == "min")
  167.         prepromin();
  168.       /*else if (param = "max")
  169.         prepromax();
  170.       else if (param = "sum")
  171.         preprosum();*/
  172.   }
  173.   private:
  174.     void prepromin()
  175.     {
  176.       int lln,lm;
  177.       lln=lg2(n)+1;
  178.       lm=lg2(m)+1;
  179.       sparse.resize(lln);
  180.       REP(i,0,lln)
  181.         sparse[i].resize(n);
  182.       REP(i,0,lln)
  183.         REP(j,0,n)
  184.           sparse[i][j].resize(lm);
  185.       REP(i,0,lln)
  186.         REP(j,0,n)
  187.           REP(k,0,lm)
  188.             sparse[i][j][k].resize(m);
  189.       REP(i,0,n)
  190.       {
  191.         REP(j,0,m)
  192.           sparse[0][i][0][j]=inp[i][j];
  193.         REP(j,1,lm)
  194.           for(int k = 0; k + (1<<j)-1 < m;k++)
  195.             sparse[0][i][j][k]=min(sparse[0][i][j-1][k],sparse[0][i][j-1][k+(1<<(j-1))]);
  196.       }
  197.       REP(i,1,lln)
  198.         for (int j = 0; j +(1<<i)-1<n;j++)
  199.           REP(k,0,lm)
  200.             REP(h,0,m)
  201.               sparse[i][j][k][h]=min(sparse[i-1][j][k][h],sparse[i-1][j+(1<<(i-1))][k][h]);
  202.     }
  203. };
  204. class SparseTable{
  205.     vector<vll> sparse;
  206.     int n;
  207.     vi input;
  208.     private: int lg2(int x){
  209.         int out = 0;
  210.         while((1 << out) <= x)
  211.             out++;
  212.         return out-1;
  213.     }
  214.     public: int rmaxpos(int left, int right){
  215.         int len = right-left+1;
  216.         int lg = lg2(len);
  217.         return (input[sparse[left][lg]] > input[sparse[left+len-(1 << lg) ][lg]]? sparse[left][lg]:sparse[left+len-(1 << lg)][lg]);
  218.     }
  219.     public: int rmaxval(int left, int right){
  220.         int len = right-left+1;
  221.         int lg = lg2(len);
  222.         return (input[sparse[left][lg]] > input[sparse[left+len-(1 << lg) ][lg]]? input[sparse[left][lg]]:input[sparse[left+len-(1 << lg)][lg]]);
  223.     }
  224.     public: int rminpos(int left, int right){
  225.         int len = right-left+1;
  226.         int lg = lg2(len);
  227.         return (input[sparse[left][lg]] < input[sparse[left+len-(1 << lg) ][lg]]? sparse[left][lg]:sparse[left+len-(1 << lg)][lg]);
  228.     }
  229.     public: int rminval(int left, int right){
  230.         int len = right-left+1;
  231.         int lg = lg2(len);
  232.         return (input[sparse[left][lg]] < input[sparse[left+len-(1 << lg) ][lg]]? input[sparse[left][lg]]:input[sparse[left+len-(1 << lg)][lg]]);
  233.     }
  234.     public: ll rsum(int left, int right){
  235.         ll ans = 0;
  236.         int pos;
  237.         while (left <= right)
  238.         {
  239.             for(int i = 19; i>=0; i--)
  240.                 if ((1 << i) <= right-left+1)
  241.                 {
  242.                     pos = i;
  243.                     break;
  244.                 }
  245.         ans += sparse[left][pos];
  246.         left = left + (1<<pos);
  247.         }
  248.         return ans;
  249.     }
  250.     public: SparseTable(vi inp, string operation){
  251.         input= inp;
  252.         n=inp.Z;
  253.         if (operation == "min")
  254.             prepromin();  
  255.         else if (operation == "max")
  256.             prepromax();
  257.         else if (operation == "sum")
  258.             preprosum();
  259.     }
  260.     private: void prepromin(){
  261.         sparse.resize(n);
  262.         int x = lg2(n)+1;
  263.         REP(i,0,n)
  264.             sparse[i].resize(x);
  265.         REP(i,0,n)
  266.             sparse[i][0]=i;
  267.         REP(j,1,x)
  268.             for(int i = 0; i + (1 << (j))-1 < n; i++)
  269.                 sparse[i][j] = (input[sparse[i][j-1]] < input[sparse[i+(1<<(j-1))][j-1]] ? sparse[i][j-1] : sparse[i+(1<<(j-1))][j-1]); //min
  270.     }
  271.     void prepromax(){
  272.         sparse.resize(n);
  273.         int x = lg2(n)+1;
  274.         REP(i,0,n)
  275.             sparse[i].resize(x);
  276.         REP(i,0,n)
  277.             sparse[i][0]=i;
  278.         REP(j,1,x)
  279.             for(int i = 0; i + (1 << (j))-1 < n; i++)
  280.                 sparse[i][j] = (input[sparse[i][j-1]] > input[sparse[i+(1<<(j-1))][j-1]] ? sparse[i][j-1] : sparse[i+(1<<(j-1))][j-1]); //min
  281.     }
  282.     void preprosum(){
  283.         sparse.resize(n);
  284.         int x = lg2(n)+1;
  285.         REP(i,0,n)
  286.             sparse[i].resize(x);
  287.         REP(i,0,n)
  288.             sparse[i][0]=input[i];
  289.         REP(j,1,x)
  290.             for(int i = 0; i + (1 << (j))-1 < n; i++)
  291.                 sparse[i][j] = sparse[i][j-1]+sparse[i+(1<<(j-1))][j-1];
  292.     }
  293. };
  294. class PruferCode{
  295.   vi code;
  296.   vpi edges;
  297.   public:
  298.     PruferCode(vi cc){
  299.       code =cc;
  300.       findEdges();
  301.     }
  302.   private:
  303.     void findEdges(){
  304.       map<int,int> mp;
  305.       set<int> has;
  306.       set<int> wait;
  307.       for (int z: code){
  308.         mp[z]++;
  309.         has.insert(z);
  310.       }
  311.       REP(i,0,code.Z+2)
  312.         if (!has.count(i))
  313.           wait.insert(i);
  314.       REP(i,0,code.Z)
  315.       {
  316.         int now = *wait.B;
  317.         edges.PB(MP(now,code[i]));
  318.         mp[now]++;
  319.         mp[code[i]]--;
  320.         if (mp[code[i]]==0)
  321.         {
  322.           has.erase(code[i]);
  323.           wait.insert(code[i]);
  324.         }
  325.         wait.erase(now);
  326.       }
  327.       assert(wait.Z ==2);
  328.       edges.PB(MP(*wait.B,*wait.RB));
  329.     }
  330.   public:
  331.     vpi getEdges()
  332.     {
  333.       return edges;
  334.     }
  335. };
  336. class SegmentTree{
  337.   int len;
  338.   vll all;
  339.   vll seg;
  340.   public:
  341.     SegmentTree(){}
  342.     SegmentTree(vll inp)
  343.     {
  344.       len = inp.Z;
  345.       all = inp;
  346.       seg.resize(4*len);
  347.       build(1,0,len-1);
  348.     }
  349.   void build(int id, int l, int r)
  350.   {
  351.     if (l==r)
  352.     {
  353.       seg[id] = all[l];
  354.       return ;
  355.     }
  356.     int mid=(l+r)/2;
  357.     build(2*id,l,mid);
  358.     build(2*id+1,mid+1,r);
  359.     seg[id] = min(seg[2*id],seg[2*id+1]);
  360.   }
  361.   ll query(int id, int l, int r, int sl, int sr)
  362.   {
  363.     if (r < sl || sr < l)
  364.       return 1e18;
  365.     if (sl <= l && sr >= r)
  366.       return seg[id];
  367.     int mid = (l+r)/2;
  368.     return min(query(2*id,l,mid,sl,sr),query(2*id+1,mid+1,r,sl,sr));
  369.   }
  370.   ll query(int l,int r)
  371.   {
  372.       return query(1,0,len-1,l,r);
  373.   }
  374. };
  375. class HopcroftKarp{
  376.   vi matched;
  377.   vector<vpi> adj;
  378.   int left;
  379.   int right;
  380.   public:
  381.   HopcroftKarp(vector<vpi> inp,int l, int r)
  382.   {
  383.     adj = inp;
  384.     left = l;
  385.     matched.resize(l);
  386.     REP(i,0,l)
  387.       matched[i] = -1;
  388.     right = r;
  389.   }
  390.   public:
  391.   vi match()
  392.   {
  393.     bool cont = true;
  394.     set<int> lfree,rfree;
  395.     REP(i,0,left)
  396.       lfree.insert(i);
  397.     REP(i,left,left+right)
  398.       rfree.insert(i);
  399.     vector<bool> yet(left,0);
  400.     REP(i,0,left)
  401.       REP(j,0,adj[i].Z)
  402.       if (adj[i][j].S==1 && rfree.count(adj[i][j].F)&& !yet[i])
  403.       {
  404.         yet[i]=true;
  405.         matched[i] = adj[i][j].F;
  406.         adj[i][j].S = 2;
  407.         REP(x,0,adj[adj[i][j].F].Z)
  408.           if (adj[adj[i][j].F][x].F == i)
  409.             adj[adj[i][j].F][x].S = 2;
  410.         rfree.erase(adj[i][j].F);
  411.         lfree.erase(i);
  412.       }
  413.     while(cont)
  414.     {
  415.       vi par(left+right,-1);
  416.       queue<pi> kyou;
  417.       for (int z : lfree)
  418.         kyou.push(MP(z,0));
  419.       int update = -1;
  420.       vi vis(left+right,0);
  421.       while(kyou.Z)
  422.       {
  423.         pi frt = kyou.front();
  424.         kyou.pop();
  425.         if (rfree.count(frt.F))
  426.         {
  427.           update = frt.F;
  428.           break;
  429.         }
  430.         if (frt.S == 0)
  431.         {
  432.           for (pi z : adj[frt.F])
  433.           {
  434.             if (z.S == 1 && !vis[z.F])
  435.             {
  436.               par[z.F]=frt.F;
  437.               vis[z.F] = 1;
  438.               kyou.push(MP(z.F,1));
  439.             }
  440.           }
  441.         }
  442.         else
  443.         {
  444.           for (pi z : adj[frt.F])
  445.           {
  446.             if (z.S == 2 && !vis[z.F])
  447.             {
  448.               par[z.F]=frt.F;
  449.               vis[z.F] = 1;
  450.               kyou.push(MP(z.F,0));
  451.             }
  452.           }
  453.         }
  454.       }  
  455.       int x = update;
  456.       int cnt = 0;
  457.       while (x != -1 && par[x] != -1)
  458.       {
  459.         REP(i,0,adj[x].Z)
  460.           if (adj[x][i].F == par[x])
  461.           {
  462.             adj[x][i].S = (cnt==0?2:1);
  463.             if (cnt==0)
  464.             {
  465.               matched[par[x]]=x;
  466.               rfree.erase(x);
  467.               lfree.erase(par[x]);
  468.             }
  469.           }
  470.         REP(i,0,adj[par[x]].Z)
  471.           if (adj[par[x]][i].F == x)
  472.             adj[par[x]][i].S = (cnt==0?2:1);
  473.         cnt++;
  474.         cnt%=2;
  475.         x=par[x];
  476.       }
  477.       if (update == -1)
  478.         cont = false;
  479.     }
  480.     return matched;
  481.   }
  482. };
  483.  
  484. class SuffixArray{
  485.   vi order;
  486.   vi lcp;
  487.   string str;
  488.   SegmentTree seg;
  489.   public:
  490.   SuffixArray(string in)
  491.   {
  492.     str = in;
  493.     str += '$';
  494.     order.resize(str.L);
  495.     lcp.resize(str.L);
  496.     compute();
  497.     seg = SegmentTree(order);
  498.   }
  499.   void compute()
  500.   {
  501.     vector<pair<char,int> > a;
  502.     vi equi(order.Z);
  503.     vi bij(order.Z);
  504.     REP(i,0,str.L)
  505.       a.PB(MP(str[i],i));
  506.     sort(a.B,a.E);
  507.     REP(i,0,str.L)
  508.       order[i] = a[i].S;
  509.     equi[order[0]]=0;
  510.     int r = 0;
  511.     REP(i,1,str.L)
  512.     {
  513.       if (a[i].F == a[i-1].F)
  514.         equi[order[i]] = r;
  515.       else
  516.         equi[order[i]] = ++r;
  517.     }
  518.     int k = 0;
  519.     while((1<<k) <str.L)
  520.     {
  521.       vector<pair<pi,int> > a(str.L);
  522.       REP(i,0,str.L)
  523.         a[i] = MP(MP(equi[i],equi[(i+(1<<k))%(str.L)]),i);
  524.       sort(a.B,a.E);
  525.       REP(i,0,str.L)
  526.       {
  527.         order[i] = a[i].S;
  528.         bij[order[i]]=i;
  529.       }
  530.       int r = 0;
  531.       equi[order[0]]=0;
  532.       REP(i,1,str.L)
  533.       {
  534.         if (a[i].F == a[i-1].F)
  535.           equi[order[i]]=r;
  536.         else
  537.           equi[order[i]]=++r;
  538.       }
  539.       k++;
  540.     }
  541.     k = 0;
  542.     REP(i,0,str.L-1)
  543.     {
  544.       int p = bij[i];
  545.       int j = order[p-1];
  546.       while(i+k < str.L && j+k <str.L  && str[i+k]==str[j+k])k++;
  547.       lcp[p] = k;
  548.       k = max(k-1,0LL);
  549.     }
  550.   }
  551.   public:
  552.   int count(string ptr)
  553.   {
  554.     int low = 0;
  555.     int hi = str.L-1;
  556.     int res1,res2;
  557.     res1 = 0;
  558.     res2 = 1e9;
  559.     while(low <= hi)
  560.     {
  561.       int mid=(low+hi)/2;
  562.       bool gr = false;
  563.       int i = 0;
  564.       for( i ; i< min((ll)ptr.L,(ll)str.L-order[mid]); i++)
  565.       {
  566.         if (ptr[i] != str[order[mid]+i])
  567.         {
  568.           if (ptr[i] > str[order[mid]+i])
  569.             gr = true;
  570.           break;
  571.         }
  572.       }
  573.       if (i == ptr.L)
  574.       {
  575.         res2=min(res2,mid);
  576.         hi=mid-1;
  577.       }
  578.       else if (!gr)
  579.         hi=mid-1;
  580.       else
  581.         low = mid+1;
  582.     }
  583.     low = 0;
  584.     hi=str.L-1;
  585.     while(low <= hi)
  586.     {
  587.       int mid=(low+hi)/2;
  588.       bool gr = false;
  589.       int i = 0;
  590.       for( i ; i< min((ll)ptr.L,(ll)str.L-order[mid]+1); i++)
  591.       {
  592.         if (ptr[i] != str[order[mid]+i])
  593.         {
  594.           if (ptr[i] > str[order[mid]+i])
  595.             gr = true;
  596.           break;
  597.         }
  598.       }
  599.       if (i == ptr.L)
  600.       {
  601.         res1=max(res1,mid);
  602.         low=mid+1;
  603.       }
  604.       else if (!gr)
  605.         hi=mid-1;
  606.       else
  607.         low = mid+1;
  608.     }
  609.     trace(res2);
  610.     if (res2 == 1e9)
  611.       return -2;
  612.     return (seg.query(res2,res1));
  613.   }
  614.   pi getPosAndLength()
  615.   {
  616.       int res = 0;
  617.       int pos = -1;
  618.       REP(i,1,str.L)
  619.       {
  620.           int low = 0;
  621.           int hi = str.L-1-max(order[i],order[i-1]);
  622.           while(low<=hi)
  623.           {
  624.               int mid = (low+hi)/2;
  625.               bool ok =false;
  626.               int pp;
  627.               if (str.substr(order[i],mid)==str.substr(order[i-1],mid))
  628.               {
  629.                   ok=true;
  630.                   pp = order[i];
  631.               }
  632.               if (ok)
  633.               {
  634.                   if (mid > res)
  635.                   {
  636.                       res = max(res,mid);
  637.                       pos = pp;
  638.                   }        
  639.                   low=mid+1;
  640.               }
  641.               else
  642.                   hi=mid-1;
  643.           }
  644.  
  645.       }
  646.       return MP(res,pos);
  647.   }
  648.   string longestRepeating()
  649.   {
  650.       pi ans = getPosAndLength();
  651.       if (ans.F==0)
  652.           return "";
  653.       return str.substr(ans.S,ans.F);
  654.   }
  655.   vi get(){
  656.       return order;
  657.   }
  658.   public:
  659.   vi getLcp(){
  660.       return lcp;
  661.   }
  662.   public:
  663.   ll diffSubstrings()
  664.   {
  665.       ll out = 0;
  666.       REP(i,1,str.L)
  667.           out += str.L - order[i] - lcp[i]-1;
  668.       return out;
  669.   }
  670. };
  671. string longestCommonSubstring(string a, string b)
  672. {
  673.     int len = 0;
  674.     string res = a+'%'+b;
  675.     SuffixArray sf = SuffixArray(res);
  676.     vi order = sf.get();
  677.     vi lcp = sf.getLcp();
  678.     vi col(order.Z);
  679.     REP(i,0,order.Z)
  680.     {
  681.         if (order[i] < a.L)
  682.             col[order[i]] = 1;
  683.         else if (order[i] > a.L)
  684.             col[order[i]] = 2;
  685.     }
  686.     int pos = -1;
  687.     REP(i,1,order.Z)
  688.         if (col[order[i]]+col[order[i-1]] == 3)
  689.         {
  690.             if (lcp[i] > len)
  691.             {
  692.                 len = max(len,lcp[i]);
  693.                 pos = (col[order[i]] == 1?order[i]:order[i-1]);
  694.             }
  695.         }
  696.     return a.substr(pos,len);
  697. }
  698. class Factorial{
  699.     int nax;
  700.     vll fa;
  701.     vll in;
  702.     public:
  703.     Factorial(int n)
  704.     {
  705.         nax = n+10;
  706.         fa.assign(nax,1);
  707.         in.resize(nax);
  708.         REP(i,1,nax)
  709.             fa[i] = (fa[i-1]*i)%mod;
  710.         REP(i,0,nax)
  711.             in[i] = mbinp(fa[i],mod-2);
  712.     }
  713.     public:
  714.     ll fac(int x)
  715.     {
  716.         return fa[x];
  717.     }
  718.     public:
  719.     ll inv(int x)
  720.     {
  721.         return in[x];
  722.     }
  723.     public:
  724.     ll comb(int x, int y)
  725.     {
  726.         if (x < y || x < 0 || y < 0)
  727.             return 0;
  728.         return (((fa[x]*in[y])%mod)*in[x-y])%mod;
  729.     }
  730. };
  731. class WaveletTree{
  732.     typedef vector<int>::iterator it;
  733.     vector<vi> pre;
  734.     int mx;
  735.     public:
  736.     WaveletTree(vi &inp, int delta)
  737.     {
  738.         pre.resize(4*inp.Z);
  739.         mx = delta+1;
  740.         build(inp.B,inp.E,0,mx-1,1);
  741.     }
  742.     void build(it b, it e, int l, int r, int d)
  743.     {
  744.         if (l == r)
  745.             return;
  746.         int mid = (l+r)/2;
  747.         pre[d].PB(0);
  748.         for (it x = b; x != e; x++)
  749.             pre[d].PB(pre[d].back()+(*x<=mid));
  750.         it p = stable_partition(b,e,[=](int i){return i <= mid;});
  751.         build(b,p,l,mid,2*d);
  752.         build(p,e,mid+1,r,2*d+1);
  753.     }
  754.     int occurrenceOf(int c, int i)
  755.     {
  756.         i++;
  757.         int l = 0;
  758.         int r = mx-1;
  759.         int d = 1;
  760.         int mid;
  761.         int shift;
  762.         while(l != r)
  763.         {
  764.             int mid = (l+r)/2;
  765.             shift = pre[d][i];
  766.             d*=2;
  767.             if (c <= mid)
  768.             {
  769.                 i = shift;
  770.                 r= mid;
  771.             }
  772.             else
  773.             {
  774.                 i -= shift;
  775.                 l = mid+1;
  776.                 d++;
  777.             }
  778.         }
  779.         return i;
  780.     }
  781.     int kthSmallest(int k, int i, int j)
  782.     {
  783.         j++;
  784.         int l = 0,r=mx-1,d=1,ri,rj;
  785.         while(l!= r)
  786.         {
  787.             int mid = (l+r)/2;
  788.             ri = pre[d][i];
  789.             rj = pre[d][j];
  790.             d *= 2;
  791.             if (k <= rj-ri)
  792.             {
  793.                 i = ri;
  794.                 j = rj;
  795.                 r = mid;
  796.             }
  797.             else
  798.             {
  799.                 k -= rj-ri;
  800.                 i -= ri;
  801.                 j -= rj;
  802.                 l = mid+1;
  803.                 d++;
  804.             }
  805.         }
  806.         return r;
  807.     }
  808.     int rectangle(int i, int j, int a, int b, int d=1){
  809.         if (b < a || j < i)
  810.             return 0;
  811.         int l = a, r = b;
  812.         if (b < l || a > r)
  813.             return 0;
  814.         if (l <= a & r >= b)
  815.             return j-i;
  816.         int mid = (a+b)/2, ri=pre[d][i], rj= pre[d][j];
  817.         return rectangle(ri,rj,a,mid,d*2)+rectangle(i-ri,j-rj,mid+1,b,2*d+1);
  818.     }
  819. };
  820. class Centroid{
  821.     int n;
  822.     vector<set<int> > adj;
  823.     vi par;
  824.     vi has;
  825.     public:
  826.     Centroid(vector<vi> ad)
  827.     {
  828.         n = ad.Z;
  829.         adj.resize(n);
  830.         par.resize(n);
  831.         has.resize(n);
  832.         REP(i,0,n)
  833.             for (int z : ad[i])
  834.             {
  835.                 adj[i].insert(z);
  836.                 adj[z].insert(i);
  837.             }
  838.         build(0,-1);
  839.     }
  840.     int dfs(int x, int p)
  841.     {
  842.         has[x] = 1;
  843.         for (int z : adj[x])
  844.             if (z!=p)
  845.                 has[x] += dfs(z,x);
  846.         return has[x];
  847.     }
  848.     int centroid(int x, int p, int sz)
  849.     {
  850.         for (int z: adj[x])
  851.             if (z != p)
  852.                 if (has[z] > sz/2)
  853.                     return centroid(z,x,sz);
  854.         return x;
  855.     }
  856.     void build(int x,int p)
  857.     {
  858.         int n = dfs(x,p);
  859.         int c = centroid(x,p,n);
  860.         if (p == -1)
  861.             p = c;
  862.         par[c] = p;
  863.         vi tmp(adj[c].B,adj[c].E);
  864.         for (int z : tmp)
  865.         {
  866.             adj[z].erase(c);
  867.             adj[c].erase(z);
  868.         }
  869.         for (int z : tmp)
  870.             build(z,c);
  871.     }
  872.     public:
  873.     vi decompose()
  874.     {
  875.         return par;
  876.     }
  877. };
  878. class Node{
  879.     public:
  880.         Node *children[26];
  881.     public:
  882.         int cnt = 0;
  883.     public:
  884.         char t;
  885.     public:
  886.         Node(int alphabet, char c)
  887.         {
  888.             REP(i,0,alphabet)
  889.                 this->children[i] = NULL;
  890.             t = c;
  891.         }
  892. };
  893. class Matrix{
  894.     int n,m;
  895.     vector<vi> mat;
  896.     public:
  897.     Matrix(int n,int m, int type)
  898.     {
  899.         this->n=n;
  900.         this->m=m;
  901.         mat.assign(n,vi(m,0));
  902.         if(type==1)
  903.         {
  904.             REP(i,0,n)
  905.                 mat[i][i]=1;
  906.         }
  907.         if(type==2)
  908.         {
  909.             REP(i,0,n)
  910.                 REP(j,i,m)
  911.                 mat[i][j]=1;
  912.         }
  913.         if (type == 3)
  914.         {
  915.             REP(j,0,m)
  916.                 mat[0][j]=1;
  917.             REP(i,1,n)
  918.                 mat[i][i-1]=1;
  919.         }
  920.     }
  921.     Matrix(vector<vi> inp)
  922.     {
  923.         this->n = inp.Z;
  924.         this->m = inp[0].Z;
  925.         mat = inp;
  926.     }
  927.     Matrix operator + (const Matrix &b)
  928.     {
  929.         class Matrix out = Matrix(this->n,this->m,0);
  930.         REP(i,0,this->n)
  931.             REP(j,0,this->m)
  932.             out.mat[i][j] = (this->mat[i][j]+b.mat[i][j])%mod;
  933.         return out;
  934.     }
  935.     Matrix operator - (const Matrix &b)
  936.     {
  937.         class Matrix out = Matrix(this->n,this->m,0);
  938.         REP(i,0,this->n)
  939.             REP(j,0,this->m)
  940.             out.mat[i][j] = (this->mat[i][j]-b.mat[i][j]+mod)%mod;
  941.         return out;
  942.     }
  943.     Matrix operator * (const Matrix &b)
  944.     {
  945.         class Matrix out = Matrix(this->n,b.m,0);
  946.         REP(i,0,this->n)
  947.             REP(j,0,b.m)
  948.             REP(x,0,this->m)
  949.             {
  950.                 out.mat[i][j] += (this->mat[i][x]*b.mat[x][j])%mod;
  951.                 out.mat[i][j] %=mod;
  952.             }
  953.         return out;
  954.     }
  955.     Matrix operator ^ (const int &p)
  956.     {
  957.         return matbin(*this,p);
  958.     }
  959.     Matrix matbin(Matrix a, int b)
  960.     {
  961.         if (b==0)
  962.             return (Matrix(a.n,a.n,1));
  963.         Matrix res = matbin(a,b/2);
  964.         if (b%2)
  965.             return res*res*a;
  966.         else
  967.             return res*res;
  968.     }
  969.     int get(int x,int y)
  970.     {
  971.         return this->mat[x][y];
  972.     }
  973. };
  974. class Trie{
  975.     Node *root;
  976.     int alphabet;
  977.     char start;
  978.     public:
  979.     Trie(int alphabet, char start)
  980.     {
  981.         this->alphabet = alphabet;
  982.         root = new Node(alphabet,'*');
  983.         this->start = start;
  984.     }
  985.     public:
  986.     void insert(string str)
  987.     {
  988.         Node *cur = root;
  989.         REP(i,0,str.L)
  990.         {
  991.             if (cur->children[str[i]-start] == NULL)
  992.             {
  993.                 cur->children[str[i]-start] = new Node(alphabet,str[i]);
  994.             }
  995.             cur = cur->children[str[i]-start];
  996.         }
  997.         cur->cnt++;
  998.     }
  999.     public:
  1000.     bool exists(string str)
  1001.     {
  1002.         Node *cur = root;
  1003.         REP(i,0,str.L)
  1004.         {
  1005.             if (cur->children[str[i]-start] == NULL)
  1006.                 return false;
  1007.             cur = cur->children[str[i]-start];
  1008.         }
  1009.         return (cur->cnt > 0);
  1010.     }
  1011.     public:
  1012.     int count(string str)
  1013.     {
  1014.         Node *cur = root;
  1015.         REP(i,0,str.L)
  1016.         {
  1017.             if (cur->children[str[i]-start] == NULL)
  1018.                 return 0;
  1019.             cur = cur->children[str[i]-start];
  1020.         }
  1021.         return (cur->cnt);
  1022.     }
  1023.     public:
  1024.     void erase(string str)
  1025.     {
  1026.         Node *cur = root;
  1027.         REP(i,0,str.L)
  1028.         {
  1029.             if (cur->children[str[i]-start] == NULL)
  1030.                 cur->children[str[i]-start] = new Node(alphabet,str[i]);
  1031.             cur = cur->children[str[i]-start];
  1032.         }
  1033.         cur->cnt--;
  1034.     }
  1035. };
  1036. struct edge{
  1037.     int a,b,l,r;
  1038.     edge(int a,int b,int l,int r)
  1039.     {
  1040.         this->a=a;
  1041.         this->b=b;
  1042.         this->l=l;
  1043.         this->r=r;
  1044.     }
  1045. };
  1046.  
  1047. struct DynamicDsu{
  1048.     struct change{
  1049.         int u,v,ru,rv;
  1050.         change(int _u,int _v,int _ru,int _rv) :u(_u),v(_v),ru(_ru),rv(_rv){}
  1051.     };
  1052.     int sz;
  1053.     int cc;
  1054.     vi par;
  1055.     vi rnk;
  1056.     stack<change> op;
  1057.     DynamicDsu(){}
  1058.     DynamicDsu(int n)
  1059.     {
  1060.         sz =n;
  1061.         cc = n;
  1062.         par.resize(n);
  1063.         rnk.resize(n);
  1064.         REP(i,0,n)
  1065.         {
  1066.             par[i]=i;  
  1067.             rnk[i]=0;
  1068.         }
  1069.     }
  1070.     int find(int x)
  1071.     {
  1072.         return par[x] ==x?x:find(par[x]);
  1073.     }
  1074.     bool merge(int a, int b)
  1075.     {
  1076.         int x=find(a);
  1077.         int y=find(b);
  1078.         if(x == y)
  1079.             return false;
  1080.         cc--;
  1081.         if(rnk[y]>rnk[x])
  1082.             swap(y,x);
  1083.         op.push(change(y,x,rnk[y],rnk[x]));
  1084.         if (rnk[x]==rnk[y])
  1085.             rnk[x]++;
  1086.         return true;
  1087.     }
  1088.     void rollback()
  1089.     {
  1090.         if (op.empty())
  1091.             return;
  1092.         change did = op.top();
  1093.         op.pop();
  1094.         cc++;
  1095.         par[did.u]=did.u;
  1096.         par[did.v]=did.v;
  1097.         rnk[did.u]=did.ru;
  1098.         rnk[did.v]=did.rv;
  1099.     }
  1100. };
  1101. struct event{
  1102.     int u,v;
  1103.     bool good;
  1104.     event(int _u,int _v):u(_u),v(_v){}
  1105. };
  1106.  
  1107. struct QueryTree{
  1108.     vector<vector<event> > tree;
  1109.     int time;
  1110.     vi ans;
  1111.     DynamicDsu dsu;
  1112.     QueryTree(int T,int n)
  1113.     {
  1114.         dsu = DynamicDsu(n);
  1115.         time =T;
  1116.         tree.resize(4*T);
  1117.         ans.resize(T);
  1118.         ans[0]=n;
  1119.     }
  1120.     void addIt(int id,int l,int r, int el,int er, event &e)
  1121.     {
  1122.         if (l<=el&&er<=r)
  1123.         {
  1124.             tree[id].PB(e);
  1125.             return ;
  1126.         }
  1127.         if (l >er ||r < el)
  1128.             return;
  1129.         int mid=(l+r)/2;
  1130.         addIt(2*id,l,mid,el,er,e);
  1131.         addIt(2*id+1,mid+1,r,el,er,e);
  1132.     }
  1133.     void addEvent(int l, int r, event e)
  1134.     {
  1135.         addIt(1,0,time-1,l,r,e);
  1136.     }
  1137.     void dfs(int id,int l,int r)
  1138.     {
  1139.         for(event &e :tree[id])
  1140.             e.good=dsu.merge(e.u,e.v);
  1141.         if (l==r)
  1142.             ans[l]=dsu.cc;
  1143.         else
  1144.         {
  1145.             int mid=(l+r)/2;
  1146.             dfs(2*id,l,mid);
  1147.             dfs(2*id+1,mid+1,r);
  1148.         }
  1149.     }
  1150.     vi solve()
  1151.     {
  1152.         dfs(1,0,time-1);
  1153.         return ans;
  1154.     }
  1155. };
  1156. struct Point
  1157. {
  1158.     int x,y;
  1159.     Point(){}
  1160.     Point(int _x,int _y):x(_x),y(_y){}
  1161.     void read()
  1162.     {
  1163.         cin >> x >> y;
  1164.     }
  1165. };
  1166. struct Vector
  1167. {
  1168.     int x,y;
  1169.     Point u,v;
  1170.     Vector(){}
  1171.     Vector(Point _a,Point _b):x(_b.x-_a.x),y(_b.y-_a.y),u(_a),v(_b){}
  1172.     Vector(int _a,int _b):x(_a),y(_b),u(0,0),v(0,0){}
  1173.     int orientation(Point a)
  1174.     {
  1175.         Vector other =Vector(u,a);
  1176.         if (*this*other < 0)
  1177.             return -1;
  1178.         else if (*this*other == 0)
  1179.             return 0;
  1180.         else
  1181.             return 1;
  1182.     }
  1183.     int operator * (const Vector &other)
  1184.     {
  1185.         return this->x*other.y-this->y*other.x;
  1186.     }
  1187. };
  1188. struct PersistentSeg{
  1189.     struct node{
  1190.         node *l,*r;
  1191.         int sum;
  1192.         node(int val):l(nullptr),r(nullptr),sum(val){}
  1193.         node(node *a,node *b)
  1194.         {
  1195.             l=a;
  1196.             r=b;
  1197.             sum=0;
  1198.             if(a)
  1199.                 sum+=a->sum;
  1200.             if(b)
  1201.                 sum+=b->sum;
  1202.         }
  1203.     };
  1204.     vector<vector<node*>> states;
  1205.     vi vals;
  1206.     int len;
  1207.     PersistentSeg(vi a)
  1208.     {
  1209.         vals=a;
  1210.         len =a.Z;
  1211.         node *root;
  1212.         root = build(0,len-1);
  1213.         vector<node*> xx;
  1214.         xx.PB(root);
  1215.         states.PB(xx);
  1216.     }
  1217.     node* build(int l,int r)
  1218.     {
  1219.         if(l==r)
  1220.             return new node(vals[l]);
  1221.         int mid = (l+r)/2;
  1222.         return new node(build(l,mid),build(mid+1,r));
  1223.     }
  1224.     int getSum(node *root, int l,int r, int sl,int sr)
  1225.     {
  1226.         if (r < sl || l > sr)
  1227.             return 0;
  1228.         if (l>=sl&&r<=sr)
  1229.             return root->sum;
  1230.         int mid = (l+r)/2;
  1231.         return (getSum(root->l,l,mid,sl,sr)+getSum(root->r,mid+1,r,sl,sr));
  1232.     }
  1233.     int getSum(int k,int l,int r)
  1234.     {
  1235.         return getSum(states[k].back(),0,len-1,l,r);
  1236.     }
  1237.     node *update(node *root,int l,int r,int pos,int val)
  1238.     {
  1239.         if (l==r)
  1240.             return new node(val);
  1241.         int mid=(l+r)/2;
  1242.         if (pos<=mid)
  1243.             return new node(update(root->l,l,mid,pos,val),root->r);
  1244.         else
  1245.             return new node(root->l,update(root->r,mid+1,r,pos,val));
  1246.     }
  1247.     void update(int k,int pos,int val)
  1248.     {
  1249.         node* upd = update(states[k].back(),0,len-1,pos,val);
  1250.         states[k].PB(upd);
  1251.     }
  1252.     void copy(int k)
  1253.     {
  1254.         node *copy = states[k].back();
  1255.         vector<node*> xx;
  1256.         xx.PB(copy);
  1257.         states.PB(xx);
  1258.     }
  1259. };
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!