【JZOJ5821】【NOIP提高A组模拟2018.8.16】 手机信号（set/权值线段树）

Problem

Hint

Solution

• 这道题就是一道考验你细节处理的题。
• 我们用形如(l,r,v)的三元组表示一个区间的信号站，意为从l到r每隔v有一个信号站。
• 考虑用set/权值线段树维护这些三元组。

• 我们插入一个三元组的时候，若其与其他三元组的区间互不相交，那自然是最好滴，我们直接丢进set/权值线段树即可。
• 不然的话，囿于他保证当前区间[l,r]中不存在信号站，即保证当前的区间不包含其他区间，那只有可能被其他区间包含。

  

• 如图，记红色区间为a，灰色区间为b。我们现在要插入a，那么原本的b中的a这一段肯定是没有信号站的，数据保证，我们不必管；但它会被分割为l和r两个子区间。
• l区间的三元组很显然；r区间的l则并不是a.r+1，而是>a.r中第一个建有信号站的，具体位置可以自己推一推。

• 如果是拆除[l,r]范围内的信号站，我们可以一个一个地删掉所有两个端点均在[l,r]范围内的三元组。
• 但是，也可能出现上面那种情况，[l,r]在一个三元组内部（或者与一个三元组有交），那么那个三元组就会被删去一部分，然后分割成1~2个子区间。

• 如果要查询点x的话，我们应找到第一个l≥x的三元组，用l-x更新一下d（记d为距离的最小值）。
• 然后，设前面一个三元组为a，用a的最末一个信号站与x的距离更新一下d。
• 此时，这个a可能会包含x，所以判断一下。如果确实包含，则算出x左右两边的两个信号站的位置，更新一下d。

• 然后便是考验你们细节处理以及调试时的耐心的时间了。
• 分析一波时间复杂度。设势能函数为三元组个数，每次插入最多会插入3个、删除1个三元组，因此每次插入至多使势能+2；删除时，每删去1个三元组势能-1；查询的时候，势能不变。
• 而每次插入、删除、查询的复杂度都是 O(log2m) O ( l o g 2 m ) 的。因此：
• 时间复杂度： O(mlog2m) O ( m l o g 2 m ) 。

Code

• 我只打了set，毕竟set更短，更舒服，不必打权值线段树。（毕竟我是c++选手）

#include <bits/stdc++.h>
#define A son[v][0]
#define B son[v][1]
#define fi first
#define se second
#define mp make_pair
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int N=;
int i,m,px,py,f;
ll c;

template<class T> void read(T&x)
{
    char ch=getchar(); x=;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
}
inline void MIN(int&x,int y) {x=min(x,y);}
inline void MAX(int&x,int y) {x=max(x,y);}

int tot=,son[N][];
P tag[N],t[N];
bool des[N];
inline void mark(int v,int l,int r,int f,int s)
{
    int len=r-l;
    if(s>len) return;
    tag[v]=mp(f,s); 
    MIN(t[v].fi,l+s);
    MAX(t[v].se,r-(len-s)%f);
}
inline void New(int&x) {if(!x) x=++tot;}
inline void push(int v,int l,int r,int m)
{
    New(A); New(B);
    if(des[v])
    {
        des[A]=, tag[A]=mp(,), t[A]=mp(+,-);
        des[B]=, tag[B]=mp(,), t[B]=mp(+,-);
        des[v]=;
        return;
    }
    int f=tag[v].fi, s=tag[v].se;
    if(f)
    {
        mark(A,l  ,m,f,s);
        mark(B,m+,r,f,(f-(m+-s-l)%f)%f);
        tag[v]=mp(,);
    }
}
inline void update(int v)
{
    t[v]=mp(+,-);
    if(A) t[v]=t[A];
    if(B) t[v]=mp(min(t[v].fi,t[B].fi),max(t[v].se,t[B].se));
}
void construct(int v,int l,int r)
{
    int m=l+r>>;
    push(v,l,r,m);
    if(px<=l&r<=py) {mark(v,l,r,f,(f-(l-px)%f)%f); return;}
    if(px<=m) construct(A,l,m);
    if(py>m) construct(B,m+,r);
    update(v);
}
void destruct(int v,int l,int r)
{
    if(px<=l&r<=py) {des[v]=; tag[v]=mp(,); t[v]=mp(+,-); return;}
    int m=l+r>>;
    push(v,l,r,m);
    if(px<=m&&A) destruct(A,l,m);
    if(py>m&&B) destruct(B,m+,r);
    update(v);
}
int query1(int v,int l,int r)
{
    if(t[v].fi>) return -;
    if(r<=px) return t[v].se;
    int m=l+r>>,x1=-,x2=-;
    push(v,l,r,m);
    if(A) x1=query1(A,l,m);
    if(px>m&&B) x2=query1(B,m+,r);
    return max(x1,x2);
}
int query2(int v,int l,int r)
{
    if(t[v].fi>) return +;
    if(px<l) return t[v].fi;
    int m=l+r>>,x1=+,x2=+;
    push(v,l,r,m);
    if(px<m&&A) x1=query2(A,l,m);
    if(B) x2=query2(B,m+,r);
    return min(x1,x2);  
}

int main()
{
    freopen("cellphone.in","r",stdin);
    freopen("cellphone.out","w",stdout);
    read(m); read(c);
    fo(i,,N-) t[i]=mp(+,-);
    fo(i,,m)
    {
        switch(getchar())
        {
            case 'c':read(px); read(py); read(f);
            construct(,,);     
            break;

            case 'd':read(px); read(py);
            destruct(,,);
            break;

            case 'q':read(px);
            if(t[].fi>) putchar();
            else
            {
                int x1=query1(,,);
                int x2=query2(,,);
                ll d=( x1>=&(x2>|px-x1<x2-px) ? px-x1 : x2-px );
                printf("%lld",max(l,c-d*d));
            }
            putchar();
            break;
        }
    }
}