当前位置:编程学习 > C/C++ >>

来看看boost::detail::addr_impl_ref模板,在addressof.hpp文件中:

题意:给你一个插入的序列,然后输出最后的序列,如果用一般方法查询为o(n),而用线段树查询可以优化到log(n)。。。。
AC代码:

[cpp] 
#include <iostream> 
#include<string.h> 
#include<algorithm> 
#include<cstdio> 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
#define lson l,mid,rt<<1 
#define rson mid+1,r,rt<<1|1 
#define N 200005 
using namespace std; 
typedef struct { 
    int l; 
    int r; 
    int sum; 
}Node; 
Node node[N<<2]; 
struct Point 

 int x; 
 int y; 
}s1[N]; 
int s[N]; 
void push_up(int rt) 

   node[rt].sum=node[rt<<1].sum+node[rt<<1|1].sum; 

void build(int l,int r,int rt) 

    node[rt].l=l; 
    node[rt].r=r; 
    if(l==r){ 
      node[rt].sum=1; 
      return; 
    } 
    int mid=(l+r)>>1; 
    build(lson); 
    build(rson); 
    push_up(rt); 

void Quary(int l,int r,int rt,int val,int x) 

    if(node[rt].l==node[rt].r) 
    { 
        node[rt].sum=0; 
        s[node[rt].l]=x; 
         return; 
    } 
    int mid=(l+r)>>1; 
    if(node[rt<<1].sum>=val)   Quary(lson,val,x); 
    else Quary(rson,val-node[rt<<1].sum,x); 
    push_up(rt); 

void in(int &a) 

    char ch; 
    while((ch=getchar())<'0'||ch>'9'); 
    for( a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0'; 
 

int main() 

    int n; 
    while(~scanf("%d",&n)) 
    { 
         CLR(s,-1); 
         CLR(node,0); 
         build(1,n,1); 
        for(int i=0;i!=n;++i) in(s1[i].x),s1[i].x++,in(s1[i].y); 
        for(int i=n-1;i>=0;--i) Quary(1,n,1,s1[i].x,s1[i].y); 
        for(int i=1;i<n;++i) 
           printf("%d ",s[i]); 
           printf("%d\n",s[n]); 
    }return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,