Description：

定义手机信号强度 $F=\max(0,c-d^2)$ ， $d$ 是这个位置距路上所有信号站距离的最小值，如果没有信号站， $F=0$ ，支持三种操作：

$1$ 、在 $[l,r]$ 中每隔 $v$ 建一个信号站。（保证之前 $[l,r]$ 中没有信号站）

$2$ 、拆除 $[l,r]$ 中的信号站。

$3$ 、询问坐标 $x$ 的手机信号强度。

$1\le n \le 2\times 10^5$

Solution：

看上去十分像线段树，然而线段树十分不好维护，由于只有单点求值，所以用 $set$ 维护区间，对于 $1$ 操作，先调整右端点使得右端点建了信号站，这样有两种可能，一是与所有其它区间不相交，这时直接把他插进去即可，还有可能是被另一个区间包含，因为题目只保证 $[l,r]$ 中不存在信号站，可能有一个区间 $v\ge r-l+1$ ，所以就要把 $set$ 中这个区间分裂，再把这三个区间加进去。对于 $2$ 操作，删除所有它包含的区间，并调整两端区间端点。对于询问操作，如果他被一个区间包含，那么比较他和他旁边两个信号站的距离，这个可以 $O(1)$ 求，如果不被包含，就在他两边区间中比较端点即可。全程注意判断是否等于 $begin/end$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int m;

ll c;

#define piii pair<pair<int,int>,int>

#define fi first

#define se second

#define mp(a,b) make_pair(a,b)

set< piii > s;

char str[20];

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + (c ^ 48);

		c = getchar();

	}

	return res;

}

int main()

{

	freopen("cellphone.in","r",stdin);

	freopen("cellphone.out","w",stdout);

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

	register int l,r,v;

	for(int i = 1;i <= m;++i)

	{

		scanf("%s",str);

		if(str[0] == 'c')

		{

			l = read();r = read();v = read();

			r = (r - l) / v * v + l;

			set< piii >::iterator it = s.lower_bound(mp(mp(l,r),v));

			if(it != s.begin())

			{

				--it;

				if((it -> fi.se) > r)

				{

					piii k = *it;s.erase(it);

					int r_ = ((l - 1) - k.fi.fi) / k.se * k.se + k.fi.fi;s.insert(mp(mp(k.fi.fi,r_),k.se));

					int l_ = ((r - k.fi.fi) / k.se + 1) * k.se + k.fi.fi;s.insert(mp(mp(l_,k.fi.se),k.se));

				}

			}

			s.insert(mp(mp(l,r),v));

		}

		if(str[0] == 'd')

		{

			l = read();r = read();

			set< piii >::iterator it = s.lower_bound(mp(mp(l,r),0));

			if(it -> fi.fi != l && it != s.begin())

			{

				--it;

				if(it -> fi.se >= l)

				{

					int r_ = ((l - 1) - (it -> fi.fi)) / (it -> se) * (it -> se) + (it -> fi.fi);

					s.insert(mp(mp(it -> fi.fi,r_),it -> se));

					if(it -> fi.se > r)

					{

						int l_ = ((r - it -> fi.fi) / (it -> se) + 1) * (it -> se) + it -> fi.fi;

						s.insert(mp(mp(l_,it -> fi.se),it -> se));

					}

					s.erase(it);

				}

			}

			while(true)

			{

				set< piii >::iterator it = s.lower_bound(mp(mp(l,r),0));

				if(it == s.end())break;

				if(it -> fi.fi > r)break;

				if(it -> fi.se <= r)s.erase(it);

				else

				{

					int l_ = ((r - it -> fi.fi) / (it -> se) + 1) * (it -> se) + it -> fi.fi;

					s.erase(*it);

					s.insert(mp(mp(l_,it -> fi.se),it -> se));

					break;

				}

			}

		}

		if(str[0] == 'q')

		{

			v = read();

			set< piii >::iterator it = s.lower_bound(mp(mp(v,0),0));

			if(it == s.end())

			{

				if(it == s.begin())puts("0");

				else

				{

					--it;

					if((it -> fi.se) <= v)

					{

						printf("%lld\n",max(0ll,c - (ll)(v - (it -> fi.se)) * (v - (it -> fi.se))));

					}

					else

					{

						int l_ = (v - it -> fi.fi) / (it -> se) * (it -> se) + it -> fi.fi;

						int r_ = l_ + it -> se;

						int d = min(v - l_,r_ - v);

						printf("%lld\n",max(0ll,c - (ll)d * d));

					}

				}

			}

			else

			{

				if(it -> fi.fi == v)printf("%lld\n",c);

				else

				{

					if(it == s.begin())printf("%lld\n",max(0ll,c - (ll)(it -> fi.fi - v) * (it -> fi.fi - v)));

					else

					{

						int d = it -> fi.fi - v;

						--it;

						if(it -> fi.se < v)d = min(d,v - (it -> fi.se));

						else

						{

							int l_ = (v - it -> fi.fi) / (it -> se) * (it -> se) + it -> fi.fi;

							int r_ = l_ + it -> se;

							d = min(d,min(v - l_,r_ - v));

						}

						printf("%lld\n",max(0ll,c - (ll)d * d));

					}

				}

			}

		}

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}