Zerojudge d788: 排名順序

題目敘述

考試成績出爐了 , 大家開始討論自己的分數高低一個接著一個參與討論 , 新加入的那個人 , 想要知道自己目前排名是多少但是太多人了 , 導致沒辦法一時得到他的排名大家開始請求小光這個答案 , 不過小光非常討厭排名 , 一點都不想幫忙現在就交給你了

輸入說明

每組輸入的第一行有一個數字 \[N \text{(} 1\leq N\leq 100000 \text{)}\] 代表接下來會有N個人陸續參與討論，接下來會有N行，代表接下來陸續加入的人的成績\[M\text{，(} 1\leq M\leq N\text{)}\] 而且每個人的成績都不會重複

輸出說明

對於已經知道的成績，請陸續對每個加入的輸出他的排名

解題方法

解法一：線段樹

(這是我第一次刻線段數，刻的不好請見諒)

先建立一棵線段樹儲存成績區間，並設定排名初始值為0。接著依照讀取順序，每讀入一筆數據q，就將線段\[ [1,q] \]的排名值+1，代表排序在他後面的人排名全部往上後1名。接著查詢範圍\[ [q,q] \]，結果就是當時的排名。

圖解（使用範例測資）

設定
讀入第一筆數據(1)
讀入第二筆數據(5)
以此類推

AC Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <map>

using namespace std;

#define int long long
#define ld long double

#ifdef ONLINE_JUDGE
	#define settings() ios::sync_with_stdio(0);cin.tie(0)
#elif defined(sublime)
	#include <cstdio>
	#define settings() freopen("d788.in","r",stdin) // Because Sublime Text doesn't support input from terminal.
#else
	#define settings()
#endif

#define INF INT64_MAX/100
#define all(x) x.begin(),x.end()

#ifdef ONLINE_JUDGE
    #define debug(x)
#else
    #define debug(x) cerr << #x << " = " << x << '\n'
#endif

#ifdef ONLINE_JUDGE
	#define debug_all(x)
#else
	#define debug_all(x) {cerr << #x << ": "; for (auto i:x) cerr << i << ' '; cerr << '\n';}
#endif

#define v vector
#define vi v< int >
#define vii v< vi >

#define lowbit(x) (x)&(-x)

#define setpoint(x) fixed << setprecision(x)

const double eps = 1e-9;

struct node
{
	int _l,_r,_sum,_lt;
	node (int l=-1,int r=-1,int sum=0,int lazytag=0):_l(l),_r(r),_sum(sum),_lt(lazytag){}
};

struct human
{
	int _order,_value;
	human(int order=-1,int value=-1):_order(order),_value(value){}
	bool operator< (human b)
	{
		if (this->_value == b._value)
			return this->_order<b._order;
		return this->_value > b._value;
	}
};

v<node> seg_tree(400005);
v<human> people;
vi human_pos(100000);

int n;
int sum;
int nmax=0;

void maintain(int pos)
{
	node &now = seg_tree[pos];
	if (now._l!=now._r)
		now._sum=seg_tree[pos<<1]._sum+seg_tree[(pos<<1)+1]._sum;
	now._sum+=now._lt;
}

void build (int pos,int l,int r)
{
	if (l==r)
	{
		seg_tree[pos]=node(l,r);
	}
	else
	{
		int m=l+(r-l)/2;
		build(pos << 1,l,m);
		build((pos<<1)+1,m+1,r);
		seg_tree[pos]._l=l;
		seg_tree[pos]._r=r;
		maintain(pos);
	}
}

void modify(int pos,int l,int r,int v)
{
	node &now = seg_tree[pos];
	if (now._l>=l && now._r<=r)
	{
		now._lt+=v;
	}
	else
	{
		int m = now._l+(now._r-now._l)/2;
		if (l<=m)
			modify(pos<<1,l,r,v);
		if (r>m)
			modify((pos<<1)+1,l,r,v);
	}
	maintain(pos);
}

void query(int pos,int l,int r,int add=0)
{
	node &now = seg_tree[pos];
	if (now._l>=l && now._r<=r)
	{
		sum+=now._sum+add*(r-l+1);
	}
	else
	{
		int m = now._l+(now._r-now._l)/2;
		if (l<=m)
			query(pos<<1,l,r,add+now._lt);
		if (r>m)
			query((pos<<1)+1,l,r,add+now._lt);
	}
}

signed main()
{
	settings();
	while(cin >> n)
	{
		nmax=0;
		for (int i=1;i<=n;++i)
		{
			int  m;
			cin >> m;
			people.push_back(human(i,m));
			nmax=max(nmax,m);
		}
		human_pos.resize(nmax+1);
		seg_tree.resize(4*nmax+1);
		sort(all(people));
		for (int i=0;i<n;++i)
			human_pos[people[i]._order]=i;
		build(1,1,nmax);
		debug(n);
		for (int i=1;i<=n;++i)
		{
			int now_pos=human_pos[i];
			modify(1,1,people[now_pos]._value,1);
			sum=0;
			query(1,people[now_pos]._value,people[now_pos]._value);
			cout << sum << '\n';
		}
		seg_tree.clear();
		human_pos.clear();
		people.clear();
	}
	return 0;
}

解法二：BIT

建立陣列 \[ a \]，其中 \[ a[i] \]代表成績為i的人的排名。接著建立a的差分陣列 \[ b \]。將陣列a的區間\[ [1,q] \]排名+1相當於以下兩個操作：

++b[1];
--b[q+1];

。要查詢q的排名則計算b的前綴和即可得到a[q](因為前綴和和差分互為逆運算)。此時即可用BIT來維護b陣列。

(撰寫中)

題目敘述#

輸入說明#

輸出說明#

解題方法#

解法一：線段樹#

圖解（使用範例測資）#

AC Code#

解法二：BIT#