POJ 2828 线段树逆序插入-白红宇

POJ 2828 线段树逆序插入

阅读量：5302 次

发布时间：2019-06-14

本文共 1022 字，大约阅读时间需要 3 分钟。

思路：

1.线段树逆着插入就OK了

2.块状链表（可是我并不会写）

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,xx,tree[1000050],cnt[1000050];struct Node{
    int num,wei;}node[1000050];void build(int l,int r,int pos,int id){    if(l==r){tree[pos]=1;if(id)printf("%d ",cnt[pos]);return;}    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    build(l,mid,lson,id),build(mid+1,r,rson,id);    tree[pos]=tree[lson]+tree[rson];}void insert(int l,int r,int pos){    if(l==r){tree[pos]=0,cnt[pos]=node[xx].wei;return;}    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;    if(tree[lson]<=node[xx].num)node[xx].num-=tree[lson],insert(mid+1,r,rson);    else insert(l,mid,lson);    tree[pos]=tree[lson]+tree[rson];}int main(){    while(~scanf("%d",&n)){        for(int i=1;i<=n;i++)            scanf("%d%d",&node[i].num,&node[i].wei);        build(1,n,1,0);        for(xx=n;xx;xx--)insert(1,n,1);        build(1,n,1,1),putchar('\n');    }}

这里写图片描述