Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: