`
java-mans
  • 浏览: 11340471 次
文章分类
社区版块
存档分类
最新评论

fzu 1608 Huge Mission

 
阅读更多

题目链接:http://acm.fzu.edu.cn/problem.php?pid=1608

题目大意:给出若干区间的效率,求总区间的效率最大和。

题目思路:本来想用一般的延迟操作来做,结果超时,看到网上有一种方法,直接插入区间,最后询问时更新到点,就可以了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define M 110000
inline int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int n,m;
struct node
{
    int l,r,col;
    int mid()
    {
        return (l+r)>>1;
    }
}T[4*M];
void build(int l,int r,int rt)
{
    T[rt].l=l;T[rt].r=r;T[rt].col=0;
    if(l==r) return;
    int mid=T[rt].mid();
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void modify(int l,int r,int rt,int data)
{
    if(T[rt].l==l&&T[rt].r==r)
    {
        T[rt].col=max(data,T[rt].col);
        return;
    }
    int mid=T[rt].mid();
    if(r<=mid) modify(l,r,rt<<1,data);
    else if(l>mid) modify(l,r,rt<<1|1,data);
    else
    {
        modify(l,mid,rt<<1,data);
        modify(mid+1,r,rt<<1|1,data);
    }
}
int query(int rt)
{
    if(T[rt].l==T[rt].r)
    {
        return T[rt].col;
    }
    T[rt<<1].col=max(T[rt].col,T[rt<<1].col);
    T[rt<<1|1].col=max(T[rt].col,T[rt<<1|1].col);
    return query(rt<<1)+query(rt<<1|1);
}
int main()
{
    int l,r,p;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(0,n,1);
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&p);
            modify(l,r-1,1,p);
        }
        printf("%d\n",query(1));
    }
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics