fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define tag "spoj"
  4. #define maxn 1003
  5. #define maxc 207
  6. #define oo 1000000007
  7. #define mid ((l+r)>>1)
  8. #define meset(a,x) memset(a,x,sizeof(a))
  9. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  10. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  11.  
  12. struct BIT2D{
  13.  
  14.     int m,n;
  15.     vector< vector<int> > bit;
  16.  
  17.     BIT2D(const int &M,const int &N): m(M), n(N), bit(M+1,vector<int>(N+1)) {};
  18.  
  19.     void update(int x,int y,const int &val)
  20.     {
  21.         for(;x<=m;x+=x&-x)
  22.             for(int _y=y;_y<=n;_y+=_y&-_y)
  23.                 bit[x][_y]+=val;
  24.     }
  25.  
  26.     int getsum(int x,int y)
  27.     {
  28.         int rep=0;
  29.  
  30.         for(;x>0;x-=x&-x)
  31.             for(int _y=y;_y>0;_y-=_y&-_y)
  32.                 rep+=bit[x][_y];
  33.         return rep;
  34.     }
  35.  
  36.     int sum(const int &x,const int &y,const int &u,const int &v)
  37.     {
  38.         return (getsum(u,v)-getsum(u,y-1)-getsum(x-1,v)+getsum(x-1,y-1));
  39.     }
  40. };
  41.  
  42. struct miniBIT2D{
  43.  
  44.     int m,n;
  45.     vector< vector<int> > node;
  46.     vector< vector<int> > bit;
  47.  
  48.     miniBIT2D(const int &M,const int &N): m(M), n(N), node(M+1), bit(M+1) {};
  49.  
  50.     void fakeup(int x,int y)
  51.     {
  52.         for(;x<=m;x+=x&-x)
  53.                 node[x].push_back(y);
  54.     }
  55.  
  56.     void fakeget(int x,int y)
  57.     {
  58.         for(;x>0;x-=x&-x)
  59.             node[x].push_back(y);
  60.     }
  61.  
  62.     void fake()
  63.     {
  64.         for(int i=1;i<=m;i++)
  65.             sort(node[i].begin(),node[i].end()),
  66.             bit[i].resize(node[i].size()+7);
  67.     }
  68.  
  69.     void update(int x,int y,const int &val)
  70.     {
  71.         for(;x<=m;x+=x&-x)
  72.             for(int _y=lower_bound(node[x].begin(),node[x].end(),y)-node[x].begin()+1;_y<=node[x].size();_y+=_y&-_y)
  73.                 bit[x][_y]+=val;
  74.     }
  75.  
  76.     int getsum(int x,int y)
  77.     {
  78.         int rep=0;
  79.  
  80.         for(;x>0;x-=x&-x)
  81.             for(int _y=upper_bound(node[x].begin(),node[x].end(),y)-node[x].begin();_y>0;_y-=_y&-_y)
  82.                 rep+=bit[x][_y];
  83.         return rep;
  84.     }
  85.  
  86.     int sum(const int &x,const int &y,const int &u,const int &v)
  87.     {
  88.         return (getsum(u,v)-getsum(u,y-1)-getsum(x-1,v)+getsum(x-1,y-1));
  89.     }
  90. };
  91.  
  92. struct query{
  93.     int val;
  94.     int x,y,u,v;
  95. };
  96. int main()
  97. {
  98.     #ifdef dmdd
  99.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  100.     #endif // dmdd
  101.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  102.  
  103.     int m,n;
  104.  
  105.     ///bit:
  106.     cin>>m>>n;
  107.     BIT2D bit(m,n);
  108.  
  109.     for(int i=1,v;i<=m;i++)
  110.         for(int j=1;j<=n;j++)
  111.             cin>>v,bit.update(i,j,v);
  112.  
  113.     int q,x,y,u,v;
  114.     cin>>q;
  115.     while(q-->0) cin>>x>>y>>u>>v,cout<<bit.sum(x,y,u,v)<<"\n";
  116.  
  117.     cout<<"-------------\n";
  118.     ///mini:
  119.     cin>>m>>n;
  120.     vector<query> up,get;
  121.     miniBIT2D bitt(m,n);
  122.  
  123.     for(int i=1,v;i<=m;i++)
  124.         for(int j=1;j<=n;j++)
  125.             cin>>v,bitt.fakeup(i,j),up.push_back({v,i,j,0,0});
  126.  
  127.     cin>>q;
  128.     while(q-->0)
  129.     {
  130.         cin>>x>>y>>u>>v;
  131.         bitt.fakeget(x-1,y-1);
  132.         bitt.fakeget(x-1,v);
  133.         bitt.fakeget(u,y-1);
  134.         bitt.fakeget(u,v);
  135.         get.push_back({0,x,y,u,v});
  136.  
  137.     }
  138.  
  139.     bitt.fake();
  140.  
  141.     for(const auto &que: up) bitt.update(que.x,que.y,que.val);
  142.     for(const auto &que: get) cout<<bitt.sum(que.x,que.y,que.u,que.v)<<"\n";
  143.  
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
4 5
1 -2 9 0 1222
2 32 1 1 21
2 2  2 2 122
3 10 4 17 -1000007

7
1 3 4 4
1 2 3 4
1 3 3 4
2 2 3 3
1 1 2 4
2 2 4 4
4 5 4 5

4 5
1 -2 9 0 1222
2 32 1 1 21
2 2  2 2 122
3 10 4 17 -1000007

7
1 3 4 4
1 2 3 4
1 3 3 4
2 2 3 3
1 1 2 4
2 2 4 4
4 5 4 5
stdout 
36
47
15
37
44
71
-1000007
-------------
36
47
15
37
44
71
-1000007
https://ideone.com/m4o7uS
language:
C++14 (gcc 8.3)
created:
6 years 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!