60pts 求调
查看原帖
60pts 求调
724676
Iwara_qwq楼主2022/8/7 09:16
#include<bits/stdc++.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
const ll inf=0x3f3f3f3f3f,INF=0x7f7f7f7f7f;
namespace Yorihime_Nao{
	template<class T> T MAX(T x,T y){return x>y?x:y;}
	template<class T,class ... Arg> T MAX(T x,T y,Arg ... arg){return MAX(x>y?x:y,arg...);}
	template<class T> T MIN(T x,T y){return x<y?x:y;}
	template<class T,class ... Arg> T MIN(T x,T y,Arg ... arg){return MIN(x<y?x:y,arg...);}
	template<class T> T lowbit(T x){return x&-x;}
	template<class T> void SWAP(T &x,T &y){T qwq;qwq=x;x=y;y=qwq;return;}
}
using namespace Yorihime_Nao;
const ll MAXN=5e5+5,MOD=998244353;
ll n,m,x;
struct node{
	ll l,r,h;
	bool operator < (const node &oth)const{
		return h<oth.h;
	}
};
node t[MAXN];
struct segment_tree{
	ll data[MAXN<<2],lazy[MAXN<<2];
	void init(){
		for(int i=1;i<=8e5;i++)data[i]=1;
		for(int i=1;i<=8e5;i++)lazy[i]=-1;
	}
	void push_down(ll id,ll L,ll R){
		if(lazy[id]==-1)return;
		ll mid=(L+R)>>1;
		data[id<<1]=(mid-L+1)*lazy[id]%MOD;
		lazy[id<<1]=lazy[id];
		data[id<<1|1]=(R-mid)*lazy[id]%MOD;
		lazy[id<<1|1]=lazy[id];
		lazy[id]=-1;
		return;
	}
	void update(ll id,ll L,ll R,ll UL,ll UR,ll delta){
		if(UR<L||UL>R)return;
		if(UL<=L&&R<=UR){
			data[id]=(R-L+1)*delta%MOD;
			lazy[id]=delta;
			return;
		}
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		update(id<<1,L,mid,UL,UR,delta);
		update(id<<1|1,mid+1,R,UL,UR,delta);
		data[id]=(data[id<<1]+data[id<<1|1]+MOD)%MOD;
		return;
	}
	ll query(ll id,ll L,ll R,ll QL,ll QR){
		if(QR<L||QR>R)return 0;
		if(QL<=L&&R<=QR)return data[id]%MOD;
		ll mid=(L+R)>>1;
		push_down(id,L,R);
		return (query(id<<1,L,mid,QL,QR)+query(id<<1|1,mid+1,R,QL,QR)+MOD)%MOD;
	}
};
segment_tree tree;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>t[i].l>>t[i].r>>t[i].h;
	sort(t+1,t+1+n);
	tree.init();
//	for(int i=1;i<=40;i++)cout<<tree.data[i]<<" ";
//	cout<<endl;
//	for(int i=1;i<=10;i++)cout<<tree.query(1,1,1e5,i,i)<<" ";
//	cout<<endl;
	for(int i=1;i<=n;i++){
		ll qwq=(tree.query(1,-1,1e5+1,t[i].l,t[i].l)+tree.query(1,-1,1e5+1,t[i].r,t[i].r))%MOD;
		tree.update(1,-1,1e5+1,t[i].l,t[i].r,qwq);
	}
//	for(int i=1;i<=10;i++)cout<<tree.query(1,1,1e5,i,i)<<" ";
//	cout<<endl;
	ll ans=0;
	for(int i=1;i<=m;i++){
		cin>>x;
		ans+=tree.query(1,-1,1e5+1,x,x);
		ans%=MOD;
	}
	cout<<ans;
	return 0;
}

2022/8/7 09:16
加载中...