YYHS-手机信号

题目描述

输入

输出

样例输入

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 ;

 }

巴特西

YYHS-手机信号

题目描述

输入

输出

样例输入

样例输出

提示

题解

最新文章

热门文章