题解
断环为链，把链复制两份
用set维护一下全是0的区间，然后查找x + n / 2附近的区间，附近各一个过不去，最后弃疗了改为查附近的两个，然后过掉了= =
熟练掌握stl的应用，你值得拥有（雾
代码
#include <bits/stdc++.h>
//#define ivorysi
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define mo 974711
#define MAXN 200005
#define pii pair<int,int>
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M;
int A[MAXN * 2],B[MAXN * 2];
char ch[MAXN * 2][3];
set<pii > S;
void Change(int p,int v) {
if(B[p] == v) return;
if(B[p] != 0 && v != 0) {B[p] = v;return;}
if(B[p] == 0) {
auto k = S.upper_bound(mp(p,4 * N));
--k;
pii t = *k;
S.erase(k);
if(p - 1 >= t.fi) S.insert(mp(t.fi,p - 1));
if(p + 1 <= t.se) S.insert(mp(p + 1,t.se));
}
else {
auto k = S.upper_bound(mp(p,4 * N)),g = k;
--g;
pii t2 = *k,t1 = *g;
if(t1.se == p - 1 && t2.fi == p + 1) {
S.erase(k);S.erase(g);
S.insert(mp(t1.fi,t2.se));
}
else if(t1.se == p - 1) {
S.erase(g);S.insert(mp(t1.fi,p));
}
else if(t2.fi == p + 1) {
S.erase(k);S.insert(mp(p,t2.se));
}
else {
S.insert(mp(p,p));
}
}
B[p] = v;
}
int check(int p,pii t) {
if(t.fi == 4 * N || t.fi == -4 * N) return 0;
if((t.fi <= p && t.se >= p) || (t.fi <= p + N && t.se >= p + N)) return 0;
else return min(t.fi - p,p + N - t.se);
}
int Query(int p) {
if(S.size() == 2) return -1;
auto k = S.lower_bound(mp(p + N / 2,4 * N)),g = k,h = k;
--g;++h;
int res = 0;
pii t = *k;
res = max(check(p,t),res);
t = *g;
res = max(check(p,t),res);
if(h != S.end()) t = *h,res = max(check(p,t),res),++h;
if(g != S.begin()) {
--g;t = *g;res = max(check(p,t),res);
}
if(h != S.end()) {
t = *h;res = max(check(p,t),res);
}
return res;
}
int calc(int a,int b,char op) {
if(op == '*') return a * b % 10;
else return (a + b) % 10;
}
void Solve() {
read(N);read(M);
S.insert(mp(4 * N,4 * N));
S.insert(mp(-4 * N,-4 * N));
for(int i = 1 ; i <= N ; ++i) {
read(A[i]);scanf("%s",ch[i] + 1);
}
A[0] = A[N];
for(int i = 1 ; i <= N ; ++i) {
B[i] = calc(A[i],A[i - 1],ch[i][1]);
}
for(int i = 1 ; i <= N ; ++i) B[i + N] = B[i],A[i + N] = A[i];
int p = -1;
for(int i = 1 ; i <= 2 * N ; ++i) {
if(B[i] == 0) {
if(p == -1) p = i;
}
else if(p != -1) {
S.insert(mp(p,i - 1));
p = -1;
}
}
if(p != -1) S.insert(mp(p,2 * N));
int op,num;char s[5];
for(int i = 1 ; i <= M ; ++i) {
read(op);
if(op == 1) {
read(p);read(num);scanf("%s",s + 1);
++p;
if(p == N) {
Change(1,calc(A[1],num,ch[1][1]));
Change(N + 1,calc(A[1],num,ch[1][1]));
}
else {
Change(p + 1,calc(A[p + 1],num,ch[p + 1][1]));
Change(p + 1 + N,calc(A[p + 1],num,ch[p + 1][1]));
}
A[p] = A[p + N] = num;ch[p][1] = s[1];
Change(p,calc(A[p],A[p - 1],s[1]));
Change(p + N,calc(A[p],A[p - 1],s[1]));
if(p == N) A[0] = num;
}
else {
read(p);++p;
int t = B[p];
Change(p,A[p]);
out(Query(p));enter;
Change(p,t);
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}