线段树+离散化,实在是不知道错在哪里了,WA了5个点
#include<bits/stdc++.h>
using namespace std;
int cnt,hi,li,ri,a[200005],h[200005],t,w[200005],l1[100005],r1[100005];
struct outt
{
int i,j;
}b[200005];
struct fro
{
int x,i;bool d;
}w1[200005];
bool cmp(const fro &a,const fro &b)
{
return a.x<b.x;
}
struct tre
{
int s,l,r;
}f[400005];
int build(int l,int r)
{
int u=++cnt;
if (l==r) return u;
f[u].s=0;
f[u].l=build(l,(l+r)/2);
f[u].r=build((l+r)/2+1,r);
return u;
}
void push_down(int u)
{
f[f[u].l].s=max(f[f[u].l].s,f[u].s);
f[f[u].r].s=max(f[f[u].r].s,f[u].s);
f[u].s=0;
}
void add(int u,int l,int r,int ll,int rr)//qujian
{
if ((l>=ll)&&(r<=rr))
{
f[u].s=max(f[u].s,hi);
return;
}
push_down(u);
if (ll<=(l+r)/2) add(f[u].l,l,(l+r)/2,ll,rr);
if (rr>(l+r)/2) add(f[u].r,(l+r)/2+1,r,ll,rr);
}
void find(int u,int l,int r)
{
if (l==r)
{
a[l]=f[u].s;
return;
}
push_down(u);
find(f[u].l,l,(l+r)/2);
find(f[u].r,(l+r)/2+1,r);
return;
}
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>li>>ri>>h[i];//w1==>离散化临时数组,w1[].i=在原数组的位置;
w1[++t].x=li;w1[t].i=i;w1[t].d=1;//1==>l;
w1[++t].x=ri;w1[t].i=i;w1[t].d=0;//0==>r;
}
sort(w1+1,w1+1+t,cmp);
w1[0].x=-1;int ct=0;
for (int i=1;i<=t;++i)
{
if (w1[i].x!=w1[i-1].x) w[++ct]=w1[i].x;//w离散化数组
if (w1[i].d==1) l1[w1[i].i]=ct;
else r1[w1[i].i]=ct;//l,r==>读入时的数据/离散化后的数;
}
cnt=0;
int rt=build(1,ct);
for (int i=1;i<=n;i++)
{
hi=h[i];
add(rt,1,ct,l1[i],r1[i]-1);
}
find(rt,1,ct);
a[0]=0;cnt=0;
for (int i=1;i<=ct;i++)
{
if (a[i]!=a[i-1])
{
b[++cnt].i=w[i];
b[cnt].j=a[i];
}
}
int ans=0;
for (int i=1;i<=cnt;i++) ans+=(b[i].i-b[i-1].i)*b[i-1].j;
cout<<ans;
return 0;
}