求助!!50WA
查看原帖
求助!!50WA
224228
YUNSI楼主2021/8/13 09:52

线段树+离散化,实在是不知道错在哪里了,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;
}
2021/8/13 09:52
加载中...