fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
  4. #define ll long long
  5. #define pb push_back
  6. #define all(x) x.begin(), x.end()
  7.  
  8. const int INF = 1e9;
  9. const ll LLINF = 1e18;
  10. const int N = 1030;
  11.  
  12. int a[N][N], fen[N][N];
  13. int n;
  14.  
  15. void fenUpdate(int x, int y, int k){
  16.     for (int i=x; i<=n; i+=i&-i)
  17.         for (int j=y; j<=n; j+=j&-j)
  18.             fen[i][j]+=k;
  19. }
  20.  
  21. int fenGet(int x, int y){
  22.     int ans = 0;
  23.     for (int i=x; i>0; i-=i&-i)
  24.         for (int j=y; j>0; j-=j&-j)
  25.             ans+=fen[i][j];
  26.     return ans;
  27. }
  28.  
  29. int fenSum(int x1, int y1, int x2, int y2){
  30.     return fenGet(x2, y2)
  31.             - fenGet(x1-1, y2)
  32.             - fenGet(x2, y1-1)
  33.             + fenGet(x1-1, y1-1);
  34. }
  35.  
  36. int main(){
  37.     fastIO;
  38.  
  39.     int t;
  40.     cin >> t;
  41.     while (t--){
  42.         cin >> n;
  43.         string s;
  44.         while (cin >> s){
  45.             if (s=="SET"){
  46.                 int x, y, k;
  47.                 cin >> x >> y >> k;
  48.                 x++;
  49.                 y++;
  50.                 fenUpdate(x, y, -a[x][y]);
  51.                 a[x][y] = k;
  52.                 fenUpdate(x, y, a[x][y]);
  53.             }
  54.             else if (s=="SUM"){
  55.                 int x1, x2, y1, y2;
  56.                 cin >> x1 >> y1 >> x2 >> y2;
  57.                 cout << fenSum(++x1, ++y1, ++x2, ++y2) << '\n';
  58.             }
  59.             else break;
  60.         }
  61.         cout << '\n';
  62.         for (int i=1; i<=n; i++) for (int j=1; j<=n; j++){
  63.             fen[i][j] = 0;
  64.             a[i][j] = 0;
  65.         }
  66.     }
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy
https://ideone.com/3rl3DU
problem MATSUM, based on SPOJ submission 35767168 (CPP14), 2026-05-21 08:32:52
language:
C++14 (gcc 8.3)
created:
11 hours 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!