URAL/1090

来自"NOCOW"

听说这题要用树状数组，特意到百度知道看了看，才把这题ＡＣ了

http://baike.baidu.com/view/1420784.html?wtp=tt

#include<iostream>
using namespace std;
 
long n,k;
long ans=1,a[10000]={0},in[10000];
 
int Lowbit(int t)
{
    ++in[t];
    return t&(t^(t-1));
}
 
int Sum(int end)
{
int sum=0;
while (end>0)
{
    sum+=in[end];
    end-=Lowbit(end);
}
return sum;
}
 
void add(int pos)
{
while(pos<=n)
{
    ++in[pos];
    pos+=Lowbit(pos);
}
}
 
void clear()
{
    long i;
    for (i=1;i<=n;i++) in[i]=0;
}
 
int main(void)
{
    long max=-1,i,j,s;
    cin>>n>>k;
    for (i=1;i<=k;++i)
    {
     s=0;
     clear();
     for (j=1;j<=n;++j)
      cin>>a[j];
     for (j=n;j>=1;--j)
      {
          add(a[j]);
          s+=Sum(a[j]-1);
      }
      if (s>max) { max=s;ans=i;}
    }
    cout<<ans<<"\n";
    return 0;
}
 
by churchill

var total,max,w,ij,i,j,n,g,r:longint;
    c:array[1..10001] of longint;
 
function lowbit(k:longint):longint;
begin
  lowbit:=k and -k;
end;
 
function sum(k:longint):longint;
var t,s:longint;
begin
  t:=k;
  s:=0;
  while t>0 do
  begin
    inc(s,c[t]);
    t:=t-lowbit(t);
  end;
  sum:=s;
end;
 
procedure change(k:longint);
var t:longint;
begin
  t:=k;
  while t<=n do
  begin
    inc(c[t]);
    t:=t+lowbit(t);
  end;
end;
 
begin
  readln(n,g);
  max:=maxlongint;ij:=0;
 
  for i:=1 to g do
  begin
    fillchar(c,sizeof(c),0);
    w:=0;
    for j:=1 to n do
    begin
      read(r);
      inc(w,sum(r));
      change(r);
    end;
    readln;
    if w<max then
    begin
      max:=w;
      ij:=i;
    end;
  end;
  writeln(ij);
end.
                         //BY Lv.wind