POJ 2828 Buy Tickets&POJ 2299 Ultra-QuickSort

POJ 2828 Buy Tickets

線段樹基本應用

傳送門：HustOJ

POJ2299

題意

2828

排隊買票時候插隊。

給出一些數對，分别代表某個人的想要插入的位置Pos_i和他的Val_i，求出最後的隊列的val順序

2299

求逆序對數量

思路

兩個題都不難，都是線段樹基本應用。

逆序對從前往後處理，遇到一個數，就查詢比他大還在他前面出現的數的個數。是以線段樹維護出現過的數。又因為資料範圍是999999999，是以需要hash一下。先排個序，标記1~n，再恢複原序。對于每個數i的hash[i]，查詢[hash[i],n]有多少個數出現過。線段樹記錄1到n出現過的數，出現一次就加一，維護區間和，即出現過的次數。

插隊問題，注意到後面的人的要求總能被滿足，先從後面處理。而後面的人會擠前面的人，是以從後網前處理時，比如某人想進k位置，實際上是從前往後數k個空位，就是他的實際位置。線段樹開始置1，表示有空位，維護和，表示區間的空位數。插入時，如果左兒子空位夠，那麼插入左兒子；否則減左側空位數，插入右兒子。

代碼

逆序對

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
    LL sum;
}stree[*MAXN];
struct Num
{
    LL val;
    int i;
    int hash;
}num[MAXN];
bool cmp1(Num a, Num b)
{
    return a.val<b.val;
}
bool cmp2(Num a, Num b)
{
    return a.i<b.i;
}
void pushup(int rt)
{
    stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        stree[rt].sum=;
        return;
    }
    int m=(l+r)>>;
    build(lson);
    build(rson);
    pushup(rt);
}
void change(int pos, int l, int r, int rt)
{
    if(l==r)
    {
        stree[rt].sum++;
        return;
    }
    int m=(l+r)>>;
    if(pos<=m) change(pos, lson);
    else change(pos, rson);
    pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R) return stree[rt].sum;

    int m=(l+r)>>;
    int res=;
    if(L<=m) res+=query(L, R, lson);
    if(m<R) res+=query(L, R, rson);
    return res;
}
int main(int argc, char *argv[])
{
    _;
    int n;
    while(cin>>n&&n!=)
    {
        for(int i=;i<=n;i++)
        {
            num[i].i=i;
            cin>>num[i].val;
        }
        sort(num+, num++n, cmp1);
        for(int i=;i<=n;i++)
        {
            num[i].hash=i;
        }
        sort(num+, num++n, cmp2);
        build(, n, );
        LL res=;
        for(int i=;i<=n;i++)
        {
            res+=query(num[i].hash, n, , n, );
            change(num[i].hash, , n, );
        }
        cout<<res<<endl;
    }

    //system("pause");
    return ;
}
           

插隊

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
    LL sum;
}stree[*MAXN];
struct Num
{
    LL val;
    int hash;
    int pos;
}num[MAXN];
bool cmp1(Num a, Num b)
{
    return a.hash<b.hash;
}
void pushup(int rt)
{
    stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        stree[rt].sum=;
        return;
    }
    int m=(l+r)>>;
    build(lson);
    build(rson);
    pushup(rt);
}
int change(int pos, int l, int r, int rt)
{
    if(l==r)
    {
        stree[rt].sum=;
        return l;
    }
    int m=(l+r)>>;
    int ret=;
    if(stree[rt<<].sum>=pos) ret=change(pos, lson);
    else ret=change(pos-stree[rt<<].sum, rson);
    pushup(rt);
    return ret;
}
int main(int argc, char *argv[])
{
    _;
    int n;
    while(cin>>n)
    {
        for(int i=;i<=n;i++)
        {
            scanf("%d",&num[i].pos);
            num[i].pos++;
            scanf("%lld",&num[i].val);
        }

        build(, n, );
        for(int i=n;i>=;i--)
        {
            num[i].hash=change(num[i].pos, , n, );
        }
        sort(num+, num++n,cmp1);
        for(int i=;i<=n;i++)
        {
            printf("%lld%c",num[i].val,i==n ? '\n' : ' ');
        }
    }

    //system("pause");
    return ;
}