题目描述
输入
输出
样例输入
11 10000
query 5
construct 5 500 100
query 500
query 1000
construct 10 90 5
query 44
destruct 44 66
query 55
construct 50 60 3
query 46
query 6000
样例输出
975
9999
9775
9984
提示
题解
这道题给你三种操作（这道题用set维护区间）
对于construct操作，我们可以发现加入的区间要么和所有的区间都不相交，要么就是区间的大小比某个区间的v还要小
construct操作读入的x,y我们可以可以把y改成x+(y-x)/v*v（最后一个信号站的位置）
对于destruct操作，我们判断一下左右端点是否把其他的区间截断了
对于query操作，我们只要找一下离这个点最近的一个区间就可以了
具体细节可以看一下代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
int x,y,v;
bool operator <(const node &a) const{
return x<a.x;
}
};
typedef multiset<node>::iterator It;
int m,l,r,v,x,y;
ll c;
char s[];
multiset<node> q;
int calc(int x,int y,int v){ return x+(y-x)/v*v; }
void solve_c(){
scanf("%d%d%d",&x,&y,&v);
y=calc(x,y,v);
It point=q.upper_bound((node){x,,});
if (point!=q.begin()){
point--;
int st=point->x,ed=point->y;
if (st<x&&ed>y){
int stp=point->v;
q.erase(point);
q.insert((node){st,calc(st,x,stp),stp});
if (st!=ed)
q.insert((node){calc(st,x,stp)+stp,ed,stp});
}
}
q.insert((node){x,y,v});
}
void solve_d(){
scanf("%d%d",&x,&y);
It point=q.lower_bound((node){x,,});
if (point!=q.begin()){
point--;
int st=point->x,ed=point->y;
if (st<x&&ed>=x){
int stp=point->v;
q.erase(point);
q.insert((node){st,calc(st,x-,stp),stp});
if (ed>y)
q.insert((node){calc(st,r,stp)+stp,ed,stp});
}
}
point=q.upper_bound((node){y,,});
if (point!=q.begin()){
point--;
int st=point->x,ed=point->y;
if (st<=y&&ed>y){
int stp=point->v;
q.erase(point);
q.insert((node){calc(st,y,stp)+stp,ed,stp});
}
}
q.erase(q.lower_bound((node){x,,}),q.upper_bound((node){y,,}));
}
void solve_q(){
scanf("%d",&x);
int d=1e9;
It point=q.lower_bound((node){x,,});
if (point!=q.end()) d=min(d,point->x-x);
if (point!=q.begin()){
point--;
int st=point->x,ed=point->y;
if (ed>=x){
int stp=point->v;
d=min(d,x-calc(st,x,stp));
if (st!=ed) d=min(d,calc(st,x,stp)+stp-x);
} else d=min(d,x-point->y);
}
if (d==1e9) puts("");
else printf("%lld\n",max(0ll,c-(ll)d*d));
}
int main(){
scanf("%d%lld",&m,&c);
for (int i=;i<=m;i++){
scanf("%s",s);
if (s[]=='q') solve_q(); else
if (s[]=='c') solve_c(); else
if (s[]=='d') solve_d();
}
return ;
}