Splay 95分求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
template <typename T>inline void read(T &x){bool f=0;x=0;char ch=getchar();while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-')ch=getchar(),f=1;while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;}
const int mod=998244353;
int root,tot,n,m;
struct Node {int ch[2],ff,cnt,val,son;} t[1000000];
struct island{
	int l,r,h;
	bool operator <(const island &b)const{
		if(h==b.h){
			if(l==b.l) return r<b.r;
			return l<b.l;
		}
		return h>b.h;
	}
}e[500005];
void push_up(int u) {t[u].son=(t[t[u].ch[0]].son+t[t[u].ch[1]].son+t[u].cnt)%mod;}
void rotate(int x) {
	int y=t[x].ff,z=t[y].ff,
	k=t[y].ch[1]==x;
	t[z].ch[t[z].ch[1]==y]=x;
	t[x].ff=z;
	t[y].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].ff=y;
	t[x].ch[k^1]=y;
	t[y].ff=x;
	push_up(y);
	push_up(x);
}
void Splay(int x,int goal) {
	while(t[x].ff!=goal) {
		int y=t[x].ff;
		int z=t[y].ff;
		if(z!=goal)(t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
		rotate(x);
	}
	if(goal==0) root=x;
}
void insert(int x,int y) {
	int u=root,ff=0;
	while(u&&t[u].val!=x) {
		ff=u;
		u=t[u].ch[x>t[u].val];
	}
	if(u) t[u].cnt+=y;
	else {
		u=++tot;
		if(ff) t[ff].ch[x>t[ff].val]=u;
		t[tot].ch[0]=0;
		t[tot].ch[1]=0;
		t[tot].ff=ff;
		t[tot].val=x;
		t[tot].cnt=y;
		t[tot].son=y%mod;
	}
	Splay(u,0);
}
void Find(int x) {
	int u=root;
	if(!u)return;
	while(t[u].ch[x>t[u].val]&&x!=t[u].val) 
        u=t[u].ch[x>t[u].val];
	Splay(u,0);
}
int Next(int x,int f) {
	Find(x);
	int u=root;
	if((t[u].val>x&&f)||(t[u].val<x&&!f))return u;
	u=t[u].ch[f];
	while(t[u].ch[f^1])u=t[u].ch[f^1];
	return u;
}
int Delete(int l,int r) {
	int last=Next(l,0);
	int next=Next(r,1);
	Splay(last,0);
	Splay(next,last);
	int del=t[next].ch[0],y=t[del].son;
	t[next].ch[0]=0;
	Next(next,1);
	//t[last].cnt-=y;
	//t[next].cnt-=y;
	return y;
}
int K_th(int x) {
	int u=root;
	if(t[u].son<x) return false;
	while(1) {
		int y=t[u].ch[0];
		if(x>t[y].son+t[u].cnt) {
			x-=t[y].son+t[u].cnt;
			u=t[u].ch[1];
		} else if(t[y].son>=x) u=y;
		else return t[u].val;
	}
}
signed main(){
	insert(-2147483647,1);insert(+2147483647,1);
	read(n);read(m);
	for(int i=0;i<m;i++){read(e[i].l);read(e[i].r);read(e[i].h);}
	sort(e,e+m);
	for(int i=0,x;i<n;i++)read(x),insert(x,1);
	for(int i=0,x;i<m;i++){
		x=Delete(e[i].l,e[i].r);
		insert(e[i].l,x);insert(e[i].r,x);
	}
	printf("%lld\n",(t[root].son-2+mod)%mod);
    return 0;
}
/*
signed main() {
	
	N=read();
	while(N--) {
		int opt=read();
		if(opt==1) insert(read());//加入
		else if(opt==2) Delete(read());//删除
		else if(opt==3) {
			Find(read());//查询x排名
			printf("%lld\n",t[t[root].ch[0]].son);
		} else if(opt==4) printf("%lld\n",K_th(read()+1));//查询排名x
		else if(opt==5) printf("%lld\n",t[Next(read(),0)].val);//前驱
		else if(opt==6) printf("%lld\n",t[Next(read(),1)].val);//后继
	}
	return 0;
}*/