fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define all(x) x.begin(),x.end()
  8. #define FOR(i,a,b) for(int i = (a), _b = b;i <= _b; i++)
  9. #define FORD(i,a,b) for(int i = (a), _b = b;i >= _b; i--)
  10. #define mp make_pair
  11. #define task "covay"
  12. template<class x,class y>
  13.     bool minimize(x &a,const y &b){
  14.         if(a > b){
  15.             a = b;
  16.             return true;
  17.         }else return false;
  18.     }
  19. template<class x,class y>
  20.     bool maximize(x &a,const y &b){
  21.         if(a < b){
  22.             a = b;
  23.             return true;
  24.         }else return false;
  25.     }
  26. typedef pair<int,int> pii;
  27. constexpr int MAXN=1e6,MOD=1e9+7;
  28. int n,m,k,l,r,ans,res;
  29. struct info{
  30.     char type;
  31.     int la,ra,lb,rb;
  32.     int x,y;
  33. } q[MAXN];
  34. struct Fenwick{
  35.     vector<vector<int>> BIT,pos;
  36.     int n;
  37.     Fenwick (int _n){
  38.         n = _n;
  39.         BIT.assign(n+5,{});
  40.         pos.assign(n+5,{});
  41.     }
  42.     void fakeget(int u,int v){
  43.         int idx = u;
  44.         while(idx > 0){
  45.             pos[idx].pb(v);
  46.             idx -= (idx & -idx);
  47.         }
  48.     }
  49.     void fakeadd(int u,int v){
  50.         int idx = u;
  51.         while(idx <= n){
  52.             pos[idx].pb(v);
  53.             idx += (idx & -idx);
  54.         }
  55.     }
  56.     void compress(){
  57.         FOR(i,1,n){
  58.             sort(all(pos[i]));
  59.             pos[i].erase(unique(all(pos[i])),pos[i].end());
  60.             BIT[i].assign(pos[i].size()+5,0);
  61.         }
  62.     }
  63.     void update(int x,int y){
  64.         for(int u = x;u <= n;u += (u & -u)){
  65.             int v = upper_bound(all(pos[u]),y) - pos[u].begin();
  66.             while(v < BIT[u].size()){
  67.                 BIT[u][v] += 1;
  68.                 v += (v & -v);
  69.             }
  70.         }
  71.     }
  72.     int get(int x,int y){
  73.         int ans = 0;
  74.         for(int u = x;u > 0;u -= (u & -u)){
  75.             int v = upper_bound(all(pos[u]),y) - pos[u].begin();
  76.             while(v > 0){
  77.                 ans += BIT[u][v];
  78.                 v -= (v & -v);
  79.             }
  80.         }
  81.         return ans;
  82.     }
  83.     int qry(int la,int ra,int lb,int rb){
  84.         return get(lb,rb) - get(la-1,rb) - get(lb,ra-1) + get(la-1,ra-1);
  85.     }
  86. };
  87. int32_t main(){
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(0);cout.tie(0);
  90.     if(fopen(task".inp","r")){
  91.         freopen(task".inp","r",stdin);
  92.         freopen(task".out","w",stdout);
  93.     }
  94.     cin >> n;
  95.     vector<int> val;
  96.     FOR(i,1,n){
  97.         cin >> q[i].type;
  98.         if(q[i].type == '+'){
  99.             cin >> q[i].x >> q[i].y;
  100.             val.pb(q[i].x);
  101.             val.pb(q[i].y);
  102.         }else{
  103.             cin >> q[i].la >> q[i].ra >> q[i].lb >> q[i].rb;
  104.             val.pb(q[i].la);
  105.             val.pb(q[i].ra);
  106.             val.pb(q[i].lb);
  107.             val.pb(q[i].rb);
  108.         }
  109.     }
  110.     sort(all(val));
  111.     val.erase(unique(all(val)),val.end());
  112.     FOR(i,1,n){
  113.         if(q[i].type == '+'){
  114.             q[i].x = lower_bound(all(val),q[i].x) - val.begin() + 1;
  115.             q[i].y = lower_bound(all(val),q[i].y) - val.begin() + 1;
  116.         }else{
  117.             q[i].la = lower_bound(all(val),q[i].la) - val.begin() + 1;
  118.             q[i].ra = lower_bound(all(val),q[i].ra) - val.begin() + 1;
  119.             q[i].lb = lower_bound(all(val),q[i].lb) - val.begin() + 1;
  120.             q[i].rb = lower_bound(all(val),q[i].rb) - val.begin() + 1;
  121.         }
  122.     }
  123.     m = val.size();
  124.     Fenwick tree(m);
  125.     FOR(i,1,n){
  126.         if(q[i].type == '+'){
  127.             int x = q[i].x,y = q[i].y;
  128.             tree.fakeadd(x,y);
  129.         }else{
  130.             int x1 = q[i].la,x2 = q[i].lb,y1 = q[i].ra,y2 = q[i].rb;
  131.             tree.fakeget(x2,y2);
  132.             tree.fakeget(x1-1,y2);
  133.             tree.fakeget(x2,y1-1);
  134.             tree.fakeget(x1-1,y1-1);
  135.         }
  136.     }
  137.     tree.compress();
  138.     FOR(i,1,n){
  139.         if(q[i].type == '+'){
  140.             int x = q[i].x,y = q[i].y;
  141.             tree.update(x,y);
  142.         }else{
  143.             int x1 = q[i].la,x2 = q[i].lb,y1 = q[i].ra,y2 = q[i].rb;
  144.             cout << tree.qry(x1,y1,x2,y2) << '\n';
  145.         }
  146.     }
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4Jq1h3
language:
C++14 (gcc 8.3)
created:
8 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!