Counting Inversions.

You are given a sequence A of N (N≤250000) integers between 1 and 50000. On this sequence you have to apply M (M≤10000) operations of the form: modify the i-th element in the sequence and then say how many inversions are there in the sequence. The number of inversions in a sequence is given by the number of pairs (i,j) with i < j and Ai > Aj.

straight-forward algorithm: using a inteval tree with a binary indexed tree in each node and maintaining such a structure.

as the memory usage will be too large if we store all the N^2 possible intervals, we just split it into larger intervals and if a interval is smaller than a specific number, then stop processing its sub-intervals. when it's neccessary to query such small intervals, use brute force way to calculate.

really slow and takes lots of memory though, no wonder it's a straight-forward way.

#include <stdio.h>
#include <math.h>
#include <cstring>
using namespace std;

const int maxn=250010;
const int maxr=50010;
const int treesize=520*2;
int size;
long long ans;
int limit;
int tree[treesize][maxr];
int nk[treesize];
int dt[maxn];
int n,m;


             inline int lowbit(int x){ return x & (-x);}
            
             inline void update(int seg,int nd,int dt){
                    while (nd<maxr){
                          tree[seg][nd]+=dt;
                          nd+=lowbit(nd);
                          }
                    }
                   
             inline int sum(int seg,int nd){
                    int ans=0;
                    while (nd>0){
                          ans+=tree[seg][nd];
                          nd-=lowbit(nd);
                          }
                    return ans;
                    }
                   
             void make_tree(int nd,int l,int r){
                  //size = size>nd?size:nd;
                  if (r-l>limit){
                                int m = (l+r)>>1;
                                make_tree(nd*2,l,m);
                                make_tree(nd*2+1,m+1,r);
                  }
                  else nk[nd]=1;
                  }
                 
             void modify(int nd,int l,int r,int des,int x,int y){
                  if (x!=0)
                        update(nd,x,-1);
                  update(nd,y,1);
                  if (nk[nd]==0){
                     int m=(l+r)>>1;
                     if (des>m)
                        modify(nd*2+1,m+1,r,des,x,y);
                     else modify(nd*2,l,m,des,x,y);
                  }
                  }
                 
             int getnum(int nd,int l,int r,int s,int t,int x,int y){
                 if (s>n||y<1)return 0;
                  if (s==l&&t==r){
                       return sum(nd,y)-sum(nd,x-1);         
                  };
                  int m=(l+r)>>1;
                  if (nk[nd]){
                     int i;
                     int ans=0;
                     for (i=s;i<=t;++i)
                          if (dt[i]>=x&&dt[i]<=y)++ans;
                     return ans;
                  }
                  else {
                      m=(l+r)>>1;
                      if (s>m)
                         return getnum(nd*2+1,m+1,r,s,t,x,y);
                      else if (t<=m)
                           return getnum(nd*2,l,m,s,t,x,y);
                      else return getnum(nd*2,l,m,s,m,x,y)+getnum(nd*2+1,m+1,r,m+1,t,x,y);
                  }
                  }
                 
             void work(){
                  scanf("%ld",&n);
                  limit=int(sqrt(n));
                  make_tree(1,1,n);
                 
                  int i,j,a,b;
                  ans=0;
                  for (i=1;i<=n;++i)
                      scanf("%ld",&dt[i]);
                  for (i=n;i>=1;--i){
                      ans+=sum(1,dt[i]-1);
                     modify(1,1,n,i,0,dt[i]);
                      }
                     
                  //now ans is the current inversion
                 
                  scanf("%ld",&m);
                  int x,y;
                 
                  for (i=1;i<=m;++i){
                      scanf("%ld%ld",&a,&b);
                      if (b>dt[a]){
                             x=getnum(1,1,n,1,a-1,dt[a]+1,b);
                             y=getnum(1,1,n,a+1,n,dt[a],b-1);
                             ans=ans-x+y;
                      }
                      else if(b<dt[a]){
                           x=getnum(1,1,n,1,a-1,b+1,dt[a]);
                           y=getnum(1,1,n,a+1,n,b,dt[a]-1);
                           ans=ans+x-y;
                      }
                      modify(1,1,n,a,dt[a],b);
                      dt[a]=b;
                      printf("%lld\n",ans);
                      }
                  }
             int main(){
                 work();
                // limit=250;
                // make_tree(1,1,250000);
                //  printf("%ld",size);  
                 }