Dang_Quan_10_Tin

Static ConvexHullTrick don't need order of A

Dec 8th, 2021 (edited)
653
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // O(nlog^2)
  2. // Chỉnh thành max nhớ thay thành hệ số giảm và chỉnh B[line.back()] > B[i] thành B[line.back()] < B[i], chỉnh A[x] < A[y] thành A[x] > A[y], x = min(x, f[i].Get(v)) thành x = max(x, f[i].Get(v)), x = Inf thành x = -Inf
  3. // Nhớ resize f thành log(n) nha
  4.  
  5. constexpr ll Inf = 1e17;
  6. ll A[N], B[N];
  7.  
  8. struct ConvexHullTrick
  9. {
  10.     vector<int> line;
  11.     vector<ld> point;
  12.     ConvexHullTrick(int n = 0)
  13.     {
  14.         point.emplace_back(-Inf);
  15.     }
  16.  
  17.     ld ff(int x, int y)
  18.     {
  19.         return (ld)1.0 * (B[y] - B[x]) / (A[x] - A[y]);
  20.     }
  21.  
  22.     void Add(int i)
  23.     {
  24.         while ((int)line.size() > 1 || ((int)line.size() == 1 && A[line.back()] == A[i]))
  25.         {
  26.             if (A[line.back()] == A[i])
  27.             {
  28.                 if (B[line.back()] > B[i])
  29.                 {
  30.                     line.pop_back();
  31.                     if (!line.empty())
  32.                         point.pop_back();
  33.                 }
  34.                 else
  35.                     break;
  36.             }
  37.             else
  38.             {
  39.                 if (ff(i, line.back()) <= ff(i, line[line.size() - 2]))
  40.                 {
  41.                     line.pop_back();
  42.                     if (!line.empty())
  43.                         point.pop_back();
  44.                 }
  45.                 else
  46.                     break;
  47.             }
  48.         }
  49.  
  50.         if (line.empty() || A[line.back()] != A[i])
  51.         {
  52.             if (!line.empty())
  53.                 point.emplace_back(ff(line.back(), i));
  54.             line.emplace_back(i);
  55.         }
  56.     }
  57.  
  58.     ll More(int x)
  59.     {
  60.         return ;
  61.     }
  62.  
  63.     ll X(int x)
  64.     {
  65.         return ;
  66.     }
  67.  
  68.     ll Get(int x)
  69.     {
  70.         int j = lower_bound(point.begin(), point.end(), X(x)) - point.begin();
  71.         return A[line[j - 1]] * X(x) + B[line[j - 1]] + More(x);
  72.     }
  73. };
  74. vector<ConvexHullTrick> f;
  75.  
  76. ll Get(int v)
  77. {
  78.     ll x = Inf;
  79.  
  80.     for (int i = 0; i < 17; ++i)
  81.         if (!f[i].line.empty())
  82.             x = min(x, f[i].Get(v));
  83.  
  84.     return x;
  85. }
  86.  
  87. void Add(int v)
  88. {
  89.     vector<int> p({v});
  90.     for (int i = 0; i < 17; ++i)
  91.         if (f[i].line.empty())
  92.         {
  93.             sort(p.begin(), p.end(), [&](const int &x, const int &y)
  94.                  { return A[x] < A[y]; });
  95.  
  96.             for (auto j : p)
  97.                 f[i].Add(j);
  98.             break;
  99.         }
  100.         else
  101.         {
  102.             for (auto j : f[i].line)
  103.                 p.emplace_back(j);
  104.             f[i].Clear();
  105.         }
  106. }
RAW Paste Data