Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=100000;
type ansistring=string;
     ar=array[1..maxn] of ansistring;
var n:longint; re:int64;
    a:ar;
    s,p,d,q:array[1..maxn] of longint;

procedure rf;
var i,l,j:longint;
begin
     assign(input,fi); reset(input);
     readln(n);
     for i:=1 to n do
     begin
          readln(a[i]);
          p[i]:=i; q[i]:=i;
     end;
     close(input);
end;

function comp(var y,x:ansistring):longint;
var i,min:longint;
begin
     if length(y)<length(x) then min:=length(y) else min:=length(x);
     for i:=1 to min do
         if y[i]<x[i] then
         begin
              comp:=-1; exit;
         end
         else
         begin
              if y[i]>x[i] then
              begin
                   comp:=1; exit;
              end;
         end;
     if length(y)<length(x) then comp:=-1
     else
     begin
          if length(y)>length(x) then comp:=1
          else comp:=0;
     end;
end;

function com(var y,x:ansistring):longint;
var i,min,lx,ly:longint;
begin
     lx:=length(x); ly:=length(y);
     min:=(lx+ly-abs(lx-ly)) shr 1;
     for i:=0 to min-1 do
         if y[ly-i]<x[lx-i] then
         begin
              com:=-1; exit;
         end
         else
         begin
              if y[ly-i]>x[lx-i] then
              begin
                   com:=1; exit;
              end;
         end;
     if ly<lx then com:=-1
     else
     begin
          if ly>lx then com:=1
          else com:=0;
     end;
end;

procedure sort(l,r:longint);
var i,j,y:longint; x,t:ansistring;
begin
     i:=l; j:=r; x:=a[q[(i+j) shr 1]];
     repeat
           while comp(a[q[i]],x)=-1 do i:=i+1;
           while comp(a[q[j]],x)=1 do j:=j-1;
           if i<=j then
           begin
                y:=q[i]; q[i]:=q[j]; q[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure sort1(l,r:longint);
var i,j,y:longint; x,t:ansistring;
begin
     i:=l; j:=r; x:=a[p[(i+j) shr 1]];
     repeat
           while com(a[p[i]],x)=-1 do i:=i+1;
           while com(a[p[j]],x)=1 do j:=j-1;
           if i<=j then
           begin
                y:=p[i]; p[i]:=p[j]; p[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort1(i,r);
     if l<j then sort1(l,j);
end;

procedure add(i:longint);
begin
     while i<=n do
     begin
          s[i]:=s[i]+1;
          i:=i+i and (-i);
     end;
end;

function calc(i:longint):longint;
var r:longint;
begin
     r:=0;
     while i>0 do
     begin
          r:=r+s[i];
          i:=i-i and (-i);
     end;
     calc:=r;
end;

procedure pr;
var i,j,l:longint; t:char;
begin
     sort(1,n);
     sort1(1,n);
     for i:=1 to n do d[p[i]]:=i;
     re:=0;
     for i:=1 to n do
     begin
          add(d[q[i]]);
          re:=re+i-calc(d[q[i]]);
     end;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
char s[N][15];
long long x[N], y[N];
pair<int, int> a[N];
int n, bit[N];

void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%s", s[i]);
}

long long hash(char * s, const bool rev = false) {
    int n = strlen(s); long long res = 0;
    if(rev) for(int i = n-1; i >= 0; --i) res = res * 27 + s[i] - 0x60;
    else for(int i = 0; i < n; ++i) res = res * 27 + s[i] - 0x60;
    for(int i = 10 - n; i > 0; --i) res *= 27;
    return res;
}

void compress() {
    for(int i = 0; i < n; ++i) x[i] = y[i] = hash(s[i]); sort(y, y+n);
    for(int i = 0; i < n; ++i) a[i].first = lower_bound(y, y+n, x[i]) - y + 1;
    for(int i = 0; i < n; ++i) x[i] = y[i] = hash(s[i], true); sort(y, y+n);
    for(int i = 0; i < n; ++i) a[i].second = n - (lower_bound(y, y+n, x[i]) - y);
    sort(a, a+n);
}

void increase(int v) {
    for(; v <= n; v += v & -v) ++bit[v];
}

int sumTo(int v) {
    int res = 0;
    for(; v > 0; v -= v & -v) res += bit[v];
    return res;
}

void solve() {
    long long res = 0;
    for(int i = 0; i < n; ++i) {
        res += sumTo(a[i].second);
        increase(a[i].second);
    }
    printf("%lld\n", res);
}

int main() {
    enter();
    compress();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

typedef unsigned long long int64u;
#define li pair<int64u, int>
#define ll pair<int64u, int64u>
const int N = 100005;
const int lim = 10;
using namespace std;
int bit[N], p[N], n;
ll a[N];
li b[N];

int64u HASH(string s) {
    int64u h = 0;
    while (s.length() < lim) s = s + '`';
    for(int i=0; i<s.length(); i++)
        h = 27 * h + s[i] - '`';
    return h;
}

void Upd(int i) {
    while (i <= n) {
        bit[i]++;
        i += i & (-i);
    }
}

int get(int i) {
    int s = 0;
    while (i) {
        s += bit[i];
        i -= i & (-i);
    }
    return s;
}

int main()
{
    scanf("%d\n", &n);
    int i, j; string s, rs;
    for(i=0; i<n; i++) {
        getline(cin, s); s = s.substr(0, s.length()-1);
        rs = string(s.rbegin(), s.rend());
        a[i] = ll(HASH(s), HASH(rs));
    }
    sort(a, a+n, greater<ll>());
    for(i=0; i<n; i++) b[i] = li(a[i].second, i);
    sort(b, b+n);
    long long res = 0;
    for(i=0; i<n; i++) p[b[i].second] = i + 1;
    for(i=0; i<n; i++) {
        res += get(p[i]);
        Upd(p[i]);
    }
    printf("%lld", res);
    return 0;
}

Code mẫu của RR

//Written by RR
{$R-,Q-}
{$Mode objFPC}
{$inline on}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
type
  st            =       string[11];
var
  f1,f2         :       text;
  n             :       longint;
  x,y           :       array[1..MAXN] of st;
  bit,b,ind     :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure swap(var a,b:longint); inline;
    var
      temp:longint;
    begin
      temp:=a; a:=b; b:=temp;
    end;
procedure swaps(var a,b:st); inline;
    var
      temp:st;
    begin
      temp:=a; a:=b; b:=temp;
    end;
procedure inp;
    var
      i:longint;
    begin
      readln(f1,n);
      for i:=1 to n do
          readln(f1,x[i]);
    end;
procedure sort1(l,r:longint); inline;
    var
      i,j:longint;
      mid:st;
    begin
      i:=l; j:=r; mid:=x[l+random(r-l+1)];
      repeat
        while x[i]<mid do inc(i);
        while x[j]>mid do dec(j);
        if i<=j then
          begin
            if i<j then swaps(x[i],x[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort1(i,r);
      if l<j then sort1(l,j);
    end;
procedure sort2(l,r:longint); inline;
    var
      i,j:longint;
      mid:st;
    begin
      i:=l; j:=r; mid:=y[ind[l+random(r-l+1)]];
      repeat
        while (y[ind[i]]<mid) do inc(i);
        while (y[ind[j]]>mid) do dec(j);
        if i<=j then
          begin
            if i<j then swap(ind[i],ind[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort2(i,r);
      if l<j then sort2(l,j);
    end;
procedure reverse(var a,kq:st);
    var
      i:longint;
    begin
      for i:=length(a) downto 1 do
        kq:=kq+a[i];
    end;
function get(u:longint):longint; inline;
    var
      v:longint;
    begin
      if u<=0 then exit(0);
      v:=u-u and (-u);
      exit(bit[u]+get(v));
    end;
procedure update(u:longint); inline;
    var
      v:longint;
    begin
      inc(bit[u]);
      v:=u+u and (-u);
      if v<=n then update(v);
    end;
procedure solve;
    var
      i:longint;
      res:int64;
    begin
      for i:=1 to n do
        reverse(x[i],y[i]);
      for i:=1 to n do ind[i]:=i;
      sort2(1,n);
      for i:=1 to n do
        b[ind[i]]:=i;
      res:=0;
      for i:=1 to n do
        begin
          res:=res+i-1-get(b[i]);
          update(b[i]);
        end;
      writeln(f2,res);
    end;

begin
  openF;
  inp;
  sort1(1,n);
  solve;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 100011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;



int n,dem[maxn+10];
long long KQ=0;
char S[11];

struct chuoi{
      int id;
      char s[11];
      chuoi(){};
      bool operator <(chuoi T) const{
           return(strcmp(s,T.s)<0);
      }
};

chuoi A[maxn];

void reverse(char p[])
{
     int len=strlen(p);
     char t;
     for(int i=(--len), j=0; i>len/2; i--, j++)
     {
          // exchange elements
          t=p[i];
          p[i]=p[j];
          p[j]=t;
     }
}

void update(int u){
     while(u<=100000){
          dem[u]++;
          u+=u&-u; 
     }
}

long long tinh(int u){
     long long r = 0;
     while(u>0){
          //printf("%d\n",u);
          r+=dem[u];
          u-=u&-u;
     }
     return r;
}

int main()
{
   // freopen("MCHAOS.in","r",stdin);
     memset(dem,0,sizeof(dem));
     scanf("%d",&n);
     for(int i = 0;i<n;i++){
          scanf("%s",A[i].s);
         // printf("%s\n",A[i].s);
     }
     sort(A,A+n);
     for(int i = 0;i<n;i++){
           A[i].id = n-i;
           reverse(A[i].s);
           // printf("%s\n",A[i].s);
     }
     sort(A,A+n);
     for(int i = 0;i<n;i++){
            // printf("%d\n",A[i].id);
          KQ += tinh(A[i].id-1);
          update(A[i].id);
     }
     printf("%lld\n",KQ);
  //   getch();
}

Code mẫu của ll931110

Program MCHAOS;
{$inline on}
Const
  input  = '';
  output = '';
  maxn = 100000;
Var
  n: longint;
  res: int64;
  s: array[1..maxn] of string[10];
  a: array[1..maxn] of longint;
  pos: array[1..maxn] of longint;

Procedure init;inline;
Var
  f: text;
  i: longint;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do readln(f, s[i]);

  Close(f);
End;

Procedure swap(i,j: longint);inline;
Var
  ts: string[10];
  tpos: longint;
Begin
  ts:= s[i];
  s[i]:= s[j];
  s[j]:= ts;

  tpos:= pos[i];
  pos[i]:= pos[j];
  pos[j]:= tpos;
End;

Procedure quicksort;

  Procedure partition(l,h: longint);inline;
  Var
    i,j: longint;
    p: string[10];
  Begin
    If l >= h then exit;
    i:= l;
    j:= h;
    p:= s[random(h - l + 1) + l];

    Repeat
      While s[i] < p do inc(i);
      While s[j] > p do dec(j);

      If i <= j then
        Begin
          If i < j then swap(i,j);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,n);
End;

Procedure update(v: longint);inline;
Begin
  While v > 0 do
    Begin
      inc(a[v]);
      v:= v - (v and -v);
    End;
End;

Function calc(v: longint): longint;inline;
Var
  t: longint;
Begin
  t:= 0;
  While v <= maxn do
    Begin
      t:= t + a[v];
      v:= v + (v and -v);
    End;
  calc:= t;
End;

Procedure reverse(i: longint);inline;
Var
  ts: string[10];
  j: longint;
Begin
  ts:= '';
  For j:= length(s[i]) downto 1 do ts:= ts + s[i][j];
  s[i]:= ts;
  pos[i]:= i;
End;

Procedure solve;inline;
Var
  i: longint;
Begin
  quicksort;
  For i:= 1 to n do reverse(i);
  quicksort;

  res:= 0;
  For i:= 1 to n do
    Begin
      res:= res + calc(pos[i]);
      update(pos[i] - 1);
    End;
End;

Procedure printresult;inline;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, res);
  Close(f);
End;

Begin
  init;
  solve;
  printresult;
End.

Code mẫu của khuc_tuan

#include <iostream>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <functional>
#include <ctime>
#include <cstdio>
#include <cstdarg>

using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define Fill(a,b) memset( (a), (b), sizeof(a))
#define pb push_back
#define MP make_pair

char a[100010][12], ra[100010][12];
char *c[100010];
int inv[100010], T[100010];
pair<char*,int> b[100010];
int n;

bool cmp(pair<char*,int> p1, pair<char*,int> p2) {
    return strcmp(p1.first, p2.first) < 0;
}

bool cmp2(char * c1, char * c2) {
    return strcmp(c1, c2) < 0;
}

int main() {
    scanf("%d", &n);
    gets(a[0]);
    for(int i=0;i<n;++i) gets(a[i]);
    for(int i=0;i<n;++i) c[i] = a[i];
    sort( c, c + n, cmp2);
    for(int i=0;i<n;++i) {
        for(int j=strlen(c[i])-1, t=0;j>=0;--j, ++t)
            ra[i][t] = c[i][j];
    }
    for(int i=0;i<n;++i) b[i] = MP(ra[i], i);
    sort(b, b + n, cmp);
    for(int i=0;i<n;++i) inv[b[i].second] = i;
    long long res = 0;
    for(int i=0;i<n;++i) {
        int j;
        for(j=inv[i];j<n;j|=j+1) res += T[j];
        for(j=inv[i];j>=0;j&=j+1,--j) ++T[j];
    }
    printf("%lld\n", res);
    return 0;
}