fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<int , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<int , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const int INF = 1e7;
  21. const long long MOD = 1e9 + 7;
  22. const int N = 2e5 + 7;
  23. int n , m , q;
  24. long long t[8 * N];
  25. int Cnt[2 * N];
  26. bool col[2 * N];
  27.  
  28. struct gv{
  29.     long long x , y;
  30.     int id;
  31. };
  32.  
  33. gv a[N];
  34.  
  35. struct Cand{
  36.     int type;
  37.     long long r1 , c1 , r2 , c2;
  38.     int id;
  39. };
  40.  
  41. vector<Cand> cand;
  42.  
  43. void nen(){
  44.     vector<pair<long long , long long>> v2;
  45.     vector<long long> v1;
  46.     for (gv &C : a){
  47.         v1.push_back(C.x);
  48.         v2.push_back({C.x , C.y});
  49.     }
  50.     for (Cand &C : cand) if (C.type == 1){
  51.         v1.push_back(C.r1);
  52.         v2.push_back({C.r1 , C.c1});
  53.     }
  54.  
  55.     sort(v1.begin() , v1.end());
  56.     sort(v2.begin() , v2.end());
  57.  
  58.     v1.erase(unique(v1.begin() , v1.end()));
  59.     v2.erase(unique(v2.begin() , v2.end()));
  60.  
  61.     for (gv &C : a){
  62.         int tmp = lower_bound(v2.begin() , v2.end() , (pair<long long , long long>){C.x , C.y}) - v2.begin();
  63.         C.x = lower_bound(v1.begin() , v1.end() , C.x) - v1.begin() + 1;
  64.         C.id = tmp;
  65.     }
  66.  
  67.     for (Cand &C : cand){
  68.         if (C.type & 1){
  69.             int tmp = lower_bound(v2.begin() , v2.end() , (pair<long long , long long>){C.r1 , C.c1}) - v2.begin();
  70.             C.r1 = lower_bound(v1.begin() , v1.end() , C.r1) - v1.begin() + 1;
  71.             C.id = tmp;
  72.         }
  73.         else{
  74.             C.r1 = lower_bound(v1.begin() , v1.end() , C.r1) - v1.begin() + 1;
  75.             C.r2 = lower_bound(v1.begin() , v1.end() , C.r2) - v1.begin() + 1;
  76.         }
  77.     }
  78.  
  79.     m = v1.size();
  80. }
  81.  
  82. void inp(){
  83.     cin >> n >> q;
  84.     for (int i = 1 ; i <= n ; ++i){
  85.         cin >> a[i].x >> a[i].y;
  86.     }
  87.  
  88.     for (int i = 1 ; i <= q ; ++i){
  89.         int type;
  90.         cin >> type;
  91.         if (type & 1){
  92.             long long r1 , c1;
  93.             cin >> r1 >> c1;
  94.             cand.push_back({type , r1 , c1 , 0 , 0 , 0});
  95.         }
  96.         else{
  97.             long long r1 , c1 , r2 , c2;
  98.             cin >> r1 >> c1 >> r2 >> c2;
  99.             cand.push_back({type , r1 , c1 , r2 , c2 , 0});
  100.         }
  101.     }
  102.  
  103.     nen();
  104. }
  105.  
  106. void update(int id , int l , int r , int pos , long long val){
  107.     if (l > pos || r < pos) return;
  108.     if (l == r){
  109.         t[id] = val;
  110.         t[id] %= MOD;
  111.         return;
  112.     }
  113.  
  114.     int mid = (l + r) >> 1;
  115.     update(id << 1 , l , mid , pos , val);
  116.     update(id << 1 | 1 , mid + 1 , r , pos , val);
  117.     t[id] = t[id << 1] * t[id << 1 | 1];
  118.     t[id] %= MOD;
  119. }
  120.  
  121. long long get(int id , int l , int r , int u , int v){
  122.     if (u > v) return 0;
  123.     if (u == v) return 1;
  124.     if (l > v || r < u) return 1;
  125.     if (u <= l && r <= v) return t[id];
  126.  
  127.     int mid = (l + r) >> 1;
  128.     long long t1 = get(id << 1 , l , mid , u , v);
  129.     long long t2 = get(id << 1 | 1 , mid + 1 , r , u , v);
  130.  
  131.     return t1 * t2 % MOD;
  132. }
  133.  
  134. void solve(){
  135.     for (gv &C : a){
  136.         update(1 , 1 , m , C.x , 1);
  137.         col[C.id] = 1;
  138.         ++Cnt[C.x];
  139.     }
  140.  
  141.     for (Cand &C : cand){
  142.         if (C.type & 1){
  143.             if (col[C.id]){
  144.                 col[C.id] = 0;
  145.                 --Cnt[C.r1];
  146.                 update(1 , 1 , m , C.r1 , Cnt[C.r1]);
  147.             }
  148.             else{
  149.                 col[C.id] = 1;
  150.                 ++Cnt[C.r1];
  151.                 update(1 , 1 , m , C.r1 , Cnt[C.r1]);
  152.             }
  153.         }
  154.         else{
  155.             cout << get(1 , 1 , m , C.r1 , C.r2) << '\n';
  156.         }
  157.     }
  158. }
  159.  
  160. int main(){
  161. //    freopen("difmax.inp" , "r" , stdin);
  162. //    freopen("difmax.out" , "w" , stdout);
  163.     faster;
  164.     inp();
  165.     solve();
  166.     return 0;
  167. }
  168.  
Success #stdin #stdout 0.07s 12820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cF0nIe
language:
C++14 (gcc 8.3)
created:
7 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!