一道简单的排队问题

[原网站地址，我再也不想去写那个网站了](http://poj.org/problem?id=2828)

题意

简单来说有n个人，他们希望自己排在第ai梯队，价值为bi，然后简单地转化题意就是数空格数,emmmmm...... 具体自己看比较好，然后题目很傻逼，卡人很难受

题解

建一颗线段树，统计范围内0的个数，然后找到相应的地点插入就好了

意义

一道不那么模板的变通线段树，然后就是大佬的玄学优化大法，nb！ 。

AC代码

 

#include<stdio.h>
#include<queue>
#include<map>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stack>
#include<vector>
#include<set>
#define re register//大佬的玄学优化大法1，直接取内存
using namespace std;
//#define int long long
#define ll long long
#define speed(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int maxn=2e5+10;//大佬的玄学优化大法2，减少空间换取时间
const int inf=0x3f3f3f3f;
const int INF=1ll<<62;

inline int rd() {
    int x=0;//大佬的玄学优化大法3，不取负数减少操作
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}

int gcd(int a,int b) {
    return b? gcd(b,a%b):a;
}

int n,t,m;
int a[maxn<<1],b[maxn<<1];
int res[maxn<<1],res2[maxn<<1];
int tree[maxn<<2];

void build (int l,int r,int rt) {
    tree[rt]=r-l+1;//范围里的0的个数
    if(l==r) {
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}

int updata(int l,int r,int rt,int need) {
    tree[rt]--;//到这里说明字串有去一个掉，所以父亲节点就先删为敬
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(tree[rt<<1]>=need)return updata(l,mid,rt<<1,need);
    else return updata(mid+1,r,rt<<1|1,need-tree[rt<<1]);//左边取完不够，就去找右边多出来的那部分
}


int main() {
    while(~scanf("%d",&n)) {
        for(re int i=1; i<=n; i++) {
            a[i]=rd();
            b[i]=rd();
            a[i]=a[i]+1;
        }
        build(1,n,1);
        for(re int i=n; i>=1; i--) {
            int pos=updata(1,n,1,a[i]);
            res[pos]=b[i];
        }
        for(re int i=1; i<n; i++) {
            printf("%d ",res[i]);
        }
        printf("%d",res[n]);//大佬的玄学优化大法4,取出重复的if减少操作
        puts("");//大佬的玄学优化大法5,额不懂
    }
    return 0;
}