SCOI 2015 小凸解密码（stl）

发表于 |
字数统计: 1,658字 | 阅读时长 ≈ 9min

[Scoi2015]小凸解密码

Description

小凸得到了一个密码盘，密码盘被等分成N个扇形，每个扇形上有一个数字(0～9)，和一个符号（“+”或”*”)

密码盘解密的方法如下：

首先，选择一个位置开始，顺时针地将数字和符号分别记在数组A和数组C巾

B0=A0

当x>0时：

若Cx为“+”，Bx=(Ax+Ax-1)%10，注意：x-1是下标

若Cx为“*”，Bx= (Ax×Ax-1)%10,注意：x-1是下标值

操作完成后，可以得到一个长度为n的数组B，然后以B0为起点将B数组顺时针写成一个环，解密就完成了，称得到的环为答案环。

现在小凸得到了一份指令表，指令表上有2种操作。

一种指令是修改操作，即改变原来密码盘上一个位置的数字和符号。

另一种指令是询问操作，具体如下：

首先从指令给出的位置开始完成解密，得到答案环。

答案环上会有一些0连在一起，将这些连在一起的0称为零区间，找出其中距离B0最远的那个零区间，输出这个距离。

零区问和B0的距离定义为：零区问内所有0到B0距离中的最小值。

Input

第1行包含2个整数n,m，代表密码盘大小和指令个数

接下来n行，每行包含1个整数和1个字符，按顺时针顺序给出了密码盘上的数组和符号

接下来m行，依次给出指令

每行第1个整数代表指令类型

若第1个墼数为1，代表本行对应指令为修改操作，之后依次有2个整数pos，num和1个字符opt，分别代表修改的位置，以及修改后该位置的数字和字符

若第1个整数为2，代表本行对应指令位询问操作，之后有1个整数pos，代表本次操作中解密的开始位置

密码盘上的位置标号为0到n-1

数据保证合法，即数据中0≤pos<N，0≤num≤9，opt为“+”或“*”

Output

对于每个询问操作1行，输出答案，若答案环上没有0，输出-1

Sample Input

5 8

0 *

0 *

0 *

0 *

0 *

2 0

1 0 1 +

1 2 1 +

2 3

1 1 1 +

1 3 1 +

1 4 1 +

2 4

Sample Output

0

2

-1

HINT

对于100%数据，$5 <=n，m≤10^5$

这题容易想到直接维护$0$区间，这里可以使用线段树，也可以直接用set。

每次修改的时候在set里面合并或拆分区间，每次查询的时候直接找距离$x+\frac{n}{2}$最近的区间，然后为了减少特判直接查查左右相邻的几个区间取最大值就行了。

口头ac很简单，但由于要处理环，写起来细节很多，比较麻烦。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define N 200005
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
inline void _S(char &c)
{
	c=GC;
	while(c!='+'&&c!='*')c=GC;
}
struct node{int l,r;};
bool operator<(node a,node b)
{
	if(a.l==b.l)return a.r<b.r;
	return a.l<b.l;
}
bool Cross(node a,node b)
{
	if(a.r>=b.l-1)return 1;
	return 0;
}
bool In(int x,node a)
{return a.l<=a.r?(x>=a.l&&x<=a.r):(x<=a.r||x>=a.l);}
node Merge(node a,node b)
{
	return (node){a.l,b.r};
}
set<node>Q;
int n,m,A[N],B[N];
char C[N];
int dis(int x,node a)
{
	if(In(x,a))return 0;
	int p=abs(x-a.l),q=abs(x-a.r);
	p=min(p,n-p);q=min(q,n-q);
	return min(p,q);
}
int f(int a,int b,char c)
{
	if(c=='+')return (a+b)%10;
	return (a*b)%10;
}
void Ins(node t)
{
	Q.insert(t);
	set<node>::iterator it=Q.lower_bound(t),pt;
	pt=it;pt++;
	if(pt!=Q.end()&&Cross(*it,*pt))Q.insert(Merge(*it,*pt)),Q.erase(*pt),Q.erase(*it);
	it=Q.lower_bound(t);
	if(it==Q.end()||!In(t.l,*it))it--;
	if(it!=Q.begin())
	{
		pt=it;pt--;
		if(Cross(*pt,*it))Q.insert(Merge(*pt,*it)),Q.erase(*pt),Q.erase(*it);
	}
	it=Q.begin();pt=Q.end();pt--;
	if(it==pt)return;
	if(it->l==0&&pt->r==n-1)Q.insert(Merge(*pt,*it)),Q.erase(*it),Q.erase(*pt);
}
void Del(int x)
{
	set<node>::iterator it=Q.lower_bound((node){x,x});
	if(it==Q.end())it--;
	if(!In(x,*it))it==Q.begin()?it=--Q.end():it=--it;
	node p=*it;Q.erase(*it);
	if(p.l<=p.r)
	{
		if(x!=p.l)Ins((node){p.l,x-1});
		if(x!=p.r)Ins((node){x+1,p.r});
	}
	else
	{
		if(x!=p.l)Ins((node){p.l,(x-1+n)%n});
		if(x!=p.r)Ins((node){(x+1)%n,p.r});
	}
}
set<node>::iterator Nex(set<node>::iterator a)
{
	a++;if(a!=Q.end())return a;
	else return Q.begin();
}
set<node>::iterator Pre(set<node>::iterator a)
{
	if(a!=Q.begin())return --a;
	return --Q.end();
}
int Gans(int x)
{
	if(!Q.size())return -1;
	int op=x+(n>>1),ans=0;op%=n;
	set<node>::iterator it=Q.lower_bound((node){op,op}),pt;
	ans=max(ans,dis(x,*it));
	pt=Nex(it);ans=max(ans,dis(x,*pt));
	pt=Nex(pt);ans=max(ans,dis(x,*pt));
	pt=Nex(pt);ans=max(ans,dis(x,*pt));
	pt=Nex(pt);ans=max(ans,dis(x,*pt));
	pt=Pre(it);ans=max(ans,dis(x,*pt));
	pt=Pre(pt);ans=max(ans,dis(x,*pt));
	pt=Pre(pt);ans=max(ans,dis(x,*pt));
	pt=Pre(pt);ans=max(ans,dis(x,*pt));
	return ans;
}
int main()
{
	int i,j,k,x,y,New,ans;
	_R(n);_R(m);
	for(i=0;i<n;i++)_R(A[i]),_S(C[i]);
	for(i=0;i<n;i++)B[i]=f(A[i],A[(i-1+n)%n],C[i]);
	for(i=0;i<n;i=j+1)
	{
		j=i;
		if(B[i]!=0)continue;
		while(j+1<n&&B[j+1]==0)j++;
		Ins((node){i,j});
	}
	for(i=1;i<=m;i++)
	{
		_R(k);
		if(k==1)
		{
			_R(x);_R(A[x]);_S(C[x]);
			New=f(A[x],A[(x-1+n)%n],C[x]);
			if(New&&!B[x])Del(x);
			else if(!New&&B[x])Ins((node){x,x});
			B[x]=New;
			New=f(A[x],A[(x+1)%n],C[(x+1)%n]);
			if(New&&!B[(x+1)%n])Del((x+1)%n);
			else if(!New&&B[(x+1)%n])Ins((node){(x+1)%n,(x+1)%n});
			B[(x+1)%n]=New;
		}
		else
		{
			_R(x);
			if(B[x]&&!A[x])
			{
				Ins((node){x,x});
				ans=Gans(x);
				Del(x);
			}
			else if(!B[x]&&A[x])
			{
				Del(x);
				ans=Gans(x);
				Ins((node){x,x});
			}
			else ans=Gans(x);
			printf("%d\n",ans);
		}
	}
}