| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re而且 无需 query 操作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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator