fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  6. #define MAX 500050
  7.  
  8. #define ll long long
  9. #define ld long double
  10. #define lli long long int
  11.  
  12. #define pb push_back
  13. #define INF 100000000000000
  14. #define mod 1000000007
  15.  
  16. // trignometric function always give value in Radians only
  17. #define PI acos(-1) //3.1415926535897932384626433832795028
  18. #define dsin(degree) sin(degree*(PI/180.0))
  19. #define dcos(degree) cos(degree*(PI/180.0))
  20. #define dtan(degree) tan(degree*(PI/180.0))
  21.  
  22. #define rsin(radian) sin(radian)
  23. #define rcos(radian) cos(radian)
  24. #define rtan(radian) tan(radian)
  25.  
  26. #define counttrailingzeroes(n) __builtin_ctzll(n)
  27. #define countsetbits(n) __builtin_popcountll(n) 
  28.  
  29. #define mem0(a) memset(a,0,sizeof(a))
  30. #define mem1(a) memset(a,-1,sizeof(a))
  31. #define memf(a) memset(a,false,sizeof(a))
  32.  
  33. #define loop(i,n)  for (lli i = 0; i < n; i++)
  34. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  35.  
  36. #define all(v) v.begin(),v.end()
  37. #define rall(v) v.rbegin(),v.rend()
  38. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  39. #define sz(x) int(x.size())
  40. #define F first
  41. #define S second
  42.  
  43. #define mii map<lli,lli>
  44.  
  45. #define pii pair<lli,lli>
  46.  
  47. #define vi vector<lli>
  48. #define vvi vector<vi>
  49. #define vpi vector<pii>
  50. #define vbool vector<bool>
  51.  
  52. #define seti set<lli>
  53.  
  54. #define gcd(a,b) __gcd((a),(b))
  55. #define lcm(a,b) (a/gcd(a,b))*b
  56. #define abs(x) ((x < 0)?-(x):x)
  57. #define isvowel(v) (0x208222>>(v&0x1f))&1
  58.  
  59. #define endl '\n'
  60.  
  61. template <typename Head>
  62. void print(Head&& head)
  63. {
  64.     cout<<head<<endl;
  65. }
  66. template <typename Head, typename... Tail>
  67. void print(Head&& head, Tail... tail)
  68. {
  69.     cout<<head<<" ";
  70.     print(tail...);
  71. }
  72.  
  73. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  74. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  75.  
  76. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  77. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  78.  
  79. #define FD(N) fixed<<setprecision(N)
  80.  
  81. #define deb(x) cout<<#x<<" "<<x<<endl;
  82.  
  83. /*
  84. 1D vector -  vi dp(n,value);
  85. */
  86.  
  87. lli mceil(lli a,lli b){ return(a/b + (a%b != 0)); }
  88.  
  89. lli mfloor(lli a,lli b){ return(a/b); }
  90.  
  91. ll modmul(ll a, ll b,ll MOD = mod) {
  92.     return ((a%MOD) * (b%MOD)) % MOD;
  93. }
  94.  
  95. ll modadd(ll a, ll b,ll MOD = mod){
  96.     return((a%MOD)+(b%MOD)+MOD)%MOD;
  97. }
  98.  
  99. ll modsub(ll a, ll b,ll MOD = mod){
  100.     return((a%MOD) - (b%MOD) + MOD)%MOD;
  101. }
  102.  
  103. lli fastexpo(lli a,lli b ,lli MOD = mod){
  104.     a = a%MOD;
  105.     lli ans=1;
  106.     while(b){
  107.         if(b&1)
  108.             ans=(ans*1ll*a)%MOD;
  109.         a=(a*1ll*a)%MOD;
  110.         b=b/2;
  111.         }
  112.     return ans;
  113.  }
  114.  
  115.  
  116. vector<int>all_div[200001];
  117. void alldivisors(){
  118. for(int i=1;i<=200000;++i){
  119.         for(int j=i;j<=200000;j+=i)
  120.             all_div[j].pb(i);
  121.     }
  122. }
  123.  
  124.  
  125. bool ispower2(lli n){
  126.     return(n and (n&(n-1))==0 );
  127. }
  128. //------------------------------------------------------------------------
  129. // lli BIT[MAX], a[MAX], n;
  130. // void update(lli x , lli val)
  131. // {
  132. //     while(x<=n)
  133. //     {
  134. //         BIT[x] += val;
  135. //         x += (x&-x);
  136. //     }
  137. // }
  138.  
  139. lli BIT1[MAX], BIT2[MAX],BIT3[MAX], BIT4[MAX];
  140. lli a[MAX], n , b[MAX];
  141.  
  142. void update(lli *BIT , lli x , lli val)
  143. {
  144.     while(x<=n)
  145.     {
  146.         BIT[x] += val;
  147.         x += (x&-x);
  148.     }
  149. }
  150.  
  151. void clear(lli n)
  152. {
  153.     loop(i,n)
  154.     {
  155.         BIT1[i]  =BIT2[i] = BIT3[i] = BIT4[i]=0;
  156.     }
  157. }
  158.  
  159. lli query(lli *BIT , lli x)
  160. {
  161.      lli sum = 0;
  162.      while(x>0)
  163.      {
  164.         sum += BIT[x];
  165.         x -= (x&-x);
  166.      }
  167.  
  168.      return sum;
  169. }
  170.  
  171. int main(){
  172. fastio
  173. lli tt =10000;
  174. cin>>tt;
  175. loop(ii,tt)
  176. {
  177.     cout<<"Case #"<<ii+1<<": ";
  178.     lli q,p;
  179.     cin>>n>>q>>p;
  180.     lli a[n+1];
  181.     FOR(i,1,n+1)
  182.     {
  183.         cin>>a[i];
  184.         for(lli s =1;s<=4;s++){
  185.             lli val1 = pow(a[i],s);
  186.             lli val2 = pow(a[i]%p,s);
  187.             lli val = val1-val2;
  188.             lli cnt=0;
  189.             while(val and val%p==0)
  190.             {
  191.                 cnt++;
  192.                 val/=p;
  193.             }
  194.             val = cnt;
  195.             if(s==1)
  196.             {
  197.                 update(BIT1,i,val);
  198.             }
  199.             else if(s==2)
  200.             {
  201.                 update(BIT2,i,val);
  202.             }
  203.             else if(s==3)
  204.             {
  205.                 update(BIT3,i,val);
  206.             }
  207.             else if(s==4)
  208.             {
  209.                 update(BIT4,i,val);
  210.             }
  211.  
  212.         }
  213.  
  214.  
  215.     }
  216.     while(q--)
  217.     {
  218.         lli tp;
  219.         cin>>tp;
  220.         if(tp==1)
  221.         {
  222.             lli pos,vall;
  223.             cin>>pos>>vall;
  224.             for(lli s =1;s<=4;s++){
  225.                 lli val1 = pow(a[pos],s);
  226.                 lli val2 = pow(a[pos]%p,s);
  227.                 lli val = val1-val2;
  228.                 lli cnt=0;
  229.                 while(val and val%p==0)
  230.                 {
  231.                     cnt++;
  232.                     val/=p;
  233.                 }
  234.                 val = cnt;
  235.                 if(s==1)
  236.                 {
  237.                     update(BIT1,pos,-val);
  238.                 }
  239.                 else if(s==2)
  240.                 {
  241.                     update(BIT2,pos,-val);
  242.                 }
  243.                 else if(s==3)
  244.                 {
  245.                     update(BIT3,pos,-val);
  246.                 }
  247.                 else if(s==4)
  248.                 {
  249.                     update(BIT4,pos,-val);
  250.                 }
  251.              }
  252.             a[pos]=vall;
  253.             for(lli s =1;s<=4;s++){
  254.                 lli val1 = pow(a[pos],s);
  255.                 lli val2 = pow(a[pos]%p,s);
  256.                 lli val = val1-val2;
  257.                 lli cnt=0;
  258.                 while(val and val%p==0)
  259.                 {
  260.                     cnt++;
  261.                     val/=p;
  262.                 }
  263.                 val = cnt;
  264.                 if(s==1)
  265.                 {
  266.                     update(BIT1,pos,val);
  267.                 }
  268.                 else if(s==2)
  269.                 {
  270.                     update(BIT2,pos,val);
  271.                 }
  272.                 else if(s==3)
  273.                 {
  274.                     update(BIT3,pos,val);
  275.                 }
  276.                 else if(s==4)
  277.                 {
  278.                     update(BIT4,pos,val);
  279.                 }
  280.              }
  281.         }
  282.         else
  283.         {
  284.             lli s,l,r;
  285.             cin>>s>>l>>r;
  286.  
  287.             lli cnt=0 , sum=0;
  288.             if(s==1)
  289.             {
  290.                 cout<<query(BIT1,r)-query(BIT1,l-1)<<" ";
  291.             }
  292.             else if(s==2)
  293.             {
  294.                 cout<<query(BIT2,r)-query(BIT2,l-1)<<" ";
  295.             }
  296.             else if(s==3)
  297.             {
  298.                 cout<<query(BIT3,r)-query(BIT3,l-1)<<" ";
  299.             }
  300.             else if(s==4)
  301.             {
  302.                 cout<<query(BIT4,r)-query(BIT4,l-1)<<" ";
  303.             }
  304.         }
  305.     }
  306.     cout<<endl;
  307.     clear(n+1);
  308.  
  309. }
  310. return 0;
  311. }
  312.  
  313.  
  314.  
Success #stdin #stdout 0.01s 20060KB
comments (?)
stdin
copy 
2
5 5 2
16 94 62 67 91
2 3 3 4
1 1 69
2 3 1 4
2 1 1 1
2 3 2 2
5 5 5
1 2 3 4 5
2 1 1 5
1 3 98
2 3 2 4
1 5 3
2 2 1 5
stdout
copy 
Case #1: 4 9 2 3 
Case #2: 1 1 1
https://ideone.com/9ukSui
language:
C++14 (gcc 8.3)
created:
2 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!