Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

很水的线段树。。。。

Posted by CKboss at 2014-07-17 13:27:36 on Problem 3277
直接更新区间lazy标记一下
输出的时候把lazy全部推到子节点,直接统计一下就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long int LL;

const LL maxn=204000;

LL r[maxn*2],md[maxn*2],val[maxn*2],n,m,vt,zhi[maxn*2],Hash[maxn*2],high[maxn];

bool cmpR(int a,int b)
{
   return val[a]<val[b];
}

int Lisan(int n)
{
    for(int i=0;i<n;i++) r[i]=i;
    sort(r,r+n,cmpR);
    md[0]=val[r[0]];
    val[r[0]]=m=0;
    for(int i=1;i<n;i++)
    {
        if(md[m]!=val[r[i]])
            md[++m]=val[r[i]];
        val[r[i]]=m;
    }
    return m;
}

LL tree[maxn<<2],cover[maxn<<2];

void push_down(int l,int r,int rt)
{
    if(cover[rt])
    {
        tree[rt<<1]=max(tree[rt<<1],tree[rt]);
        tree[rt<<1|1]=max(tree[rt<<1|1],tree[rt]);
        cover[rt<<1]=cover[rt<<1|1]=1;
        cover[rt]=0;
    }
}

void update(int L,int R,LL c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        tree[rt]=max(tree[rt],c);
        cover[rt]=1;
        return ;
    }
    push_down(l,r,rt);
    int m=(l+r)/2;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
}

LL ans;

void over_tree(int l,int r,int rt)
{
    push_down(l,r,rt);
    if(l==r)
    {
        ans+=(Hash[r+1]-Hash[l])*tree[rt];
        return ;
    }
    int m=(l+r)/2;
    over_tree(lson); over_tree(rson);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        vt=0;
        memset(tree,0,sizeof(tree));
        memset(cover,0,sizeof(cover));
        for(int i=0;i<n;i++)
        {
            LL a,b,c;
            scanf("%I64d%I64d%I64d",&a,&b,&c);
            val[vt]=zhi[vt]=a; vt++;
            val[vt]=zhi[vt]=b; vt++;
            high[i]=c;
        }
        int mx=Lisan(vt);
        for(int i=0;i<vt;i++)
        {
            Hash[val[i]]=zhi[i];
        }
        for(int i=0;i<n;i++)
        {
            update(val[i*2],val[i*2+1]-1,high[i],0,mx,1);
        }
        ans=0;
        over_tree(0,mx,1);
        printf("%I64d\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator