考场上抱着骗分的心态随便打了一下,结果,,过了

先上代码

#include<bits/stdc++.h>
#define int long long
//英特纳雄耐尔一定要实现
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int n,m;
struct sb{
	int l,r,h;
	int data;//data记录有几个点掉到上面
	bool operator<(const sb& u)const{
	    return h<u.h;
	}
}a[N];
struct dsb{
	int x;//本来还有其他的后来都去掉了,,所以是结构体
}b[N];
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
#define cin(x) read(x)
int f(int x,int h,int fr){
	for(int i=fr-1/*只找自己下面的*/;i>=0;i--){
		if(a[i].l<=x&&a[i].r>=x){
			return i;
		}
	}
  //找到这个点会掉到哪条线段上,,
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin(n);
	cin(m);
	for(int i=1;i<=m;i++){
		cin(a[i].l);
		cin(a[i].r);
		cin(a[i].h);
	}
	a[0].l=-1;
	a[0].r=INT_MAX;
	a[0].h=0;//a[0]即x轴
	sort(a+1,a+m+1);
	for(int i=1;i<=n;i++){
		cin(b[i].x);
		int t=f(b[i].x,1e9,m+1);
		a[t].data++;//把原有的点丢到下面的对应线段上
	}
	for(int i=m;i>=1;i--){//从上往下找
		if(a[i].data){//没有点掉落在上面的不用管了
			int l=a[i].l,r=a[i].r;
			int t1=f(l,a[i].h,i),t2=f(r,a[i].h,i);//点从两端分别坠落
			a[t1].data+=a[i].data;
			a[t2].data+=a[i].data;
			a[t1].data%=mod;
			a[t2].data%=mod;
		}
	}
	cout<<a[0].data<<endl;
	return 0;
}

可以发现第i条线段的两端向下找对应点最坏情况下需要查找i次(直到找到x轴上),原有点则都要查找m次,这个数据大概像这样

本题中n,m范围相近,时间是$O(n*m+m^2)$即$O(m^2)$,在5e5的范围下压根过不去,,,可是它就是过了,求问为什么