202112CSPT4磁盘文件操作

题意：有n个id号，m段空间，k个操作：
$0$:从L开始到R或遇到第一个其他非空id号为止，写入$id$号以及值$val$；如果成功写入则输出写入成功的最右位置，否则输出-1
$1$:若$[L,R]$全为同目标id，则删除id号以及值val并输出OK；否则输出FAIL
$2$:若$[L,R]$全为空且上次占用id号全为目标id号，则恢复删除结果并输出OK；否则输出FAIL
$3$:查找单点P的id号以及val值；为空则输出0 0

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
struct Node
{int val,id1,id2,idpre;//值,插入id,表示区间都为相同的id,之前被删除的id int lazyval,lazyid1,lazyid2,lazyidpre;//懒标记 int l,r;
}t[5000010];
vector<int> v;
int ID[800010],q[800010][4];
int n,m,k;
int find(int s)
{return lower_bound(v.begin(),v.end(),s)-v.begin()+1;
}
void pushup(int p)
{t[p].val=(t[ls].val==t[rs].val)?t[ls].val:1e9+10;if(t[ls].id1==-1||t[rs].id1==-1)t[p].id1=-1;else if(t[ls].id1==t[rs].id1)t[p].id1=t[ls].id1;else if(t[ls].id1==0)t[p].id1=t[rs].id1;else if(t[rs].id1==0)t[p].id1=t[ls].id1;else t[p].id1=-1;if(t[ls].id2==-1||t[rs].id2==-1)t[p].id2=-1;else if(t[ls].id2==t[rs].id2)t[p].id2=t[ls].id2;else t[p].id2=-1;if(t[ls].idpre==-1||t[rs].idpre==-1)t[p].idpre=-1;else if(t[ls].idpre==t[rs].idpre)t[p].idpre=t[ls].idpre;else t[p].idpre=-1;return ;
}
void build(int p,int l,int r)
{t[p].l=l;t[p].r=r;if(l==r){t[p].val=0;t[p].id1=t[p].id2=t[p].idpre=0;t[p].lazyval=1e9+10;t[p].lazyid1=t[p].lazyid2=t[p].lazyidpre=-1;return ;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);t[p].lazyval=1e9+10;pushup(p);
}
void spread(int p)
{if(t[p].lazyval!=1e9+10){t[ls].val=t[rs].val=t[p].lazyval;t[ls].lazyval=t[rs].lazyval=t[p].lazyval;t[p].lazyval=1e9+10; }if(t[p].lazyid1!=-1){t[ls].id1=t[rs].id1=t[p].lazyid1;t[ls].lazyid1=t[rs].lazyid1=t[p].lazyid1;t[p].lazyid1=-1;}if(t[p].lazyid2!=-1){t[ls].id2=t[rs].id2=t[p].lazyid2;t[ls].lazyid2=t[rs].lazyid2=t[p].lazyid2;t[p].lazyid2=-1;}if(t[p].lazyidpre!=-1){t[ls].idpre=t[rs].idpre=t[p].lazyidpre;t[ls].lazyidpre=t[rs].lazyidpre=t[p].lazyidpre;t[p].lazyidpre=-1;}return ;
}
int findR(int p,int l,int id) 
{spread(p);if(t[p].r<l||t[p].id1==id||t[p].id1==0)return -999;else if(t[p].id2!=-1)return t[p].l-1;else {int mid=(t[p].l+t[p].r)>>1;int R=(l<=mid)?findR(ls,l,id):-999;return (R==-999)?findR(rs,l,id):R;}
}
void change(int p,int l,int r,int k,int id,bool ig=0)
{if(t[p].r<l||t[p].l>r)return ;if(t[p].l>=l&&t[p].r<=r){if(k!=1e9+10)t[p].val=t[p].lazyval=k;t[p].id1=id;t[p].id2=id;t[p].lazyid1=id;t[p].lazyid2=id;if(!ig)t[p].idpre=t[p].lazyidpre=id;return ;}spread(p);int mid=(t[p].l+t[p].r)>>1;if(l<=mid)change(ls,l,r,k,id,ig);if(mid<r)change(rs,l,r,k,id,ig);pushup(p); 
}
int askidsame(int p,int l,int r,int id,bool ig=0)
{if(t[p].r<l||t[p].l>r)return 0;if(t[p].l>=l&&t[p].r<=r){if(ig)return (t[p].id2==0&&t[p].idpre==id);//恢复 else return t[p].id2==id;//删除 }	spread(p);int mid=(t[p].l+t[p].r)>>1;int same=1;if(l<=mid)same=same&&askidsame(ls,l,r,id,ig);//区间都要id相同 if(mid<r&&same)same=same&&askidsame(rs,l,r,id,ig);return same;
}
int askval(int p,int x)
{if(x>=t[p].l&&x<=t[p].r&&t[p].val!=1e9+10)return t[p].val;spread(p);int mid=(t[p].l+t[p].r)>>1;int val=0;if(x<=mid)val=askval(ls,x);else val=askval(rs,x);return val;
} 
int askid(int p,int x)
{if(x>=t[p].l&&x<=t[p].r&&t[p].id2!=-1)return t[p].id2;spread(p);int mid=(t[p].l+t[p].r)>>1;int id2=-1;if(x<=mid)id2=askid(ls,x);else id2=askid(rs,x);return id2;
} 
int main()
{cin>>n>>m>>k;for(int i=1;i<=k;i++){cin>>q[i][0];if(q[i][0]==0){cin>>ID[i]>>q[i][1]>>q[i][2]>>q[i][3];v.push_back(q[i][1]);v.push_back(q[i][1]-1);v.push_back(q[i][2]);v.push_back(q[i][2]+1);}if(q[i][0]==1){cin>>ID[i]>>q[i][1]>>q[i][2];v.push_back(q[i][1]);v.push_back(q[i][1]-1);v.push_back(q[i][2]);v.push_back(q[i][2]+1);}if(q[i][0]==2){cin>>ID[i]>>q[i][1]>>q[i][2];v.push_back(q[i][1]);v.push_back(q[i][1]-1);v.push_back(q[i][2]);v.push_back(q[i][2]+1);}if(q[i][0]==3){cin>>q[i][1];v.push_back(q[i][1]);}}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());//将多余的数字去除build(1,1,v.size());for(int i=1;i<=k;i++){int L=find(q[i][1]),R=find(q[i][2]);//cout<<"!"<<L<<" "<<R<<endl;if(q[i][0]==0){int realR=findR(1,L,ID[i]);//cout<<"!!"<<realR<<endl; if(realR!=-999)R=min(realR,R);//找到右区间 if(L<=R){cout<<v[R-1]<<endl;//cout<<q[i][2]<<endl;// 注意返回离散化前的值change(1,L,R,q[i][3],ID[i]);}else cout<<"-1"<<endl;//如果R大于l说明区间无法赋值 }else if(q[i][0]==1){if(askidsame(1,L,R,ID[i])){cout<<"OK"<<endl;change(1,L,R,1e9+10,0,1);}else cout<<"FAIL"<<endl;}else if(q[i][0]==2){if(askidsame(1,L,R,ID[i],1)){cout<<"OK"<<endl;change(1,L,R,1e9+10,ID[i],1);}else cout<<"FAIL"<<endl;}else if(q[i][0]==3){int id=askid(1,L);int val=askval(1,L);if(id==0)cout<<"0 0"<<endl;else cout<<id<<" "<<val<<endl;}//cout<<"!!"<<t[3].id1<<" "<<t[3].id2<<endl;} return 0;
}