独立博客: 哲学与程序

哲学与程序

ZOJ@3453

ZOJ@3453 题目连接
题意:有N个敌人,排成一排编号为1~n;对于敌人i有一个初始value[i];对于敌人i,其朋友范围区间[Li,Ri],i可能在[Li,Ri]区间内。你每次从右边发射子弹,第i颗子弹值为Ki,打中第一个value值大于或等于Ki的敌人,该敌人value值变为1,其朋友范围内的敌人value值均增加1;但是,如果没有敌人的value值大于或者等于Ki,则所有敌人value值增加1。求最后敌人中最高的value值。
解法:线段树,每个节点设置一个max、add元素,max表示该区间上的最大值,add表示该区间增加的值;实现(1)区间段元素+1操作,即对应的区间add+1;(2)对于对某个value值置1,即可将max=-覆盖该点的所有区间add累加值+1;(3)查找大于或等于K的最右元素。
// 2385696      2011-01-14 20:30:00        Accepted      3453      C++      430      6040      redsea
#include<stdio.h>
#include
<string.h>
#include
<algorithm>
using namespace std;
const int maxn = 100005;
int fr[maxn], fl[maxn], value[maxn];
struct node{
    
int cr,cl;
    
int r,l;
    
int max, add;
}st[maxn
*2];
int len;
int build(int l,int r, int root)
{
    
if(l==r){
        st[root].cr 
= st[root].cl = -1;
        st[root].r 
= r;
        st[root].l 
= l;
        st[root].max 
= value[l];
        st[root].add 
= 0;
        
return value[l];
    }
else{
        
int mid = (l+r)/2;
        st[root].r 
= r;
        st[root].l 
= l;
        len
++;
        
int ll = len;
        st[root].cl 
= ll;
        
int m1 = build(l,mid, ll);
        len
++;
        
int rr = len;
        st[root].cr 
= rr;
        
int m2 = build(mid+1,r,rr);
        st[root].add 
= 0;
        st[root].max 
= (m1<m2?m2:m1);
        
return st[root].max;
    }
}
int add(int l, int r, int root)
{
    
if(root < 0)return -1000000000;
    
else if(st[root].l > r || st[root].r < l){
        
return -1000000000;
    }
    
else if(l <= st[root].l && r >= st[root].r){
        st[root].add
++;
        st[root].max
++;
        
return st[root].max;
    }
else{
        
int m1 = add(l,r,st[root].cl);
        
int m2 = add(l,r,st[root].cr);
        
if(m1<m2)m1=m2;
        
if(st[root].max < m1+st[root].add)st[root].max = m1+st[root].add;
        
return st[root].max;
    }
}
int findMax(int x, int root, int a)
{
    
if(st[root].r == st[root].l)
        
return st[root].l;
    
else{
        
int l = st[root].cl;
        
int r = st[root].cr;
        
if(st[r].max + a+st[root].add >= x)
            
return findMax(x,r,a+st[root].add);
        
else
            
return findMax(x,l,a+st[root].add);
    }
}

int setToOne(int w, int root, int a)
{
    
if(st[root].l == st[root].r)
    {
        st[root].add 
= 0;
        st[root].max 
= -+ 1;
        
return st[root].max;
    }
else{
        
int l = st[root].cl;
        
int r = st[root].cr;
        
if(st[l].l <= w && st[l].r >= w){
            
int m1 =setToOne(w,l,a+st[root].add);
            
int m2 =st[r].max;
            st[root].max 
= (m1<m2?m2:m1)+st[root].add;
            
return st[root].max;
        }
else{
            
int m1 = setToOne(w,r,a+st[root].add);
            
int m2 = st[l].max;
            st[root].max 
= (m1<m2?m2:m1)+st[root].add;
            
return st[root].max;
        }
    }
}
int main()
{
    
int n, m, x;
    
while(scanf("%d",&n)!=EOF)
    {
        
for(int i = 1; i <= n; i++){
            scanf(
"%d%d%d",value+i,fl+i,fr+i);
        }
        len 
= 0;
        build(
1,n,0);
        scanf(
"%d",&m);
        
while(m--)
        {
            scanf(
"%d",&x);
            
if(st[0].max < x){
                add(
1,n,0);
            }
            
else{
                
int index = findMax(x,0,0);
                setToOne(index,
0,0);
                add(fl[index],fr[index],
0);
            }
        }
        printf(
"%d\n",st[0].max);
    }
    
return 0;
}


posted on 2011-01-15 12:34 哲学与程序 阅读(169) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序