Submission #3102113

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define REP(i,m) for(int i=0;i<m;++i)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
using namespace std;
static const int INF =500000000; 
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
struct BIT{
	int val[60005];
	int n;
	int elem;
	void init(int n_){
		n=1;
		elem=0;
		while(n<n_) n<<=1;
		REP(i,n+1) val[i]=0;
	}
	int add(int k,int a){// ..k]
		++k;
		elem+=a;
		while(k>0){
			val[k]+=a;
			k-=k&-k;
		}
	}
	int query(int k){//[k...
		++k;
		int res=0;
		while(k<=n){
			res+=val[k];
			k+=k&-k;
		}
		return res;
	}
	int query2(int k){// ...k)
		int res=elem-query(k);
		return res;
	}
};
static const int B=200;
BIT bit[205];
BIT sum[205];
BIT bind[205];
int self[205],seq[30005];
int group;
int n;
void init(int N, int A[])
{
	n=N;
	REP(i,n) seq[i]=A[i];
	for(int i=0;i<n;i+=B){
		int m=min(B,n-i);
		bit[i/B].init(n+1);
		REP(j,m) bit[i/B].add(seq[i+j],1),self[i/B]+=bit[i/B].query(seq[i+j]+1);
		++group;
	}
	REP(i,group) sum[i].init(n+1);
	REP(i,n){
		for(int j=i/B;j<group;++j) sum[j].add(seq[i],1);
	}
	REP(i,group){
		bind[i].init(group+1);
		REP(j,i){
			for(int k=i*B;k<min(n,i*B+B);++k) bind[i].add(j,bit[j].query(seq[k]+1));
		}
	}
}
void update(int k,int x){
	int prev=seq[k];
	int pos=k/B,m=min(pos*B+B,n)-pos*B;
	REP(i,m) bit[pos].add(seq[i+pos*B],-1);
	seq[k]=x;
	self[pos]=0;
	REP(i,m) bit[pos].add(seq[i+pos*B],1),self[pos]+=bit[pos].query(seq[i+pos*B]+1);
	for(int i=pos;i<group;++i){
		sum[i].add(prev,-1);
		sum[i].add(x,1);
	}
	REP(i,pos){
		bind[pos].add(i,-bit[i].query(prev+1));
		bind[pos].add(i,bit[i].query(x+1));
	}
	for(int i=pos+1;i<group;++i){
		bind[i].add(pos,-bit[i].query2(prev));
		bind[i].add(pos,bit[i].query2(x));
	}
}
int tmp[205],zip[205];
BIT temp;
int train(int p, int q)
{
	int res=0;
	++q;
	int qbegin=q/B;
	for(int i=0;i<qbegin;++i) res+=bind[i].query(0)+self[i];
	qbegin*=B;
	int m=q-qbegin;
	
	REP(i,m)  res+=(qbegin==0?0:sum[qbegin/B-1].query(seq[i+qbegin]+1));

	REP(i,m) zip[i]=tmp[i]=seq[i+qbegin];
	sort(zip,zip+m);
	int zn=unique(zip,zip+m)-zip;
	REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip;
	temp.init(zn+1);
	REP(i,m) res+=temp.query(tmp[i]+1),temp.add(tmp[i],1);
	int pbegin=p/B;
	for(int i=0;i*B+B<=q;++i){
		res-=bind[i].query2(pbegin);
		if(i<pbegin) res-=self[i];
	}
	for(int i=qbegin;i<q;++i) res-=(pbegin==0?0:sum[pbegin-1].query(seq[i]+1));
	pbegin*=B;
	if(qbegin!=pbegin){
		m=p-pbegin;
		REP(i,m) zip[i]=tmp[i]=seq[i+pbegin];
		REP(i,m) res-=sum[qbegin/B-1].query2(tmp[i])-sum[pbegin/B].query2(tmp[i]);
		sort(zip,zip+m);
		int zn=unique(zip,zip+m)-zip;
		REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip;
		temp.init(zn+1);
		REP(i,m) res-=temp.query(tmp[i]+1),temp.add(tmp[i],1);
		
		for(int i=p;i<pbegin+B;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip);
		for(int i=qbegin;i<q;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip);
	}else{
		m=p-pbegin;
		REP(i,m) zip[i]=tmp[i]=seq[i+pbegin];
		sort(zip,zip+m);
		int zn=unique(zip,zip+m)-zip;
		REP(i,m) tmp[i]=lower_bound(zip,zip+zn,tmp[i])-zip;
		temp.init(zn+1);
		REP(i,m) res-=temp.query(tmp[i]+1),temp.add(tmp[i],1);

		for(int i=p;i<q;++i) res-=temp.query(upper_bound(zip,zip+zn,seq[i])-zip);

	}
	return res;
}

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 ...