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

## 很水的线段树。。。。

Posted by CKboss at 2014-07-17 13:27:36 on Problem 3277
```直接更新区间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: