test/yukicoder/925.SqrtDC.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://yukicoder.me/problems/no/925

Depends on

• 典型的な平方分割 (src/DataStructure/SortedPerBucket.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/925
// competitive-verifier: TLE 7
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "src/DataStructure/SortedPerBucket.hpp"
using namespace __gnu_pbds;
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<long long> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SortedPerBucket<long long, 1024> sqrtdc(a);
 long long s= 0;
 tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> S(a.begin(), a.end());
 while (Q--) {
  int op;
  cin >> op;
  if (op == 1) {
   long long X, Y;
   cin >> X >> Y;
   (X^= s)&= (1 << 16) - 1, (Y^= s)&= (1ll << 40) - 1;
   X--;
   sqrtdc.set(X, Y);
   S.insert(Y);
  } else {
   int L, R;
   cin >> L >> R;
   (L^= s)&= (1 << 16) - 1, (R^= s)&= (1 << 16) - 1;
   if (L > R) swap(L, R);
   L--;
   int m= (R - L) / 2;
   int ok= 0, ng= S.size();
   while (abs(ok - ng) > 1) {
    int i= (ok + ng) / 2;
    (sqrtdc.count(L, R, *S.find_by_order(i)) <= m ? ok : ng)= i;
   }
   long long x= *S.find_by_order(ok);
   long long ans= sqrtdc.sum(L, R) - sqrtdc.sum(L, R, x) * 2;
   ans-= x * (R - L - sqrtdc.count(L, R, x) * 2);
   cout << ans << '\n';
   s^= ans;
  }
 }
 return 0;
}

#line 1 "test/yukicoder/925.SqrtDC.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/925
// competitive-verifier: TLE 7
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#line 2 "src/DataStructure/SortedPerBucket.hpp"
#include <limits>
#include <algorithm>
#include <array>
#line 6 "src/DataStructure/SortedPerBucket.hpp"
#include <numeric>
template <class T, size_t B= 700> class SortedPerBucket {
 static constexpr T INF= std::numeric_limits<T>::max() / 2;
 struct Dat {
  const size_t n;
  T a[B], sorted[B], acc[B + 1];
  T add, lb, ub;
  Dat(size_t b): n(b), a{0}, sorted{0}, acc{0}, add(0), lb(-INF), ub(INF) {}
  Dat(const T *bg, size_t b): n(b), a{0}, acc{0}, add(0), lb(-INF), ub(INF) {
   for (int i= n; i--;) a[i]= *(bg + i);
   build();
  }
  inline bool eval() {
   if (add == 0 && lb == -INF && ub == INF) return false;
   for (auto &x: a) x= std::clamp(x, lb, ub) + add;
   return add= 0, lb= -INF, ub= INF, true;
  }
  inline void build() { std::copy_n(a, B, sorted), std::sort(sorted, sorted + n), std::partial_sum(sorted, sorted + n, acc + 1); }
  inline size_t idx(T x) const { return std::lower_bound(sorted, sorted + n, x) - sorted; }
  inline size_t count(T x) const { return x-= add, (x <= lb ? 0 : ub < x ? n : idx(x)); }
  inline T sum() const {
   size_t l= idx(lb), u= idx(ub);
   return acc[u] - acc[l] + lb * l + ub * (n - u) + add * n;
  }
  inline T sum(T x) const {
   if (x-= add; x <= lb) return 0;
   if (ub < x) return sum();
   size_t l= idx(lb), u= idx(x);
   return acc[u] - acc[l] + lb * l + add * u;
  }
  inline T get(size_t k) const { return std::clamp(a[k], lb, ub) + add; }
 };
 const size_t n;
 std::vector<Dat> dat;
 template <class U, class All, class One> inline U prod(size_t l, size_t r, const All &all, const One &one) const {
  U ret= 0;
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (; k < dat[i].n; ++k) ret+= one(dat[i].get(k));
    ++i;
   }
   for (; i < j; ++i) ret+= all(dat[i]);
   for (; m--;) ret+= one(dat[j].get(m));
  } else
   for (; k < m; ++k) ret+= one(dat[i].get(k));
  return ret;
 }
 template <class All, class One> inline void update(size_t l, size_t r, const All &all, const One &one) {
  if (size_t i= l / B, j= r / B, k= l % B, m= r % B; i < j) {
   if (k) {
    for (dat[i].eval(); k < dat[i].n; k++) one(dat[i].a[k]);
    dat[i].build(), ++i;
   }
   for (; i < j; ++i) all(dat[i]);
   if (m) {
    for (dat[j].eval(); m--;) one(dat[j].a[m]);
    dat[j].build();
   }
  } else {
   for (dat[i].eval(); k < m; ++k) one(dat[i].a[k]);
   dat[i].build();
  }
 }
public:
 SortedPerBucket(size_t n): n(n) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(r - l);
 }
 SortedPerBucket(const std::vector<T> &a): n(a.size()) {
  for (size_t l= 0, r; l < n; l= r) r= std::min(l + B, n), dat.emplace_back(a.data() + l, r - l);
 }
 // count i s.t. (l <= i < r) && (a[i] < ub)
 size_t count(size_t l, size_t r, T ub) const {
  return prod<size_t>(l, r, [&](const Dat &d) { return d.count(ub); }, [&](T x) { return x < ub; });
 }
 // count i s.t. (l <= i < r) && (lb <= a[i] < ub)
 size_t count(size_t l, size_t r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
 // sum a[i] s.t. (l <= i < r)
 T sum(size_t l, size_t r) const {
  return prod<T>(l, r, [&](const Dat &d) { return d.sum(); }, [&](T x) { return x; });
 }
 // sum a[i] s.t. (l <= i < r) && (a[i] < ub)
 T sum(size_t l, size_t r, T ub) const {
  return prod<T>(l, r, [&](const Dat &d) { return d.sum(ub); }, [&](T x) { return x < ub ? x : 0; });
 }
 // sum a[i] s.t. (l <= i < r)  && (lb <= a[i] < ub)
 T sum(size_t l, size_t r, T lb, T ub) const { return sum(l, r, ub) - sum(l, r, lb); }
 void set(size_t k, T x) {
  size_t i= k / B, j= k % B;
  dat[i].eval(), dat[i].a[j]= x, dat[i].build();
 }
 T get(size_t k) const { return dat[k / B].get(k % B); }
 T operator[](size_t k) const { return get(k); }
 void add(size_t l, size_t r, T v) {
  update(l, r, [&](Dat &d) { d.add+= v; }, [&](T &x) { x+= v; });
 }
 void chmin(size_t l, size_t r, T ub) {
  auto f= [&](Dat &d) {
   T b= ub - d.add;
   d.ub= std::min(d.ub, b), d.lb= std::min(d.lb, b);
  };
  update(l, r, f, [&](T &x) { x= std::min(x, ub); });
 }
 void chmax(size_t l, size_t r, T lb) {
  auto f= [&](Dat &d) {
   T a= lb - d.add;
   d.lb= std::max(d.lb, a), d.ub= std::max(d.ub, a);
  };
  update(l, r, f, [&](T &x) { x= std::max(x, lb); });
 }
 void chclamp(size_t l, size_t r, T lb, T ub) {
  auto f= [&](Dat &d) {
   T a= lb - d.add, b= ub - d.add;
   d.ub= std::clamp(d.ub, a, b), d.lb= std::clamp(d.lb, a, b);
  };
  update(l, r, f, [&](T &x) { x= std::clamp(x, lb, ub); });
 }
};
#line 9 "test/yukicoder/925.SqrtDC.test.cpp"
using namespace __gnu_pbds;
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 vector<long long> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SortedPerBucket<long long, 1024> sqrtdc(a);
 long long s= 0;
 tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> S(a.begin(), a.end());
 while (Q--) {
  int op;
  cin >> op;
  if (op == 1) {
   long long X, Y;
   cin >> X >> Y;
   (X^= s)&= (1 << 16) - 1, (Y^= s)&= (1ll << 40) - 1;
   X--;
   sqrtdc.set(X, Y);
   S.insert(Y);
  } else {
   int L, R;
   cin >> L >> R;
   (L^= s)&= (1 << 16) - 1, (R^= s)&= (1 << 16) - 1;
   if (L > R) swap(L, R);
   L--;
   int m= (R - L) / 2;
   int ok= 0, ng= S.size();
   while (abs(ok - ng) > 1) {
    int i= (ok + ng) / 2;
    (sqrtdc.count(L, R, *S.find_by_order(i)) <= m ? ok : ng)= i;
   }
   long long x= *S.find_by_order(ok);
   long long ans= sqrtdc.sum(L, R) - sqrtdc.sum(L, R, x) * 2;
   ans-= x * (R - L - sqrtdc.count(L, R, x) * 2);
   cout << ans << '\n';
   s^= ans;
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	000_sample_1.txt	AC	6 ms	4 MB
g++-13	000_sample_2.txt	AC	6 ms	4 MB
g++-13	000_sample_3.txt	AC	5 ms	4 MB
g++-13	100_small_rand_1.txt	AC	22 ms	4 MB
g++-13	100_small_rand_2.txt	AC	23 ms	4 MB
g++-13	200_large_rand_1.txt	AC	2240 ms	12 MB
g++-13	200_large_rand_2.txt	AC	2240 ms	12 MB
g++-13	200_large_rand_3.txt	AC	2249 ms	11 MB
g++-13	201_fewnums_1.txt	AC	1473 ms	6 MB
g++-13	202_toofew_1.txt	AC	986 ms	6 MB
g++-13	203_biased1_1.txt	AC	1976 ms	10 MB
g++-13	204_biased2_1.txt	AC	2422 ms	13 MB
g++-13	205_many_1.txt	AC	2046 ms	11 MB
g++-13	206_dec1_1.txt	AC	1819 ms	11 MB
g++-13	207_inc1_1.txt	AC	1130 ms	5 MB
g++-13	208_dec2_1.txt	AC	1786 ms	12 MB
g++-13	209_inc2_1.txt	AC	2916 ms	10 MB
g++-13	210_biased3_1.txt	AC	2283 ms	8 MB
g++-13	300_max_rand_1.txt	AC	2419 ms	12 MB
g++-13	301_many2_1.txt	AC	1979 ms	10 MB
g++-13	302_many1_1.txt	AC	2447 ms	13 MB
g++-13	303_many1dec_1.txt	AC	1868 ms	14 MB
clang++-18	000_sample_1.txt	AC	6 ms	4 MB
clang++-18	000_sample_2.txt	AC	5 ms	4 MB
clang++-18	000_sample_3.txt	AC	5 ms	4 MB
clang++-18	100_small_rand_1.txt	AC	21 ms	4 MB
clang++-18	100_small_rand_2.txt	AC	22 ms	4 MB
clang++-18	200_large_rand_1.txt	AC	2179 ms	11 MB
clang++-18	200_large_rand_2.txt	AC	2181 ms	12 MB
clang++-18	200_large_rand_3.txt	AC	2190 ms	12 MB
clang++-18	201_fewnums_1.txt	AC	1481 ms	6 MB
clang++-18	202_toofew_1.txt	AC	987 ms	6 MB
clang++-18	203_biased1_1.txt	AC	1918 ms	10 MB
clang++-18	204_biased2_1.txt	AC	2434 ms	13 MB
clang++-18	205_many_1.txt	AC	2045 ms	11 MB
clang++-18	206_dec1_1.txt	AC	1713 ms	11 MB
clang++-18	207_inc1_1.txt	AC	1170 ms	6 MB
clang++-18	208_dec2_1.txt	AC	1660 ms	11 MB
clang++-18	209_inc2_1.txt	AC	2636 ms	10 MB
clang++-18	210_biased3_1.txt	AC	2108 ms	8 MB
clang++-18	300_max_rand_1.txt	AC	2430 ms	12 MB
clang++-18	301_many2_1.txt	AC	2104 ms	10 MB
clang++-18	302_many1_1.txt	AC	2464 ms	13 MB
clang++-18	303_many1dec_1.txt	AC	1885 ms	14 MB

Back to top page