turbo.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

struct indexed_tree {

   int n;

   int T[1230997];

   void clear(int N){

      n=N;

      for (int i=1; i<=n; i++) T[i]=0;

   }

   void update(int pos, int value){

      for (int i=pos; i<=n; i+=i&-i)

      T[i] += value;

   }

   int get(int pos){

      int i, r=0;

      for (i=pos; i>=1; i-=i&-i)

      r += T[i];

      return r;

   }

   int get(int ll, int rr){

      int r = get(rr) - get(ll-1);

      //printf("get(%d, %d) = %d\n", ll, rr, r);

      return r;

   }

};

int n;

int a[1230997];

int b[1230997];

indexed_tree tr;

main(){

   int i;

   scanf("%d", &n);

   tr.clear(n);

   for (i=1; i<=n; i++) scanf("%d", &a[i]);

   for (i=1; i<=n; i++){

      if (a[i]<=n/2) b[a[i]] = tr.get(a[i]+1, n-a[i]+1);

      tr.update(a[i], 1);

   }

   tr.clear(n);

   for (i=n; i>=1; i--) {

      if (a[i]>(n+1)/2) b[a[i]] = tr.get(n-a[i]+2, a[i]-1);

      tr.update(a[i], 1);

   }

   for (i=1; i<=n/2; i++)

   printf("%d\n%d\n", b[i], b[n-i+1]);

   if (n&1) printf("0\n");

}

Nhận xét