- 先将原始状态的 (B) 处理出来,可以发现,若不修改,则每次指定的起始位置不同,对这个环 (B) 带来的影响只有 (B_0) 不同,即每次 (B_0=A_0) ,其他位置不变.可以询问时修改这个值,询问结束时改回去.
- 如果要修改,可以发现修改 (A_i) 其实只会影响 (B_i,B_{i+1}) 的值,也可以较快完成.
- 只需要用一个 (set) 维护环上的零区间,修改,查询时都分情况维护,回答就好了.断环成链(复制一份接在后面)可以减小编写难度.
(虽然还是挺麻烦)
临摹参考了Menci的代码.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define inf 1e9
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=1e5+10;
const int P=10;
struct node{
int l,r;
node(int pos) : l(pos) {}
node(int l,int r): l(l),r(r) {}
};
bool operator < (const node &a,const node &b)
{
return a.l<b.l;
}
bool operator < (const int &x,const node &y)
{
return x<y.l;
}
typedef node ZeroRange;
int n,m,A[MAXN],B[MAXN<<1];
char C[MAXN];
set<node> s;
typedef set<node>::iterator it;
void update(int pos,int v)
{
if(v==0 && B[pos]!=0)//1->0
{
for(int x=pos;x<2*n;x+=n)//再拼一段,拼成长2n的链
{
it nx=s.lower_bound(x);
it pr=--s.lower_bound(x);
if(nx->l==x+1 && pr->r==x-1)
{
node newnode(pr->l,nx->r);
s.erase(pr);
s.erase(nx);
s.insert(newnode);
}
else if(nx->l==x+1)
{
node newnode(x,nx->r);
s.erase(nx);
s.insert(newnode);
}
else if(pr->r==x-1)
{
node newnode(pr->l,x);
s.erase(pr);
s.insert(newnode);
}
else
s.insert(node(x,x));
}
}
else if(v!=0 && B[pos]==0)//0->1
{
for(int x=pos;x<2*n;x+=n)
{
it cur=--s.upper_bound(x);
if(x!=cur->l && x!=cur->r)
{
node l(cur->l,x-1);
node r(x+1,cur->r);
s.erase(cur);
s.insert(l);
s.insert(r);
}
else if(x!=cur->r)
{
node newnode(x+1,cur->r);
s.erase(cur);
s.insert(newnode);
}
else if(x!=cur->l)
{
node newnode(cur->l,x-1);
s.erase(cur);
s.insert(newnode);
}
else
s.erase(cur);
}
}
B[pos]=B[pos+n]=v;
}
inline int calc(int x,int y,char opt)
{
if(opt=='+')
return (x + y) % P;
else
return x * y % P;
}
void update(int pos,int v,char opt)
{
A[pos]=v,C[pos]=opt;
update(pos,calc(A[pos],A[(pos-1+n)%n],C[pos]));
update((pos+1)%n,calc(A[(pos+1)%n],A[pos],C[(pos+1)%n]));
}
inline int dist(int x,int y)
{
if(x>y)
swap(x,y);
return min(y-x,x-y+n);
}
int dist(int pos,const node &nd)
{
if(nd.l==inf || nd.l==-inf)
return -1;
if(nd.l<n && nd.r>=n)
{
if(pos%n>=nd.l && pos%n<=nd.r)
return 0;
if(pos%n+n>=nd.l && pos%n+n<=nd.r)
return 0;
}
if(pos%n>=nd.l%n && pos%n<=nd.r%n)
return 0;
return min(dist(pos%n,nd.l%n),dist(pos%n,nd.r%n));
}
int query(int pos)
{
int bak=B[pos];
update(pos,A[pos]);
int ans;
if(s.size()==2)
ans=-1;
else if(s.size()==3)
ans=dist(pos,*++s.begin());
else
{
ans=-1;
bool flag=(++s.begin())->l == ((--(--s.end()))->r+1)%n;
int opos=((pos-n/2)+n)%n;
it opp=--s.upper_bound(opos);
if(opp==s.begin())
opp=--s.upper_bound(opos+n);
if(flag && (opp==++s.begin()))
opp=--s.upper_bound(opos+n);
if(opp!=s.begin() && !(flag && (opp==++s.begin() || opp == --(--s.end()))))
ans=max(ans,dist(pos,*opp));
if(opp!=++s.begin())
{
it pr=opp;
pr--;
if(!(flag && pr==++s.begin()))
ans=max(ans,dist(pos,*pr));
}
if(opp!=--s.end())
{
it nx=opp;
++nx;
if(!(flag && nx== --(--s.end())))
ans=max(ans,dist(pos,*nx));
}
}
update(pos,bak);
return ans;
}
int main()
{
n=read(),m=read();
for(int i=0;i<n;++i)
scanf("%d %c",&A[i],&C[i]);
for(int i=0;i<n;++i)
B[i]=B[i+n]=calc(A[i],A[(i-1+n)%n],C[i]);
for(int l=0;l<2*n;)
{
if(B[l]==0)
{
int r=l;
while(r+1<2*n && B[r+1]==0)
++r;
s.insert(node(l,r));
l=r+1;
}
else
++l;
}
s.insert(node(-inf,-inf));
s.insert(node(inf,inf));
for(int i=0;i<m;++i)
{
int op=read(),pos=read();
if(op==1)
{
int v;
char opt;
scanf("%d %c",&v,&opt);
update(pos,v,opt);
}
else
printf("%d
",query(pos));
}
return 0;
}