Submission #16852

---

Source Code Expand

#include"training.h"
#include<cmath>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class Fenwick_tree{
	int n,a[30000];

public:
	void build(int n){
		this->n=n;
		rep(i,n) a[i]=0;
	}

	void add(int i,int v){
		for(;i<n;i|=i+1) a[i]+=v;
	}

	int sum(int i,int j){
		if(i==0){
			int s=0;
			for(;j>=0;j=(j&(j+1))-1) s+=a[j];
			return s;
		}
		return sum(0,j)-sum(0,i-1);
	}
};

class Fenwick_tree_dual{
	int n,a[174];

public:
	void build(int n){
		this->n=n;
		rep(i,n) a[i]=0;
	}

	void add(int i,int j,int v){
		if(i==0){
			for(;j>=0;j=(j&(j+1))-1) a[j]+=v;
			return;
		}
		add(0,j,v);
		add(0,i-1,-v);
	}

	int sum(int i){
		int s=0;
		for(;i<n;i|=i+1) s+=a[i];
		return s;
	}
};

class Fenwick_tree_dual_2D{
	int m;
	Fenwick_tree_dual a[174];

public:
	void build(int m,int n){
		this->m=m;
		rep(i,m) a[i].build(n);
	}

	void add(int t,int l,int b,int r,int v){
		if(t==0){
			for(;b>=0;b=(b&(b+1))-1) a[b].add(l,r,v);
			return;
		}
		add(0,l, b ,r, v);
		add(0,l,t-1,r,-v);
	}

	int sum(int i,int j){
		int s=0;
		for(;i<m;i|=i+1) s+=a[i].sum(j);
		return s;
	}
};

int n,n2,a[30000];

Fenwick_tree_dual_2D block; // block[i][j] := ( バケット i の左端からバケット j の右端までの区間についての解 )
Fenwick_tree freq[174]; // freq[i] := ( バケット 0 の左端からバケット i の右端までの区間についての頻度分布 )

void init(int _n,int _a[]){
	n=_n;
	n2=(int)ceil(sqrt(n));
	rep(i,n) a[i]=_a[i]-1;

	// block の計算
	block.build(n2,n2);
	rep(i,n2){
		static Fenwick_tree FT;
		FT.build(n);

		int res=0;
		for(int j=n2*i;j<n;){
			int i0=j/n2;
			rep(k,n2){
				if(j==n) break;
				res+=FT.sum(a[j]+1,n-1);
				FT.add(a[j],1);
				j++;
			}
			block.add(i,i0,i,i0,res);
		}
	}

	// freq の計算
	static int tmp[30000];
	for(int i=0;i<n;){
		int i0=i/n2;
		freq[i0].build(n);
		rep(j,n2){
			if(i==n) break;
			tmp[a[i]]++;
			i++;
		}
		rep(v,n) freq[i0].add(v,tmp[v]);
	}
}

// 更新クエリ a[p] = x
void update(int p,int x){
	x--;
	if(a[p]==x) return;

	int u=p/n2; // p が属するバケットの番号

	// block の更新
	// p より左の部分による block の変化分の計算
	int m1=0,m2=0;
	for(int i=n2*u;i<p;i++){
		if(x< a[i] && a[i]<=a[p]) m1++;
		if(x>=a[i] && a[i]> a[p]) m2++;
	}
	block.add(u,u,u,n2-1, m1);
	block.add(u,u,u,n2-1,-m2);
	for(int w=u-1;w>=0;w--){
		if(x<a[p]) m1+=freq[w].sum(x+1,a[p])-(w>0?freq[w-1].sum(x+1,a[p]):0);
		if(x>a[p]) m2+=freq[w].sum(a[p]+1,x)-(w>0?freq[w-1].sum(a[p]+1,x):0);
		block.add(w,u,w,n2-1, m1);
		block.add(w,u,w,n2-1,-m2);
	}

	// p より右の部分による block の変化分の計算
	m1=m2=0;
	for(int i=p+1;i<min(n2*(u+1),n);i++){
		if(x> a[i] && a[i]>=a[p]) m1++;
		if(x<=a[i] && a[i]< a[p]) m2++;
	}
	block.add(0,u,u,u, m1);
	block.add(0,u,u,u,-m2);
	for(int w=u+1;w<n2;w++){
		if(x>a[p]) m1+=freq[w].sum(a[p],x-1)-freq[w-1].sum(a[p],x-1);
		if(x<a[p]) m2+=freq[w].sum(x,a[p]-1)-freq[w-1].sum(x,a[p]-1);
		block.add(0,w,u,w, m1);
		block.add(0,w,u,w,-m2);
	}

	// freq の更新
	for(int v=u;v<n2;v++){
		freq[v].add(a[p],-1);
		freq[v].add(x,1);
	}

	a[p]=x;
}

int train(int l,int r){
	r++;
	// u : [l, r) に含まれるバケットのうち、一番左にあるもの
	// v : [l, r) の右にあるバケットのうち、一番左にあるもの
	int u=l; if(u%n2!=0) u+=n2-l%n2; u/=n2;
	int v=r/n2;

	int res=0;
	if(u<v){
		// バケット内でのスワップ回数
		res+=block.sum(u,v-1);

		// 左にはみ出した部分とバケット内とのスワップ回数
		for(int i=l;i<n2*u;i++){
			res+=freq[v-1].sum(0,a[i]-1);
			if(u>0){
				res-=freq[u-1].sum(0,a[i]-1);
			}
		}

		// 右にはみ出した部分とバケット内とのスワップ回数
		for(int i=n2*v;i<r;i++){
			res+=freq[v-1].sum(a[i]+1,n-1);
			if(u>0){
				res-=freq[u-1].sum(a[i]+1,n-1);
			}
		}
	}

	// 左にはみ出した部分と右にはみ出した部分とのスワップ回数
	int m=0;
	static int b[30000]; // はみ出した部分だけからなる a の部分列
	if(u<v){
		for(int i=l;i<n2*u;i++) b[m++]=a[i];
		for(int i=n2*v;i<r;i++) b[m++]=a[i];
	}
	else{ // [l, r) がどのバケットも包含していないとき
		for(int i=l;i<r;i++) b[m++]=a[i];
	}
	static Fenwick_tree FT;
	FT.build(n);
	rep(i,m){
		res+=FT.sum(b[i]+1,n-1);
		FT.add(b[i],1);
	}

	return res;
}

Submission Info

Compile Error

./grader.cpp: In function ‘int main()’:
./grader.cpp:11: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:13: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result