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