fork download
copy 
  1. ///////////////////////////////////////////
  2. // it is what it is //                   //
  3. // it is what it is //                   //
  4. ///////////////////////////////////////////
  5. #include <bits/stdc++.h>
  6. #include <iostream>
  7. #define int long long
  8. #define ll long long
  9. #define fast cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
  10. #define all(x) x.begin(),x.end()
  11. #define alr(x) x.rbegin(),x.rend()
  12. #define endl '\n'
  13. #define emb emplace_back
  14. #define F first
  15. #define S second
  16. #define yes cout << "YES\n"
  17. #define no cout <<"NO\n"
  18. #define pii pair< int , char>
  19. #define PI acos(-1.0)
  20. #define sz(x) x.size()
  21. using namespace std;
  22. int const mod = 1e9+7, N = 2e5 + 100;
  23. map<int , int>mp;
  24. struct segtree
  25. {
  26.     int sz = 1;
  27.     vector< set<int> >tree;
  28.     set<int> NUl;
  29.     set<int> merge( set<int> a ,  set<int> b)
  30.     {
  31.         set< int > s (a.begin() , a.end());
  32.         for(auto x : b)s.insert(x);
  33.         return s;
  34.     }
  35.  
  36.     void init( int n )
  37.     {
  38.         while(sz < n) sz *= 2;
  39.         tree.resize(2 * sz );
  40.     }
  41.     void build(vector<int> &a , int x , int lx , int rx)
  42.     {
  43.         if(rx - lx == 1)
  44.         {
  45.             if(lx < (int)a.size() )tree[x].insert(a[lx]);
  46.             return;
  47.         }
  48.         int mid = (lx + rx)/2;
  49.         build(a , 2 * x + 1 , lx , mid );
  50.         build(a , 2 * x + 2 , mid , rx );
  51.         tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
  52.  
  53.     }
  54.     void build(vector<int> &a)
  55.     {
  56.         build(a , 0 , 0 , sz );
  57.     }
  58.     void updt(int i , int v , int x , int lx , int rx)
  59.     {
  60.         if(rx - lx == 1)
  61.         {
  62.             tree[x].clear();
  63.             tree[x].insert(v);
  64.             return;
  65.         }
  66.         int mid = (lx + rx)/2;
  67.         if( i < mid )
  68.         {
  69.             updt( i , v , 2 * x + 1 , lx , mid);
  70.         }
  71.         else
  72.         {
  73.             updt( i , v , 2 * x + 2 , mid , rx);
  74.         }
  75.         tree[x] = merge(tree[2 * x + 1],tree[2 * x + 2]);
  76.     }
  77.     void updt( int i , int v )
  78.     {
  79.         updt(i , v , 0 , 0 , sz);
  80.     }
  81.     set <int> get(int l , int r , int x , int lx , int rx)
  82.     {
  83.         if(lx >= r || rx <= l)return NUl;
  84.         if( lx >= l && rx <= r)return tree[x];
  85.         int mid = (lx + rx)/2;
  86.         set<int> ret1 = get(l , r , 2 * x + 1 , lx , mid);
  87.         set<int> ret2 = get(l , r , 2 * x + 2 , mid ,rx);
  88.         return merge(ret1 , ret2);
  89.     }
  90.     set <int> get(int l , int r)
  91.     {
  92.         return get(l , r , 0 , 0 , sz);
  93.     }
  94.  
  95. };
  96. void solve()
  97. {
  98.     int n , q; cin  >> n >> q;
  99.     vector<int>a(n);
  100.     for(int i = 0 ; i < n ;i ++)
  101.     {
  102.         cin >> a[i];
  103.     }
  104.     segtree st;
  105.     st.init(n+1);
  106.     st.build(a);
  107.     while(q--)
  108.     {
  109.         int t , i ,v;
  110.         cin >> t >> i >> v;
  111.         if(t == 1)
  112.         {
  113.             cout << st.get(i-1,v).size() << endl;
  114.         }
  115.         else
  116.         {
  117.             st.updt(i-1,v);
  118.         }
  119.     }
  120.  
  121.  
  122.  
  123. }
  124. int32_t main()
  125. {
  126.     fast;
  127.     //freopen("","r",stdin);
  128.     //freopen("","w",stdout);
  129.     int test = 1;
  130.     //cin >> test;
  131.     while(test--)
  132.     {
  133.        solve();
  134.     }
  135. }
  136.  
  137. ////////////////////////////////////////////////////
  138. //bool isPrime(ll n)
  139. //{
  140. //    if (n <= 1)return false;
  141. //    if (n <= 3)return   true;
  142. //    if (n % 2 == 0||n % 3 == 0)return false;
  143. //    for (ll i = 5; i * i <= n; i = i + 6)
  144. //        if (n % i == 0||n % (i + 2) == 0)return false;
  145. //    return true;
  146. //}
  147. //
  148. /////////////////////////////////////////////////////
  149. //
  150. /////////////////////////////////////////////////////
  151. //ll GCD(ll  a,ll  b )
  152. //{
  153. //    return b ? GCD(b, a % b ) : a ;
  154. //}
  155. /////////////////////////////////////////////////////
  156. //ll LCM(ll a, ll b)
  157. //{
  158. //    return (a / GCD(a, b)) * b;
  159. //}
  160.  
  161. //ll  po(ll  x, ll os)
  162. //{
  163. //    if( os == 0 )
  164. //        return 1;
  165. //    ll z = po(x,os/2);
  166. //    if( os&1 )
  167. //        return z*z%mod*x%mod;
  168. //
  169. //    return z*z%mod;
  170. //}
  171. ////////////////////////////////////////////////////
  172. //ll exEuclid(ll a, ll b, ll& x, ll& y)
  173. //{
  174. //    if (b==0)
  175. //    {
  176. //        x=1;
  177. //        y=0;
  178. //        return a;
  179. //    }
  180. //    ll x1,y1;
  181. //    ll d=exEuclid(b,a%b,x1,y1);
  182. //    x=y1;
  183. //    y=x1-y1*(a/b);
  184. //    return d;
  185. //}
  186. /////////////////////////////////////////////////////////
  187. //bool cmp(const pair<int, int>& a, const pair<int, int>& b)
  188. //{
  189. //    if (a.first != b.first)return a.first > b.first;
  190. //    return a.second > b.second;
  191. //}
  192. /////////////////////////////////////////////////////////
  193. ///// indexed set
  194. /////#include <ext/pb_ds/assoc_container.hpp>
  195. /////#include <ext/pb_ds/tree_policy.hpp>
  196. /////#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  197. /////using namespace __gnu_pbds;
  198. /////////////////////////////////////////////////////////
  199. //int  po(int  x, int os)
  200. //{
  201. //    if( os == 0 )
  202. //        return 1;
  203. //    ll z = po(x,os/2);
  204. //    if( os&1 )
  205. //        return z*z*x;
  206. //
  207. //    return z*z;
  208. //}
  209. //int mod_inverse(int x)
  210. //{
  211. //    return po(x, mod-2);
  212. //}
  213. ////////////////////////////////////////////////////
  214.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
7 6
1 2 3 6 5 4 19
1 1 3
1 2 5
1 2 4
2 2 8
1 1 6
1 1 3
stdout
copy 
3
4
3
6
3
https://ideone.com/664TMY
language:
C++ (gcc 8.3)
created:
84 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!