SHARE
TWEET

bit

warriorscats Jun 30th, 2020 1,083 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC diagnostic push
  2. #pragma GCC diagnostic ignored "-Wbuiltin-declaration-mismatch"
  3. #include <fstream>
  4. #include <vector>
  5.  
  6. namespace fast_and_furious {
  7.     class InParser {
  8.     public:
  9.         InParser (const char* file_name) {
  10.             input_file.open (file_name, std::ios::in);
  11.             input_file.sync_with_stdio (false);
  12.             index = 0;
  13.             input_file.read (buffer, SIZE);
  14.         }
  15.  
  16.         InParser& operator >> (int &n) {
  17.             for (; !std::isdigit (buffer[index]); increment ());
  18.             n = 0;
  19.             for (; std::isdigit (buffer[index]); increment ())
  20.                 n = n * 10 + (buffer[index] - '0');
  21.  
  22.             return *this;
  23.         }
  24.  
  25.         ~InParser () {
  26.             input_file.close ();
  27.         }
  28.  
  29.     private:
  30.         std::fstream input_file;
  31.         static const int SIZE = 0x1000;
  32.         int index;
  33.         char buffer[SIZE];
  34.  
  35.         void increment () {
  36.             if (++ index == SIZE)
  37.                 index = 0, input_file.read (buffer, SIZE);
  38.         }
  39.     };
  40.  
  41.     class OutParser {
  42.     public:
  43.         OutParser (const char* file_name) {
  44.             output_file.open (file_name, std::ios::out);
  45.             output_file.sync_with_stdio (false);
  46.             index = 0;
  47.         }
  48.  
  49.         OutParser& operator << (int64_t target) {
  50.             if (target < 10)
  51.                 increment (target + '0');
  52.             else {
  53.                 (*this) << (target / 10);
  54.                 increment (target % 10 + '0');
  55.             }
  56.  
  57.             return *this;
  58.         }
  59.  
  60.         OutParser& operator << (int target) {
  61.             if (target < 10)
  62.                 increment (target + '0');
  63.             else {
  64.                 (*this) << (target / 10);
  65.                 increment (target % 10 + '0');
  66.             }
  67.  
  68.             return *this;
  69.         }
  70.  
  71.         OutParser& operator << (const char* target) {
  72.             int aux = 0;
  73.             while (target[aux])
  74.                 increment (target[aux ++]);
  75.  
  76.             return *this;
  77.         }
  78.  
  79.         ~OutParser () {
  80.             output_file.write (buffer, index);
  81.             output_file.close ();
  82.         }
  83.  
  84.     private:
  85.         std::fstream output_file;
  86.         static const int SIZE = 0x1000;
  87.         int index;
  88.         char buffer[SIZE];
  89.  
  90.         void increment (char ch) {
  91.             if (index == SIZE)
  92.                 index = 0, output_file.write (buffer, SIZE), buffer[index ++] = ch;
  93.             else buffer[index ++] = ch;
  94.         }
  95.     };
  96.  
  97.     class FenwickTree {
  98.         std::vector <std::vector <int>> BIT;
  99.         int N;
  100.         int LSB (int x) {
  101.             return x & -x;
  102.         }
  103.         int Query (int x, int y) {
  104.             int sum = 0;
  105.             for (int i = x; i > 0; i -= LSB (i))
  106.                 for (int j = y; j > 0; j -= LSB (j))
  107.                     sum += BIT[i][j];
  108.             return sum;
  109.         }
  110.  
  111.     public:
  112.         FenwickTree (int n): N (n) {
  113.             BIT.assign (N + 1, std::vector <int> (N + 1, 0));
  114.         }
  115.         ~FenwickTree () {
  116.             for (auto line: BIT)
  117.                 line.clear ();
  118.             BIT.clear ();
  119.         }
  120.         void Update (int x, int y, int val) {
  121.             for (int i = x; i <= N; i += LSB (i))
  122.                 for (int j = y; j <= N; j += LSB (j))
  123.                     BIT[i][j] += val;
  124.         }
  125.         int Query (int x1, int y1, int x2, int y2) {
  126.             return Query (x2, y2) - Query (x2, y1 - 1) - Query (x1 - 1, y2) + Query (x1 - 1, y1 - 1);
  127.         }
  128.     };
  129. };
  130. using namespace fast_and_furious;
  131.  
  132.  
  133. InParser fin ("aib2d.in");
  134. OutParser fout ("aib2d.out");
  135.  
  136. int n, q, task, x1, y1, x2, y2, val;
  137.  
  138.  
  139. int main () {
  140.     fin >> n;
  141.     FenwickTree BIT (n);
  142.     for (int i = 1; i <= n; ++ i)
  143.         for (int j = 1; j <= n; ++ j)
  144.             fin >> val, BIT.Update (i, j, val);
  145.     fin >> q;
  146.     for (int i = 1; i <= q; ++ i) {
  147.         fin >> task;
  148.         if (task == 1)
  149.             fin >> x1 >> y1 >> val, BIT.Update (x1, y1, val);
  150.         else
  151.             fin >> x1 >> y1 >> x2 >> y2, fout << BIT.Query (x1, y1, x2, y2) << "\n";
  152.     }
  153.  
  154.     return 0;
  155. }
  156. #pragma GCC diagnostic pop
RAW Paste Data
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
Top