poj2828[单点修改]

发表于 | 分类于 ， ， | 阅读数 次

链接:poj2828[单点修改]

题解

  • 倒着单点更新
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    using namespace std;
    const int N=2e5+7;
    typedef pair<int,int> s;
    s q[N];
    int tr[N<<2],ans[N],n;
    inline void build(int o,int l,int r){
    	tr[o]=r-l+1;
    	if(l==r)return ;
    	int mid=l+r>>1;
    	build(lson);
    	build(rson);
    }
    inline void update(int o,int l,int r,int x,int p){
    	if(l==r){ans[l]=p;tr[o]=0;return ;}
    	int mid=l+r>>1;
    	if(x<=tr[o<<1])update(lson,x,p);
    	else update(rson,x-tr[o<<1],p);
    	tr[o]-=1;
    }
    int main(){
    	while(~scanf("%d",&n)){
    		int m=n+1;
    		build(1,1,m);
    		rep(i,1,n)scanf("%d%d",&q[i].first,&q[i].second);
    		repd(i,n,1)update(1,1,m,q[i].first+1,q[i].second);
    		rep(i,1,n)printf("%d ",ans[i]);
    		puts("");
    	}
    	return 0;
    }