fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll lim=1e5;
  5. ll n,m,k;
  6. vector<vector<ll>> pos,BIT;
  7. vector<ll> posx;
  8. map<pair<ll,ll>,ll> mp;
  9. struct{
  10.     char type;
  11.     ll x,y,x1,y1,val;
  12. }LK[lim];
  13. inline ll U(ll u){
  14.     return lower_bound(posx.begin(),posx.end(),u)-posx.begin();
  15. }
  16. inline ll V(ll u,ll i){
  17.     return lower_bound(pos[i].begin(),pos[i].end(),u)-pos[i].begin();
  18. }
  19. inline void fakeadd(ll u,ll v){
  20.     u=U(u);
  21.     for (;u<pos.size();u+=u&-u)
  22.         pos[u].push_back(v);
  23. }
  24. inline void fakequery(ll u,ll v){
  25.     u=U(u);
  26.     for (;u>0;u-=u&-u)
  27.         pos[u].push_back(v);
  28. }
  29. inline void fakegetquery(ll x,ll y,ll x1,ll y1){
  30.     fakequery(x1,y1);
  31.     fakequery(x-1,y1);
  32.     fakequery(x1,y-1);
  33.     fakequery(x-1,y-1);
  34. }
  35. void setup(){
  36.     for (ll i=1;i<=k;i++){
  37.         cin>>LK[i].type;
  38.         if (LK[i].type=='S'){
  39.             cin>>LK[i].x>>LK[i].y>>LK[i].val;
  40.             posx.push_back(LK[i].x);
  41.         }
  42.         else{
  43.             cin>>LK[i].x>>LK[i].y>>LK[i].x1>>LK[i].y1;
  44.             posx.push_back(LK[i].x-1);
  45.             posx.push_back(LK[i].x1);
  46.         }
  47.     }
  48.     posx.push_back(-1);
  49.     sort(posx.begin(),posx.end());
  50.     posx.erase(unique(posx.begin(),posx.end()),posx.end());
  51.     BIT.resize(posx.size(),{});
  52.     pos.resize(posx.size(),{});
  53.     for (ll i=1;i<=k;i++){
  54.         if (LK[i].type=='S') fakeadd(LK[i].x,LK[i].y);
  55.         else fakegetquery(LK[i].x,LK[i].y,LK[i].x1,LK[i].y1);
  56.     }
  57.     for (ll i=1;i<pos.size();i++){
  58.         pos[i].push_back(-1);
  59.         sort(pos[i].begin(),pos[i].end());
  60.         pos[i].erase(unique(pos[i].begin(),pos[i].end()),pos[i].end());
  61.         BIT[i].resize(pos[i].size(),0);
  62.     }
  63. }
  64. inline void update(ll u,ll v,ll val){
  65.     u=U(u);
  66.     for (ll i=u;i<pos.size();i+=i&-i)
  67.         for (ll j=V(v,i);j<pos[i].size();j+=j&-j)
  68.             BIT[i][j]+=val;
  69. }
  70.  
  71. inline ll get(ll u,ll v){
  72.     ll res=0;
  73.     u=U(u);
  74.     for (ll i=u;i>0;i-=i&-i)
  75.         for (ll j=V(v,i);j>0;j-=j&-j)
  76.             res+=BIT[i][j];
  77.     return res;
  78. }
  79. inline ll query(ll x1,ll y1,ll x2,ll y2){
  80.     return (get(x2,y2)-get(x2,y1-1)-get(x1-1,y2)+get(x1-1,y1-1));
  81. }
  82. int main(){
  83.     cin.tie(nullptr)->sync_with_stdio(0);
  84.     #define F "query"
  85.     if (ifstream(F".inp")){
  86.         freopen(F".inp","r",stdin);
  87.         freopen(F".out","w",stdout);
  88.     }
  89.     cin>>n>>m>>k;
  90.     setup();
  91.     for (ll i=1;i<=k;i++){
  92.         if(LK[i].type=='S'){
  93.             if (mp.count({LK[i].x,LK[i].y}))
  94.                 LK[i].val-=mp[{LK[i].x,LK[i].y}];
  95.             update(LK[i].x,LK[i].y,LK[i].val);
  96.             mp[{LK[i].x,LK[i].y}]+=LK[i].val;
  97.         }
  98.         else{
  99.             cout<<query(LK[i].x,LK[i].y,LK[i].x1,LK[i].y1)<<"\n";
  100.         }
  101.     }
  102.     return 0;
  103. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ceh7nL
language:
C++14 (gcc 8.3)
created:
3 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!