5821. 【NOIP提高A组模拟2018.8.16】 手机信号

题目大意

在x轴上，支持查询某个定点到所以被标记的点的最短距离，
在某个区间间隔标记点，删除某个区间的所有点。

题解

关键只是要解决第二个操作，
注意到在要新建基站的整个区间都是没有基站的，
于是就想到一种做法。
用三元组(l,r,v)表示在区间[l,r]中，每间隔v就有一个基站。
考虑到每次新建基站的情况，
1、整个区间都没有被任何区间覆盖，这种情况很好处理，直接新建三元组。
2、这个新加入的区间，是之前某个区间中的某两个相邻基站的空隙，这种情况就将原来的区间分裂为两个区间，然后在加入新的区间。
关于查询，就是在所以区间中，找覆盖了它的区间，还有它前面那个区间的最后一个，跟它后面区间的最前面一个。
关于如何维护这些区间，就用c++自带的set，按照l来维护，要保证set里面的所有区间不能重叠。

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <set>
#define ll long long
#define N 200003
#define M 2147483646
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

ll max(ll a,ll b){return a>b?a:b;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int T,n,m,l,r,v,x,opl,opr,opx,ops,tot;
ll c,ans;
bool bz[2003];

struct node
{
    int l,r,v;
}t,w;

set<node> q;
set<node>::iterator it;
bool operator<(const node& lhs, const node& rhs)
{  
    return lhs.l<rhs.l;
}  

int main()
{
    freopen("cellphone.in","r",stdin);
    freopen("cellphone.out","w",stdout);

    scanf("%d%lld",&T,&c);

    w.v=1;
    w.l=w.r=-M;q.insert(w);
    w.l=w.r=M;q.insert(w);

    for(tot=1;T;T--)
    {
        for(ch=G();ch!='q' && ch!='o' && ch!='d';ch=G());
        if(ch=='q')
        {
            read(x);
            w.l=w.r=x;
            it=q.lower_bound(w);
            t=*it;ans=t.l-x;

            it--;
            t=*it;
            if(t.r<=x) 
            {
                r=(t.r-t.l)/t.v*t.v+t.l;
                ans=min(ans,(ll)x-r);
            }
            else
            {
                for(l=0,r=(t.r-t.l)/t.v;l<r;)
                {
                    m=(l+r)>>1;
                    v=t.l+m*t.v;
                    ans=min(ans,(ll)abs(v-x));
                    if(v>x)r=m;else l=m+1;
                }
                m=(l+r)>>1;
                v=t.l+m*t.v;
                ans=min(ans,(ll)abs(v-x));
            }
            ans=c-ans*ans;
            if(ans<0)ans=0;
            write(ans),P('\n');
        }
        else
        if(ch=='o')
        {
            read(l);read(r);read(v);
            w.l=l;w.r=r;w.v=v;
            it=q.upper_bound(w);
            it--;t=*it;         
            if(t.r<l)q.insert(w);else
            {
                q.erase(t);
                w.l=t.l,w.r=l-1,w.v=t.v;
                if(w.l<=w.r)q.insert(w);

                w.l=((r-t.l)/t.v+1)*t.v+t.l,w.r=t.r;w.v=t.v;
                if(w.l<=w.r)q.insert(w);

                w.l=l;w.r=r;w.v=v;
                q.insert(w);
            }
        }
        else
        {
            read(l);read(r);w.l=l;
            it=q.upper_bound(w);
            it--;t=*it;it++;
            if(t.r>=l)
            {
                q.erase(t);
                t.r=l-1;
                if(t.l<=t.r)q.insert(t);
            }
            for(;;)
            {
                t=*it,it++;
                if(t.r<=r)q.erase(t);else break;
            }
            if(t.l<=r)
            {
                q.erase(t);
                t.l=((r-t.l)/t.v+1)*t.v+t.l;
                if(t.l<=t.r)q.insert(t);
            }
        }
    }

    return 0;
}