fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6.  
  7. " when you are not practicing someone else is ,
  8.  and the day u meet them u will lose "
  9.  
  10. */
  11. #include<bits/stdc++.h>
  12. #include<stdio.h>
  13. using namespace std;
  14.  
  15. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  16. #define MAX 100050
  17.  
  18. #define ll long long
  19. #define ld long double
  20. #define lli int
  21.  
  22. #define pb push_back
  23. #define INF 1000000000000
  24. #define mod 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define mem0(a) memset(a,0,sizeof(a))
  37. #define mem1(a) memset(a,-1,sizeof(a))
  38. #define memf(a) memset(a,false,sizeof(a))
  39.  
  40. #define loop(i,n)  for (lli i = 0; i < n; i++)
  41. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  42.  
  43. #define all(v) v.begin(),v.end()
  44. #define rall(v) v.rbegin(),v.rend()
  45. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  46. #define sz(x) int(x.size())
  47. #define F first
  48. #define S second
  49.  
  50. #define mii map<lli,lli>
  51.  
  52. #define pii pair<lli,lli>
  53.  
  54. #define vi vector<lli>
  55. #define vvi vector<vi>
  56. #define vpi vector<pii>
  57. #define vbool vector<bool>
  58.  
  59. #define seti set<lli>
  60.  
  61. #define gcd(a,b) __gcd((a),(b))
  62. #define lcm(a,b) (a/gcd(a,b))*b
  63. #define abs(x) ((x < 0)?-(x):x)
  64.  
  65. #define endl '\n'
  66.  
  67. template <typename Head>
  68. void print(Head&& head)
  69. {
  70.     cout<<head<<endl;
  71. }
  72. template <typename Head, typename... Tail>
  73. void print(Head&& head, Tail... tail)
  74. {
  75.     cout<<head<<" ";
  76.     print(tail...);
  77. }
  78.  
  79. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  80. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  81.  
  82. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  83. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  84.  
  85. #define FD(N) fixed<<setprecision(N)
  86.  
  87. #define deb(x) cout<<#x<<" "<<x<<endl;
  88.  
  89. /*
  90. 1D vector -  vi dp(n,value);
  91. 2D vector -  vvi dp(n,vi(n,value));
  92. */
  93.  
  94. // chandan1,2
  95. void chandan1(){int y=1;return;}
  96. void chandan2(){
  97.         loop(i,10){
  98.         lli x=1;
  99.     }
  100.     return(chandan1());
  101. }
  102.  
  103. //-------------------------------------------------MO's ALGO (with update) ---------------------------------------------------------------
  104.  
  105.  
  106. const int blk_sz = 500; // u can take sqrt(n) too 
  107.  
  108. typedef struct query
  109. {
  110.     lli l , r , q_time , id;
  111.     query(lli L , lli R , lli Q_time , lli ID)
  112.     {
  113.         l = L;
  114.         r = R;
  115.         q_time = Q_time;
  116.         id = ID;
  117.     }
  118. }query;
  119.  
  120.  
  121.  
  122. typedef struct update
  123. {
  124.     lli ind , prev_val , new_val;
  125.     update(lli Ind , lli Prev_val , lli New_val)
  126.     {
  127.         ind = Ind;
  128.         prev_val = Prev_val;
  129.         new_val = New_val;
  130.     }
  131. }update;
  132.  
  133. bool cmp(query a , query b)
  134. {
  135.     lli blk_num_a_l = a.l / blk_sz;
  136.     lli blk_num_b_l = b.l / blk_sz;
  137.  
  138.     if(blk_num_a_l != blk_num_b_l)
  139.         return(blk_num_a_l < blk_num_b_l);
  140.  
  141.     lli blk_num_a_r = a.r / blk_sz;
  142.     lli blk_num_b_r = b.r / blk_sz;
  143.  
  144.     if(blk_num_a_r != blk_num_b_r)
  145.         return(blk_num_a_r < blk_num_b_r);
  146.  
  147.     return(a.q_time < b.q_time);
  148. }
  149.  
  150.  
  151. lli a[MAX] , cnt=0 , total = 0;
  152. unordered_map<lli,lli> freq;
  153. vector<query> q;
  154. vector<update> upd;
  155.  
  156.  
  157. void add(lli pos)
  158. {
  159.     freq[a[pos]]++;
  160.     if((freq[a[pos]] == 1) and (a[pos]%3==0))
  161.         total += a[pos];
  162. }
  163.  
  164. void remove(lli pos)
  165. {
  166.     freq[a[pos]]--;
  167.     if((freq[a[pos]] == 0) and (a[pos]%3==0))
  168.         total -= a[pos];
  169. }
  170.  
  171.  
  172.  
  173.  
  174. //------------------------------------------------- MO's ALGO (with update) ---------------------------------------------------------------
  175.  
  176. lli ML = 0 , MR = -1;
  177.  
  178. void updo(lli pos)
  179. {
  180.     lli new_val = upd[pos].new_val;
  181.     lli index = upd[pos].ind;
  182.  
  183.     if((index >= ML) and (index <= MR) ) remove(index);
  184.  
  185.     a[index] = new_val;
  186.  
  187.     if((index >= ML) and (index <= MR) ) add(index);
  188.  
  189.  
  190. }
  191.  
  192. void undo(lli pos)
  193. {
  194.     lli prev_val = upd[pos].prev_val;
  195.     lli index = upd[pos].ind;
  196.  
  197.     if((index >= ML) and (index <= MR) ) remove(index);
  198.  
  199.     a[index] = prev_val;
  200.  
  201.     if((index >= ML) and (index <= MR) ) add(index);
  202. }
  203.  
  204. int main(){
  205. fastio
  206. lli t=1;
  207. //cin>>t;
  208. chandan2();
  209. while(t--) {
  210.     lli n,m;
  211.     cin>>n>>m;
  212.     loop(i,n)
  213.         cin>>a[i];
  214.  
  215.  
  216.     lli updates = 0;
  217.     loop(i,m)
  218.     {
  219.         lli type;
  220.         cin>>type;
  221.         if(type == 0) //update query
  222.         {
  223.             lli ind , val;
  224.             cin>>ind>>val;
  225.             ind--;
  226.             updates++;
  227.             upd.pb({ind , a[ind] , val}); //index , prev_val , new_val;
  228.         }
  229.         else // ask query
  230.         {
  231.            lli l , r;
  232.            cin>>l>>r;
  233.             --l,--r;
  234.             q.pb({l,r,updates,i}); 
  235.         }
  236.  
  237.     }
  238.  
  239.     sort(all(q),cmp);
  240.  
  241.     lli ans[m];
  242.     mem1(ans);
  243.  
  244.     lli cr_time = 0;
  245.  
  246.     for(auto xt : q)
  247.     {
  248.         lli l =xt.l;
  249.         lli r = xt.r;
  250.         lli qt = xt.q_time; // how many updates till this query ?
  251.         lli id = xt.id;
  252.  
  253.        // print(l,r,qt,id);
  254.  
  255.         while(cr_time < qt)
  256.         {
  257.             updo(cr_time);
  258.             cr_time++;
  259.         }
  260.  
  261.         while(cr_time > qt)
  262.         {
  263.             cr_time--;
  264.             undo(cr_time);
  265.         }
  266.  
  267.         // STANDARD MO - 
  268.  
  269.         while(MR < r)
  270.         {
  271.             MR++;
  272.             add(MR);
  273.         }
  274.  
  275.         while(MR > r)
  276.         {
  277.             remove(MR);
  278.             MR--;
  279.         }
  280.  
  281.  
  282.         while(ML < l)
  283.         {
  284.             remove(ML);
  285.             ML++;
  286.         }
  287.  
  288.         while(ML > l)
  289.         {
  290.             ML--;
  291.             add(ML);
  292.         }
  293.  
  294.         ans[id] = total;
  295.     }
  296.  
  297.     loop(i,m)
  298.     {
  299.         if(ans[i]!= -1)
  300.             print(ans[i]);
  301.     }
  302.   }
  303. return 0;
  304. }
  305.  
  306. //https://t...content-available-to-author-only...h.co/p/distinct-dishting
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
5 3
1 2 3 9 1
1 1 5
0 3 9
1 1 5
stdout
copy 
12
9
https://ideone.com/rhQRQI
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!