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

HDU 4351

区间合并的线段树
 
#include<cstdio> 
#include<algorithm> 
#include<cstring> 
#include<vector> 
#define N 100100 
#define f(x) ((x)==0?0:((x)%9==0?9:(x)%9)) 
using namespace std; 
 
struct Tree{ 
    int l,r; 
    int ls,rs,all,num; 
}tree[5*N]; 
int val[N],mul[1125][1125]; 
 
void init(){ 
    int i,j,p,q; 
    for(i=0;i<=1023;i++) 
        for(j=i;j<=1023;j++){ 
            mul[i][j]=0; 
            for(p=0;p<=9;p++) 
                if(i&(1<<p)) 
                    for(q=0;q<=9;q++) 
                        if(j&(1<<q)) 
                            mul[i][j]|=(1<<f(p+q)); 
            mul[j][i]=mul[i][j]; 
        } 

 
void build(int s,int t,int id){ 
    tree[id].l=s,tree[id].r=t; 
    if(s==t){ 
        tree[id].ls=tree[id].rs=tree[id].num=tree[id].all=1<<f(val[s]); 
        return ; 
    } 
    int mid=(s+t)>>1; 
    build(s,mid,id<<1); 
    build(mid+1,t,id<<1|1); 
    tree[id].all=tree[id<<1].all|tree[id<<1|1].all|mul[tree[id<<1].rs][tree[id<<1|1].ls]; //all表示所有情况 
    tree[id].num=mul[tree[id<<1].num][tree[id<<1|1].num];      //num表示此区间内所有数和的digital root 
    tree[id].ls=tree[id<<1].ls|mul[tree[id<<1].num][tree[id<<1|1].ls]; //ls表示所有含有区间左端点的区间的情况 
    tree[id].rs=tree[id<<1|1].rs|mul[tree[id<<1|1].num][tree[id<<1].rs];//rs表示所有含有区间右端点的区间的情况 

 
struct Tree query(int s,int t,int id){ 
    struct Tree t1,t2,t3; 
    if(tree[id].l==tree[id].r)return tree[id]; 
    if(tree[id].l==s && tree[id].r==t)return tree[id]; 
    int mid=(tree[id].l+tree[id].r)>>1; 
    if(mid>=t)return query(s,t,id<<1); 
    else if(mid<s)return query(s,t,id<<1|1); 
    else{ 
        t1=query(s,mid,id<<1); 
        t2=query(mid+1,t,id<<1|1); 
        t3.all=t1.all|t2.all|mul[t1.rs][t2.ls]; 
        t3.num=mul[t1.num][t2.num]; 
        t3.ls=t1.ls|mul[t1.num][t2.ls]; 
        t3.rs=t2.rs|mul[t2.num][t1.rs]; 
        return t3; 
    } 

 
int main(){ 
    int t,T,n,q; 
    int i,j,l,r; 
    init(); 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d",&n); 
        for(i=1;i<=n;i++)scanf("%d",&val[i]); 
        build(1,n,1); 
        scanf("%d",&q); 
        printf("Case #%d:\n",t); 
        for(j=1;j<=q;j++){ 
            scanf("%d %d",&l,&r); 
            struct Tree tem=query(l,r,1); 
            int num=1; 
            vector<int>vec; 
            vec.clear(); 
            for(i=9;i>=0 && num<=5;i--){ 
                if(tem.all&(1<<i)){ 
                    num++; 
                    vec.push_back(i); 
                } 
            } 
            while(num<=5){ 
                vec.push_back(-1); 
                num++; 
            } 
            for(i=0;i<vec.size();i++){ 
                if(!i)printf("%d",vec[i]); 
                else printf(" %d",vec[i]); 
            } 
            puts(""); 
        } 
        if(t!=T)puts(""); 
    } 
    return 0; 

 

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