显然的斜率式子推一下，维护一个斜率递减的凸壳二分
由于有删除
所以每次加一个点不合并左右儿子
当这一层的下一个节点被填满时再合并
这样至少要删除次才会有一次的重构
修改复杂度就是对的
询问的时候个节点
前面每个最多都只会递归左右儿子，最后一个会递归个儿子
节点数复杂度仍然是
不过注意由于这里线段树长度不是的
对于某些叶子节点前面也对着一些需要的
复杂度
空间
开始的时候斜率式子推反了没发现
在网上找了个数据调
调了半天不知道哪里有问题
结果那sb博主造的数据是错的
还在那里得意洋洋的说找了几个程序都没跑过
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>
cs int mod=998244353;
inline void chemx(ll &a,ll b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
struct pt{
int x,y;
pt(int _x=0,int _y=0):x(_x),y(_y){}
friend inline pt operator +(cs pt &a,cs pt &b){
return pt(a.x+b.x,a.y+b.y);
}
friend inline pt operator -(cs pt &a,cs pt &b){
return pt(a.x-b.x,a.y-b.y);
}
friend inline ll operator *(cs pt &a,cs pt &b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
friend inline bool operator <(cs pt &a,cs pt &b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
};
struct node{
vector<pt> vec;
node(){vec.clear();}
inline void pb(cs pt &x){
while(vec.size()>1&&(x-vec[vec.size()-2])*(vec[vec.size()-1]-vec[vec.size()-2])<=0)vec.pop_back();
vec.pb(x);
}
friend inline node merge(cs node &a,cs node &b){
node c;
int i=0,j=0;
while(i<a.vec.size()&&j<b.vec.size()){
if(a.vec[i]<b.vec[j])c.pb(a.vec[i]),i++;
else c.pb(b.vec[j]),j++;
}
while(i<a.vec.size())c.pb(a.vec[i]),i++;
while(j<b.vec.size())c.pb(b.vec[j]),j++;
return c;
}
inline bool check(cs pt &a,cs pt &b,cs pt &c){
pt d=b-a;
return d*c<=0;
}
inline ll query(pt k){
int l=0,r=(int)vec.size()-2;
while(l<=r){
int mid=(l+r)>>1;
if(check(vec[mid],vec[mid+1],k))l=mid+1;
else r=mid-1;
}
return k*vec[l];
}
};
cs int N=300005;
node tr[N<<2];
int last[N],vis[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
inline void build(int u,int l,int r,int dep){
vis[u]=0,tr[u].vec.clear(),last[dep]=0;
if(l==r)return;
build(lc,l,mid,dep+1),build(rc,mid+1,r,dep+1);
}
inline void pushup(int u){
vis[u]=1,tr[u]=merge(tr[lc],tr[rc]);
}
inline void insert(int u,int l,int r,int p,pt k,int dep){
if(r==p){
int x=last[dep];
if(x)pushup(x);
if(l==r)last[dep]=0;else last[dep]=u;
}
if(l==r){tr[u].pb(k);return;}
if(p<=mid)insert(lc,l,mid,p,k,dep+1);
else insert(rc,mid+1,r,p,k,dep+1);
}
void delet(int u,int l,int r,int p,int dep){
tr[u].vec.clear(),vis[u]=0;
if(last[dep]==u)last[dep]=0;
if(l==r)return;
if(p<=mid)delet(lc,l,mid,p,dep+1);
else delet(rc,mid+1,r,p,dep+1);
}
inline ll query(int u,int l,int r,int st,int des,pt k){
if(l==r){return tr[u].query(k);}
if(st<=l&&r<=des){
if(vis[u])return tr[u].query(k);
else return max(query(lc,l,mid,st,des,k),query(rc,mid+1,r,st,des,k));
}
ll res=-2e18;
if(st<=mid)chemx(res,query(lc,l,mid,st,des,k));
if(mid<des)chemx(res,query(rc,mid+1,r,st,des,k));
return res;
}
int n,m,ans,mx;
signed main(){
read(),m=read();
while(m){
ans=n=0;
mx=min(m,300000);
build(1,1,mx,1);
for(int i=1;i<=m;i++){
int op=read();
if(op==1){
int x=read(),y=read();
insert(1,1,mx,++n,pt(x,y),1);
}
else if(op==2){
delet(1,1,mx,n--,1);
}
else {
int l=read(),r=read(),x=read(),y=read();
ll res=query(1,1,mx,l,r,pt(x,y));
ans^=(res%mod+mod)%mod;
}
}
cout<<ans<<'
';
m=read();
}
}