fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define gx getchar_unlocked
  4. #define px putchar_unlocked
  5.  
  6. inline void iscan( int &n )
  7. {
  8.     register int sign = 1; n = 0;
  9.     register char c = gx();
  10.     while( c < '0' || c > '9' ) {
  11.         if( c == '-' ) sign = -1;
  12.         c = gx();
  13.     }
  14.     while( c >= '0' && c <= '9' )
  15.         n = (n<<3) + (n<<1) + c - '0', c = gx();
  16.     n = n * sign;
  17. }
  18.  
  19. inline void lprint( ULL n )
  20. {
  21.     if(n<0) {
  22.         n=-n;
  23.         px('-');
  24.     }
  25.     register int i=64;
  26.     register char o[64];
  27.     do {
  28.         o[--i] = (n%10) + '0';
  29.         n/=10;
  30.     }while(n);
  31.     do {
  32.         px(o[i]);
  33.     }while(++i<64);
  34. }
  35.  
  36. int BIT[501][50001];
  37.  
  38. long long inv[50001];
  39.  
  40. int A[250001];
  41.  
  42. int sq,N;
  43.  
  44. inline void update(int idx)
  45. {
  46.     for(;idx<=50000;)
  47.     {
  48.         ++inv[idx];
  49.         idx+=idx&-idx;
  50.     }
  51.     return ;
  52. }
  53.  
  54. inline long long Get(int idx)
  55. {
  56.     long long sum=0;
  57.     for(;idx>0;)
  58.     {
  59.         sum+=inv[idx];
  60.         idx-=idx&-idx;
  61.     }
  62.     return sum;
  63. }
  64.  
  65. inline void update(int number,int idx,int value)
  66. {
  67.     for(;idx<=50000;)
  68.     {
  69.         BIT[number][idx]+=value;
  70.         idx+=idx&-idx;
  71.     }
  72.     return ;
  73. }
  74. inline int Get(int idx , int number)
  75. {
  76.     int sum=0;
  77.     for(;idx>0;)
  78.     {
  79.         sum+=BIT[number][idx];
  80.         idx-=idx&-idx;
  81.     }
  82.     return sum;
  83. }
  84.  
  85. inline long long changeL(int L, int value)
  86. {
  87.         long long change=0;
  88.         const int ped=L/sq+1;
  89.         for(int tree=1;tree<=((N-1)/sq+1);++tree)
  90.             if(tree==ped)
  91.                 continue;
  92.             else if (tree<ped)
  93.                     change=change+(Get(50000,tree)-Get(value,tree))-(Get(50000,tree)-Get(A[L],tree));
  94.             else
  95.                     change=change+Get(value-1,tree)-Get(A[L]-1,tree);
  96.  
  97.         update(ped,A[L],-1);
  98.         update(ped,value,+1);
  99.         for(int i=(ped-1)*sq;i<L;++i)
  100.         {
  101.             if(A[i]>A[L])
  102.                 --change;
  103.             if(value<A[i])
  104.                 ++change;
  105.         }
  106.         for(int i=L+1;i%sq!=0;++i)
  107.         {
  108.             if(A[i]<A[L])
  109.                 --change;
  110.             if(value>A[i])
  111.                 ++change;
  112.         }
  113.         return change;
  114. }
  115. int main()
  116. {
  117.     int i,M,L,R;
  118.     iscan(N);
  119.     sq=sqrt(N);
  120.     long long ans=0;
  121.     int tree_num=0;
  122.     for(i=0;i<N;++i)
  123.         {
  124.             if(i%sq==0)
  125.                 tree_num++;
  126.             iscan(A[i]);
  127.             update(tree_num,A[i],+1);
  128.         }
  129.     for(i=N-1;i>=0;--i)
  130.         {
  131.                 ans+=Get(A[i]-1);
  132.                 update(A[i]);
  133.         }
  134.     iscan(M);
  135.     for(i=0;i<M;++i)
  136.     {
  137.         iscan(L);iscan(R);
  138.         ans+=changeL(L-1,R);
  139.         A[L-1]=R;
  140.         lprint(ans);
  141.         px('\n');
  142.     }
  143.     return 0;
  144. }
  145.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:19:21: error: variable or field 'lprint' declared void
 inline void lprint( ULL n )
                     ^
prog.cpp:19:21: error: 'ULL' was not declared in this scope
stdout
copy 
Standard output is empty
https://ideone.com/gzgzgH
language:
C++14 (gcc 8.3)
created:
9 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!