fork download
copy 
  1. /*/ 
  2.    Author: _Chaitanya1999
  3.    "Everything in this world is magic, except to the magician"
  4. /*/
  5. #include<bits/stdc++.h>
  6. using namespace std;    
  7.  
  8. /*/---------------------------Defines-----------------------------------------/*/
  9.  
  10. #pragma GCC optimize("Ofast") 
  11. #define int long long
  12. #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
  13. #define pb push_back 
  14. #define eb emplace_back
  15. #define fn for(int i =0 ;i <n;i++)  
  16. #define fn1 for( int i =1;i<=n; i++)
  17. #define fm for(int j =0 ;j <m;j++)
  18. #define fm1 for(int j =1;j<=m;j++)
  19. #define fi first
  20. #define se second
  21. #define endl '\n'
  22. #define PI  3.14159265358979323846
  23. #define MOD 1000000007
  24. #define all(a) a.begin(),a.end()
  25. #define rall(a) a.rbegin(),a.rend()
  26. const int N = 2e6+5;    
  27. const int INF = 1e18L;
  28. // for all eight directions
  29. int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  30. int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  31. // for all 4 directions
  32. //int dx[4]={-1,1,0,0};
  33. //int dy[4]={0,0,-1,1};
  34. //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  35. /*/-----------------------------Debug begins----------------------------------/*/
  36. vector<string> split(const string& s, char c) {
  37.   vector<string> v; stringstream ss(s); string x;
  38.   while (getline(ss, x, c)) v.emplace_back(x); return move(v);
  39. }
  40. template<typename T, typename... Args>
  41. inline string arrStr(T arr, int n) {
  42.   stringstream s; s << "[";
  43.   for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
  44.   if(n>0)
  45.   s << arr[n - 1] ;
  46.   s<< "]";
  47.   return s.str();
  48. }
  49. #define trace(args...) {__trace_begin(__LINE__); __trace(split(#args, ',').begin(), args);}
  50. inline void __trace_begin(int line) { cerr << "#" << line << ": "; }
  51. template<typename T> inline void __trace_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
  52. template<typename T> inline void __trace_out_var(T* val) { cerr << arrStr(val, 10); }
  53. template<typename T> inline void __trace_out_var(T val) { cerr << val; }
  54. inline void __trace(vector<string>::iterator it) { cerr << endl; }
  55.  
  56. template<typename T, typename... Args>
  57. inline void __trace(vector<string>::iterator it, T a, Args... args) {
  58.   cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  59.   __trace_out_var(a);
  60.   cerr << "; ";
  61.   __trace(++it, args...);
  62. }
  63. /*/-----------------------------Code begins----------------------------------/*/
  64. int ar[N];
  65. int tree[N];
  66. void build(int l,int r,int tn){
  67.   if(l==r){
  68.     tree[tn] = ar[l];
  69.     return ;
  70.   }
  71.   int mid = (l+r)/2;
  72.   build(l,mid,2*tn+1);
  73.   build(mid+1,r,2*tn+2);
  74.   tree[tn] = min(tree[tn*2+1] , tree[2*tn+2]);
  75. }
  76. int qry(int l,int r,int ql,int qr,int tn){
  77.   if(l > qr || r < ql)return INF;
  78.   else if(l>=ql && r<=qr){
  79.     return tree[tn];
  80.   }
  81.    int mid = (l+r)/2;
  82.   return min(qry(l,mid,ql,qr,2*tn+1),qry(mid+1,r,ql,qr,2*tn+2)); 
  83. }
  84. void update(int pos,int l,int r,int v,int tn){
  85.   if(l==r && pos==l){
  86.     tree[tn] = v;
  87.     ar[l]= v;
  88.     return ;
  89.   }
  90.   int mid=(l+r)/2;
  91.   if(pos>=l && pos<=mid)update(pos,l,mid,v,tn*2+1);
  92.   if(pos>=mid+1&&pos<=r)update(pos,mid+1,r,v,2*tn+2);
  93.   tree[tn] = min(tree[tn*2+1] , tree[2*tn+2]);
  94.  
  95. }
  96. signed main(){
  97.   IOS;
  98.   int T=1;
  99.   // cin >> T;
  100.   while(T--){
  101.     int n,q;
  102.     cin >> n >> q;
  103.     unordered_map<int,vector<int>>mp;
  104.     fn{
  105.       cin >> ar[i];
  106.       mp[ar[i]].pb(i);
  107.     }
  108.     build(0,n-1,0);
  109.     while(q--){
  110.       int t,l,r;
  111.       cin>>t>>l>>r;
  112.       if(t==1){
  113.         int old = ar[l];
  114.         auto it = lower_bound(all(mp[old]),l);
  115.         mp[old].erase(it);
  116.         update(l,0,n-1,r,0);
  117.         auto it2 = lower_bound(all(mp[r]),l);
  118.         mp[r].insert(it2,l);
  119.       }else{
  120.         int mi = qry(0,n-1,l,r-1,0);
  121.         int ans = upper_bound(all(mp[mi]),r-1)-mp[mi].begin();
  122.         ans-=lower_bound(all(mp[mi]),l)-mp[mi].begin();
  123.         cout << mi << " "<< ans <<'\n';
  124.       }
  125.  
  126.     }
  127.   }
  128.   return 0;
  129. }
Success #stdin #stdout 0s 5716KB
comments (?)
stdin
copy 
5 5
3 4 3 5 2
2 0 3
1 1 2
2 0 3
1 0 2
2 0 5
stdout
copy 
3 2
2 1
2 3
https://ideone.com/hZfZJF
language:
C++14 (gcc 8.3)
created:
3 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!