Submission #3188606

---

Source Code Expand

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int n,a[30000],P[30001];
pair<int,int> pr[30000];

void init(int N, int A[])
{
  n=N;
  for(int i=0;i<n;i++){
    a[i]=A[i];
    pr[i].first=A[i];
    pr[i].second=i;
  }
  sort(pr,pr+n);
  int bit[1<<16]={0};
  P[0]=0;
  for(int i=0;i<n;i++){
    P[i+1]=P[i];
    int c=n-a[i]+1,p=c-1;
    while(p){
      P[i+1]+=bit[p];
      p-=p&(-p);
    }
    bit[c]++;
    while(c<1<<16){
      c+=c&(-c);
      bit[c]++;
    }
  }
}

void update(int i, int x)
{
  int k=0;
  for(int j=0;j<i;j++){
    if(a[j]<=a[i]&&a[j]>x){
      k++;
    }
    else if(a[j]>a[i]&&a[j]<=x){
      k--;
    }
  }
  P[i+1]+=k;
  for(int j=i+1;j<n;j++){
    if(a[i]<=a[j]&&x>a[j]){
      k++;
    }
    else if(a[i]>a[j]&&x<=a[j]){
      k--;
    }
    P[j+1]+=k;
  }
  int l=lower_bound(pr,pr+n,make_pair(a[i],i))-pr;
  pair<int,int> e=make_pair(x,i);
  if(a[i]<x){
    int j;
    for(j=l;j+1<n&&pr[j+1]<e;j++){
      pr[j]=pr[j+1];
    }
    pr[j]=e;
  }
  else{
    int j;
    for(j=l;0<=j-1&&e<pr[j-1];j--){
      pr[j]=pr[j-1];
    }
    pr[j]=e;
  }
  a[i]=x;
}

int train(int p, int q)
{
  int A;
  if(n<=5000){
    A=0;
    int bit[1<<16]={0};
    for(int i=q;i>=p;i--){
      int c=a[i],p=c-1;
      while(p){
	A+=bit[p];
	p-=p&(-p);
      }
      bit[c]++;
      while(c<1<<16){
	c+=c&(-c);
	bit[c]++;
      }
    }
  }
  else{
    A=P[q+1]-P[p];
    int k=0;
    for(int i=0;i<n;i++){
      if(pr[i].second<p){
	A-=k;
      }
      else if(pr[i].second<=q){
	k++;
      }
    }
  }
  return A;
}

Submission Info

Compile Error

/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 0 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 1 has invalid symbol index 12
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 2 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 3 has invalid symbol index 2
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 4 has invalid symbol index 11
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 5 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 6 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 7 has invalid symbol index 13
/usr/bin/ld: /usr/lib/debug/usr/lib/x86_64-linux-gnu/crt1.o(.debug_info): relocation 8 has invalid symbol ...