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

Re而且 无需 query 操作

Posted by WilliamACM at 2013-07-26 14:35:07 on Problem 3277
In Reply To:【离散化后按照h从小到大排序 做线段树即可】 Posted by:WilliamACM at 2013-07-26 14:33:31
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define ll long long
const ll N=40009;
struct node
{
    ll x,y,h;
    bool operator <(node a) const{return h<a.h;}
}a[N];
vector<ll> ar;
struct Tree
{
    ll l,r,lazy,A;
    ll len()
    {
        return ar[r]-ar[l];
    }
}t[N<<3];
ll n;

#define ls (p<<1)
#define rs (ls|1)
#define mid ((t[p].l+t[p].r)>>1)
void build_tree(ll p,ll l,ll r)
{
    t[p].l=l,t[p].r=r;
    t[p].lazy=t[p].A=0;
    if(l+1==r)return;
    build_tree(ls,l,mid);
    build_tree(rs,mid,r);
}
void push_down(ll p)
{
    if(t[p].lazy)
    {
        t[ls].lazy=t[rs].lazy=t[p].lazy;
        t[ls].A=t[p].lazy*t[ls].len();
        t[rs].A=t[p].lazy*t[rs].len();
        t[p].lazy=0;
    }
}
void modify(ll p,ll l,ll r,ll h)
{
    if(t[p].l==l&&t[p].r==r)
    {
        t[p].lazy=h;
        t[p].A=t[p].len()*h;
        return;
    }
    push_down(p);
    if(r<=mid) modify(ls,l,r,h);
    else
        if(l>=mid) modify(rs,l,r,h);
    else
    {
        modify(ls,l,mid,h);
        modify(rs,mid,r,h);
    }
    t[p].A=t[ls].A+t[rs].A;
}
ll  query(ll p,ll l,ll r)
{
    if(t[p].l==l&&t[p].r==r)return t[p].A;
    push_down(p);
    if(r<=mid) return query(ls,l,r);
    else
        if(l>=mid) return query(rs,l,r);
    else return query(ls,l,mid)+query(rs,mid,r);
}
ll M;
void init()
{
    scanf("%lld",&n);
    for(ll i=0;i<n;i++)
    {
        scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].h);
        if(a[i].x>a[i].y) swap(a[i].x,a[i].y);
        ar.push_back(a[i].x);
        ar.push_back(a[i].y);
    }
    sort(ar.begin(),ar.end());
    M=unique(ar.begin(),ar.end())-ar.begin();
    sort(a,a+n);
    for(ll i=0;i<n;i++)
    {
        a[i].x=lower_bound(ar.begin(),ar.begin()+M,a[i].x)-ar.begin();
        a[i].y=lower_bound(ar.begin(),ar.begin()+M,a[i].y)-ar.begin();
    }
}
void solve()
{
    build_tree(1,0,M-1);
    for(ll i=0;i<n;i++)
    if(a[i].x<a[i].y)
    {
        modify(1,a[i].x,a[i].y,a[i].h);
    }
    printf("%lld\n",t[1].A);
}
int main()
{
   // freopen("in.txt","r",stdin);
    init();
    solve();
    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