UVA 1400 线段树-白红宇

UVA 1400 线段树

阅读量：5340 次

发布时间：2019-06-15

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

input

n m　　1<=n,m<=500000

a1 a2 ... an 　　|ai|<=1e9

m行查询

每行一对a b

output

对于每对a b输出区间[a,b]中最小连续和x y,如果有多组满足，输出x最小，如果还有多组满足，输出y最小

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #define MAX 500000 13 14 using namespace std; 15 16 struct pos 17 { 18 int s,e; 19 bool operator<(const pos&a)const 20 { 21 if(s!=a.s) return s
                 
                  >1),lc=k<<1,rc=(k<<1)+1; 44 build(l,m,lc); 45 build(m+1,r,rc); 46 sum[k]=sum[lc]+sum[rc]; //sum 47 pre[k]=sum[lc]+pre[rc]; //pre 48 pree[k]=pree[rc]; 49 if(pre[k]<=pre[lc]) 50 { 51 pre[k]=pre[lc]; 52 pree[k]=pree[lc]; 53 } 54 suf[k]=suf[lc]+sum[rc]; //suf 55 sufs[k]=sufs[lc]; 56 if(suf[k]
                  
                   =r) 79 { 80 if(sub[k]>maxsum) 81 { 82 maxsum=sub[k]; 83 minp=subp[k]; 84 } 85 else if(sub[k]==maxsum) minp=min(minp,subp[k]); 86 node u; 87 u.pre=pre[k];u.pree=pree[k];u.sum=sum[k];u.suf=suf[k];u.sufs=sufs[k]; 88 return u; 89 } 90 int m=l+((r-l)>>1),lc=k<<1,rc=(k<<1)+1; 91 node lcc,rcc; 92 if(a<=m) lcc=query(l,m,lc); 93 if(b>m) rcc=query(m+1,r,rc); 94 if(a<=m&&b>m) 95 { 96 node u; 97 u.sum=lcc.sum+rcc.sum; //sum 98 u.pre=lcc.sum+rcc.pre; //pre 99 u.pree=rcc.pree;100 if(u.pre<=lcc.pre)101 {102 u.pre=lcc.pre;103 u.pree=lcc.pree;104 }105 u.suf=lcc.suf+rcc.sum; //suf106 u.sufs=lcc.sufs;107 if(u.suf
                   
                    maxsum)116 {117 maxsum=subk;118 minp=subpk;119 }120 else if(subk==maxsum) minp=min(minp,subpk);121 return u;122 }123 else if(a<=m) return lcc;124 else return rcc;125 }126 int main()127 {128 freopen("/home/user/桌面/in","r",stdin);129 while(scanf("%d%d",&n,&m)==2)130 {131 build(1,n,1);132 printf("Case %d:\n",cas++);133 while(m--)134 {135 scanf("%d%d",&a,&b);136 minp.s=minp.e=n;137 maxsum=-0x7fffffff-1;138 query(1,n,1);139 printf("%d %d\n",minp.s,minp.e);140 }141 }142 //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);143 return 0;144 }