線段樹(shù)

//2828

View Code /*
* [這段話轉(zhuǎn)的。。]
* 如果我們從頭開(kāi)始一次做的話，無(wú)論是用鏈表還是數(shù)組，肯定會(huì)超時(shí)（鏈表尋址時(shí)間長(zhǎng)，數(shù)組移位時(shí)間長(zhǎng)。）。
* 所以要用一個(gè)快速的方法直接找到位置。但是換個(gè)角 度，如果我們反過(guò)來(lái)排，那樣的話，我們就知道他所在的
* 精確位置！把存儲(chǔ)的結(jié)構(gòu)想象成是鏈表，插隊(duì)的人插入后，把他所在的位置從鏈表中屏蔽掉，然后在新的鏈 表種
* 繼續(xù)這樣存，這樣的話我們就得到了我們想要的順序！
*
* 按照這種思想，可以用線段樹(shù)實(shí)現(xiàn)。。。
*
*/

#include <cstdio>
using namespace std;

const int MAXN = 200000 + 5;
int n, p[MAXN], v[MAXN];
int ans[MAXN], tail;

struct node{
int l, r;
int num, value; //num:當(dāng)前時(shí)刻，該區(qū)間有多少空位，， value:該區(qū)間的人的value（只葉子節(jié)點(diǎn)有意義）
};
node tree[MAXN * 3]; //注意*3！ 否則 RE！！

//建樹(shù)
void build(int i, int l, int r){
tree[i].l = l; tree[i].r = r;
tree[i].num = r - l + 1; //初始時(shí)的空位數(shù)

if(l == r) return;
int mid = (l + r) >> 1;
build(i<<1, l, mid);
build(i<<1 | 1, mid+1, r);
}

//……
void insert(int i, int p, int v){
tree[i].num--; //沒(méi)到一個(gè)區(qū)間，該區(qū)間的空位數(shù)-1，
// 因?yàn)榧热坏竭_(dá)該區(qū)間，則該人要么在該區(qū)間，要么在該區(qū)間的子區(qū)間。都導(dǎo)致區(qū)間的空位數(shù)-1

if(tree[i].l == tree[i].r){ //只葉子節(jié)點(diǎn)的value有意義
tree[i].value = v;
return ;
}

if(tree[i<<1].num > p)
insert(i<<1, p, v);
else
insert(i<<1 | 1, p-tree[i<<1].num, v); //減去左子區(qū)間的空位數(shù)
}

void cal(int i){
if(tree[i].l == tree[i].r){
ans[tail++] = tree[i].value;
return;
}
cal(i<<1);
cal(i<<1 | 1);

}

int main(){
while(scanf("%d", &n) == 1){
for(int i=0; i<n; i++)
scanf("%d %d", &p[i], &v[i]);

build(1, 1, n);

for(int i=n-1; i>=0; i--){
insert(1, p[i], v[i]);
}

tail = 0;
cal(1);

printf("%d", ans[0]);
for(int i=1; i<n; i++){
printf(" %d", ans[i]);
}
printf("\n");

}

return 0;
}

也可以用樹(shù)狀數(shù)組

【轉(zhuǎn)】

View Code /*
PKU 2828：樹(shù)狀數(shù)組+二分，一開(kāi)始一直在想如何處理后面加進(jìn)來(lái)的人，即正著考慮的話，當(dāng)前的信息是不能得到答案的，突然想起以前一道題，發(fā)現(xiàn)只要倒著處理的話，就能很好得解決這個(gè)問(wèn)題了，因?yàn)樽詈笠粋€(gè)插進(jìn)來(lái)的人所插入的位置就是這個(gè)人最后所站的位置。具體的做法就是先在樹(shù)狀數(shù)組的每個(gè)位置上都加1，表示一開(kāi)始每個(gè)位置上都站著一個(gè)人，每次二分查找該人所站的位置，找到后把這個(gè)位置的1減掉，相當(dāng)于這個(gè)位置被占據(jù)了，那么下次要得到相同人數(shù)的話位置就相應(yīng)得往后移了。
*/
#include <cstdio>
#include <memory.h>
using namespace std;

const int N = 200005;
int _n;
int res[N];
int c[N];
struct Peo {
int pos, val;
}peo[N];

int lowbit( int n )
{
return n & (-n);
}

void modify( int n, int delta )
{
while( n <= _n )
{
c[n] += delta;
n += lowbit(n);
}
}

int sum( int n )
{
int ret = 0;
while( n != 0 )
{
ret += c[n];
n -= lowbit(n);
}
return ret;
}

int getRank( int pos ) {
int mid, begin = 1, end = _n;
while ( begin < end ) {
mid = (begin + end) / 2;
if ( sum(mid) >= pos ) end = mid;
else begin = mid + 1;
}
return end;
}

int main()
{
while ( scanf("%d", &_n) != EOF ) {
int i;
memset(c, 0, sizeof(c));
for (i=1; i<=_n; ++i) {
scanf("%d %d", &peo[i].pos, &peo[i].val);
peo[i].pos++;
modify(i, 1);
}
for (i=_n; i>=1; --i) {
int now = getRank(peo[i].pos);
res[now] = peo[i].val;
modify(now, -1);
}
for (i=1; i<_n; ++i) {
if (i == 1) printf("%d", res[i]);
else printf(" %d", res[i]);
}
printf(" %d\n", res[_n]);
}
return 0;
}

總結(jié)

以上是生活随笔為你收集整理的poj-2828 Buy Tickets ***的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。