fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 200005;
  5. const int MAXK = 5;
  6. const int INF = 1e9;
  7.  
  8. int n, k, q;
  9. int a[MAXN][MAXK];
  10.  
  11.  
  12. struct Node {
  13.     int min_val[1 << MAXK];
  14.     int max_val[1 << MAXK];
  15. };
  16.  
  17. Node tree[4 * MAXN];
  18.  
  19.  
  20. void build(int id, int l, int r) {
  21.     if (l == r) {
  22.         for (int mask = 0; mask < (1 << k); mask++) {
  23.             int sum = 0;
  24.             for (int i = 0; i < k; i++) {
  25.                 if (mask & (1 << i)) {
  26.                     sum += a[l][i];
  27.                 } else {
  28.                     sum -= a[l][i];
  29.                 }
  30.             }
  31.             tree[id].min_val[mask] = sum;
  32.             tree[id].max_val[mask] = sum;
  33.         }
  34.         return;
  35.     }
  36.  
  37.     int mid = (l + r) / 2;
  38.     build(id * 2, l, mid);
  39.     build(id * 2 + 1, mid + 1, r);
  40.  
  41.     for (int mask = 0; mask < (1 << k); mask++) {
  42.         tree[id].min_val[mask] = min(tree[id * 2].min_val[mask], tree[id * 2 + 1].min_val[mask]);
  43.         tree[id].max_val[mask] = max(tree[id * 2].max_val[mask], tree[id * 2 + 1].max_val[mask]);
  44.     }
  45. }
  46.  
  47.  
  48. void update(int id, int l, int r, int pos) {
  49.     if (l == r) {
  50.         for (int mask = 0; mask < (1 << k); mask++) {
  51.             int sum = 0;
  52.             for (int i = 0; i < k; i++) {
  53.                 if (mask & (1 << i)) {
  54.                     sum += a[l][i];
  55.                 } else {
  56.                     sum -= a[l][i];
  57.                 }
  58.             }
  59.             tree[id].min_val[mask] = sum;
  60.             tree[id].max_val[mask] = sum;
  61.         }
  62.         return;
  63.     }
  64.  
  65.     int mid = (l + r) / 2;
  66.     if (pos <= mid) {
  67.         update(id * 2, l, mid, pos);
  68.     } else {
  69.         update(id * 2 + 1, mid + 1, r, pos);
  70.     }
  71.  
  72.     for (int mask = 0; mask < (1 << k); mask++) {
  73.         tree[id].min_val[mask] = min(tree[id * 2].min_val[mask], tree[id * 2 + 1].min_val[mask]);
  74.         tree[id].max_val[mask] = max(tree[id * 2].max_val[mask], tree[id * 2 + 1].max_val[mask]);
  75.     }
  76. }
  77.  
  78.  
  79. pair<int, int> query(int id, int l, int r, int ql, int qr, int mask) {
  80.     if (ql <= l && r <= qr) {
  81.         return {tree[id].min_val[mask], tree[id].max_val[mask]};
  82.     }
  83.  
  84.     int mid = (l + r) / 2;
  85.     pair<int, int> res = {INF, -INF};
  86.  
  87.     if (ql <= mid) {
  88.         auto left_res = query(id * 2, l, mid, ql, qr, mask);
  89.         res.first = min(res.first, left_res.first);
  90.         res.second = max(res.second, left_res.second);
  91.     }
  92.  
  93.     if (qr > mid) {
  94.         auto right_res = query(id * 2 + 1, mid + 1, r, ql, qr, mask);
  95.         res.first = min(res.first, right_res.first);
  96.         res.second = max(res.second, right_res.second);
  97.     }
  98.  
  99.     return res;
  100. }
  101.  
  102. int main() {
  103.     ios_base::sync_with_stdio(false);
  104.     cin.tie(NULL);
  105.  
  106.     cin >> n >> k;
  107.     for (int i = 1; i <= n; i++) {
  108.         for (int j = 0; j < k; j++) {
  109.             cin >> a[i][j];
  110.         }
  111.     }
  112.  
  113.     build(1, 1, n);
  114.  
  115.     cin >> q;
  116.     while (q--) {
  117.         int type;
  118.         cin >> type;
  119.  
  120.         if (type == 1) {
  121.             int idx;
  122.             cin >> idx;
  123.             for (int j = 0; j < k; j++) {
  124.                 cin >> a[idx][j];
  125.             }
  126.             update(1, 1, n, idx);
  127.         } else {
  128.             int l, r;
  129.             cin >> l >> r;
  130.  
  131.             int ans = 0;
  132.             for (int mask = 0; mask < (1 << k); mask++) {
  133.                 auto [min_val, max_val] = query(1, 1, n, l, r, mask);
  134.                 ans = max(ans, max_val - min_val);
  135.             }
  136.  
  137.             cout << ans << "\n";
  138.         }
  139.     }
  140.  
  141.     return 0;
  142. }
Success #stdin #stdout 0s 5680KB
comments (?)
stdin 
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5
stdout 
8
4
4
12
10
https://ideone.com/oCiajt
language:
C++ (gcc 8.3)
created:
13 days 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!