题目
做法
省流量大师：环状维护(0)子段信息。
线段树做法
转载自：https://www.luogu.com.cn/blog/AutumnKite/solution-p5226
数组倍长以后直接用线段树维护 (B)，发现每次修改只会修改最多四个 (B_i) ，可以直接单点修改。
对于询问，显然可以二分答案 (md)，那么显然需要满足 ([x+md-1,n+x-md+1]) 这段区间中存在被大于 (0) 的数包围的全 (0) 子段。
也就是说，我们需要求区间中被大于 (0) 的数包围的子段数量。
基础线段树练习题。
注意特判答案为 (0) 的情况，即 (A_x=0) 且 ([x+1,n+x-1]) 中没有符合条件的子段。然后 (md) 就可以在 ([1,n/2]) 的范围内二分了。
而答案为 (-1) 的情况就是 (md) 在这个范围内取任意值都不合法。当然你想特判也行。
时间复杂度 (O(qlog^2n))。
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
int read(){
register int x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
return f ? x : -x;
}
void print(int x, char ch = '
'){
if (x == 0) return putchar('0'), putchar(ch), void(0);
int cnt = 0, num[25];
for (x < 0 ? putchar('-'), x = -x : 0; x; x /= 10) num[++cnt] = x % 10;
while (cnt) putchar(num[cnt] ^ '0'), --cnt;
putchar(ch);
}
const int N = 200005;
char s[5];
int n, q, a[N], c[N];
namespace segt{
struct node{
int c, l, r, s; // c 是区间中 >0 的数量，l,r表示区间左右的数，s表示满足条件的全 0 子段数量
void init(int v){
s = 0;
if (v) c = l = r = 1;
else c = l = r = 0;
}
}a[N << 2];
node operator + (const node &a, const node &b){
node c;
c.c = a.c + b.c, c.l = a.l, c.r = b.r;
c.s = a.s + b.s;
if (a.c && b.c && (!a.r || !b.l)) ++c.s;
return c;
}
void modify(int u, int l, int r, int x, int v){
if (l == r) return a[u].init(v), void(0);
int md = (l + r) >> 1;
if (x <= md) modify(u << 1, l, md, x, v);
else modify(u << 1 | 1, md + 1, r, x, v);
a[u] = a[u << 1] + a[u << 1 | 1];
}
node query(int u, int l, int r, int L, int R){
if (L <= l && r <= R) return a[u];
int md = (l + r) >> 1;
if (R <= md) return query(u << 1, l, md, L, R);
else if (L > md) return query(u << 1 | 1, md + 1, r, L, R);
else return query(u << 1, l, md, L, R) + query(u << 1 | 1, md + 1, r, L, R);
}
}
int calc(int i){ return c[i] ? a[i] * a[i - 1] % 10 : (a[i] + a[i - 1]) % 10; } // 计算 B 的值
int main(){
n = read(), q = read();
for (register int i = 1; i <= n; ++i){
a[i] = read(), scanf("%s", s), c[i] = s[0] == '*';
a[n + i] = a[i], c[n + i] = c[i];
}
for (register int i = 2; i <= (n << 1); ++i)
segt :: modify(1, 1, n << 1, i, calc(i));
while (q--){
int op = read(), x = read() + 1;
if (op == 1){
a[x] = read(), scanf("%s", s), c[x] = s[0] == '*';
a[n + x] = a[x], c[n + x] = c[x];
if (x > 1) segt :: modify(1, 1, n << 1, x, calc(x));
segt :: modify(1, 1, n << 1, x + 1, calc(x + 1));
segt :: modify(1, 1, n << 1, n + x, calc(n + x));
if (x < n) segt :: modify(1, 1, n << 1, n + x + 1, calc(n + x + 1));
// 修改四个点的 B[i]
}
else{
if (!a[x] && segt :: query(1, 1, n << 1, x + 1, n + x - 1).s == 0){ puts("0"); continue; } // 特判答案为 0 的情况
segt :: modify(1, 1, n << 1, x, a[x]);
segt :: modify(1, 1, n << 1, n + x, a[x]);
// 特别处理端点的 B[i]
int l = 0, r = n >> 1, md, ans = -2;
while (l <= r)
if (md = (l + r) >> 1, segt :: query(1, 1, n << 1, x + md, n + x - md).s) ans = md, l = md + 1;
else r = md - 1;
++ans; // 二分的其实是全 0 段两边的数到端点的距离，所以加 1
print(ans);
if (x > 1) segt :: modify(1, 1, n << 1, x, calc(x));
segt :: modify(1, 1, n << 1, n + x, calc(n + x));
}
}
}
平衡树做法
这个做法是我自己想的，(O(qlogn))就可以处理。
应该都想到了，但是代码恶心。
如果是链状的，用FHQ treap随便处理一下就行了，把一段连续的(0)当成一个节点。
至于修改也最多只会修改两个数字，查询修改过去再修改回来即可，而且越贴近(x+frac{n}{2})的地方效果更佳呦，参照这样的思路查询也就简单不少了。
但是，如果是环，就比较麻烦，因为平衡树区间之间必须要有严格的大小，比如按(l)比大小，或者按(r)比大小，但是环可能存在([n,1])这种反人类的段。
- 对于类似([n,1])的段，我们额外设置一个点来维护，但是代码难度大，算了
我打了一半就删了。 - 考虑常数更大的做法，每次我们维护([1,x])和([y,n])，等到查询再把他们删掉当成([y,x])，GOOD，这样就很好维护了。
有人问，为什么不用倍长（把数组扩大一倍）的方法来做？像上文线段树一样？但是你要明白，这样搞仍然是要处理环的，倍长没用（当然你也可以尝试着用一下，用了倍长代码实现应该会更简单一点）。
个人认为正是因为线段树处理环比平衡树更加无力，所以才要采用二分+倍长的方法，当然，如果采用和平衡树类似的思路，其也可以到达(O(qlogn))。
当然，我打代码为了节省码量，很多地方用了较大常数的写法，所以常数还是可以继续优化下去的，虽然常数大，但是时间仍然很优秀，在2020.10.25跑到了479ms，吸了氧就可以跑到289ms了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define N 110000
#define NN 310000
using namespace std;
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
int n,m;
inline int dis(int x,int y)//x->y的最短距离
{
if(x>y)x^=y^=x^=y;
return mymin(y-x,n-y+x);
}
int val[NN],son[NN][2],len,rt;
struct node
{
int l,r;
node(int x=0,int y=0){l=x;r=y;}
}tr[NN];
inline bool pd(int x,node y)
{
if(y.l<=y.r && x<=y.r && x>=y.l)return 1;
else if(y.l>y.r && (x>=y.l || x<=y.r))return 1;
return 0;
}
inline int node_dis(int x,node y)
{
if(pd(x,y)==1)return 0;
else return mymin(dis(x,y.l),dis(x,y.r));
}
inline int pd(int x,int k)//判断x是否在某个区间内
{
while(x)
{
if(pd(k,tr[x])==1)return x;
if(k<tr[x].l)x=son[x][0];
else x=son[x][1];
}
return 0;
}
void spilt(int now,int k,int &A,int &B)//不存在区间x使得k>=x.l 并且 x.r>k 这里只要x.r<=k就归到A
{
if(!now)A=B=0;
else
{
if(tr[now].r<=k)A=now,spilt(son[A][1],k,son[A][1],B);
else B=now,spilt(son[B][0],k,A,son[B][0]);
}
}
int merge(int A,int B)
{
if(!A || !B)return A+B;
else
{
if(val[A]<=val[B]){son[A][1]=merge(son[A][1],B);return A;}
else {son[B][0]=merge(A,son[B][0]);return B;}
}
}
inline int addnode(int l,int r)
{
len++;
val[len]=rand();
tr[len]=node(l,r);
return len;
}
inline void add(int now)
{
int x,y;
spilt(rt,tr[now].l-1,x,y);
rt=merge(merge(x,now),y);
}
inline void del(int now/*删除编号为x的点*/)
{
int x,y,z;
spilt(rt,tr[now].l-1,x,y);spilt(y,tr[now].r,y,z);
rt=merge(x,z);
}
inline void kuozhan(int now)//只会向右扩展
{
int x,y;
spilt(rt,tr[now].r,x,y);
int k=pd(y,tr[now].r+1);
if(k)
{
spilt(y,tr[k].r,k,y);
tr[now].r=tr[k].r;
}
rt=merge(x,y);
}
inline void fenlie(int now,int k)
{
if(tr[now].l==tr[now].r)del(now);
else if(tr[now].l==k || tr[now].r==k)tr[now].l+=(tr[now].l==k),tr[now].r-=(tr[now].r==k);
else
{
int x=tr[now].r;tr[now].r=k-1;
add(addnode(k+1,x));
}
}
int a[N],b[N],c[N];
inline void change(int now,int k)
{
if((b[now] && k) || (!b[now] && !k))b[now]=k;
else
{
if(!k)//从无到有
{
int t;
if(now!=1 && (t=pd(rt,now-1)))tr[t].r++;
else t=addnode(now,now),add(t);
kuozhan(t);
}
else fenlie(pd(rt,now),now);
b[now]=k;
}
}
inline int tiqu(int k/*包含k的*/,int goal,int &ans)
{
int t=pd(rt,k);
if(!t)return 0;
del(t);
ans=mymax(node_dis(goal,tr[t]),ans);
return t;
}
inline int findright(int x)//疯狂跳右儿子最大
{
while(son[x][1])x=son[x][1];
return x;
}
inline int findleft(int x)
{
while(son[x][0])x=son[x][0];
return x;
}
int findans(int now)//变成环的任务在外面处理
{
int x1=0,x2=0,x3=0,x4=0;
int ans=-1;
if((x1=pd(rt,1)) && (x2=pd(rt,n)))
{
if(x1==x2)return 0;//整个就是一个环
spilt(rt,tr[x1].r,x1,rt);
spilt(rt,tr[x2].l-1,rt,x2);
ans=node_dis(now,node(tr[x2].l,tr[x1].r));
}
else x1=x2=0;
int limit=(now+n/2-1)%n+1;
x3=tiqu(now,now,ans);
x4=tiqu(limit,now,ans);
if(now<limit)
{
int x,y,z;
spilt(rt,now-1,x,y);spilt(y,limit,y,z);
if(y)ans=mymax(ans,node_dis(now,tr[findright(y)]));
if(z)ans=mymax(ans,node_dis(now,tr[findleft(z)]));
else if(x)ans=mymax(ans,node_dis(now,tr[findleft(x)]));
rt=merge(merge(merge(x1,x),merge(x3,y)),merge(x4,merge(z,x2)));
}
else if(now>limit)
{
int x,y,z;
spilt(rt,limit-1,x,y);spilt(y,now,y,z);
if(y)ans=mymax(ans,node_dis(now,tr[findleft(y)]));
if(x)ans=mymax(ans,node_dis(now,tr[findright(x)]));
else if(z)ans=mymax(ans,node_dis(now,tr[findright(z)]));
rt=merge(merge(merge(x1,x),merge(x4,y)),merge(x3,merge(z,x2)));
}
return ans;
}
inline int getnum(int x,int y,int z)
{
if(!z)return (x+y)%10;
return (x*y)%10;
}
inline int getshit(int x)
{
if(!x)return n;
else if(x==n+1)return 1;
else return x;
}
int main()
{
// freopen("std.in","r",stdin);
// freopen("vio.out","w",stdout);
srand(time(0));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
b[i]=1;//防止后面change的时候以为他是0
char st[10];
scanf("%d%s",&a[i],st);
if(st[0]=='+')c[i]=0;
else c[i]=1;
}
for(int i=1;i<=n;i++)
{
change(i,getnum(a[getshit(i-1)],a[i],c[i]));
}
for(int i=1;i<=m;i++)
{
int type;
scanf("%d",&type);
if(type==1)
{
int pos,num;char st[10];
scanf("%d%d%s",&pos,&num,st);
pos++;
if(st[0]=='+')c[pos]=0;
else c[pos]=1;
a[pos]=num;
change(pos,getnum(a[getshit(pos-1)],a[pos],c[pos]));
int x=getshit(pos+1);
change(x,getnum(a[pos],a[x],c[x]));
}
else
{
int pos;scanf("%d",&pos);
pos++;
int x=b[pos];
change(pos,a[pos]);
printf("%d
",findans(pos));
change(pos,x);
}
}
return 0;
}