记录一下 atcoder 的一些解题思路和代码。

abc370

A/B: 直接模拟。

C: 贪心。可以得知，先从前往后扫，把 ${S_i > T_i}$ 的依次修改；再从后往前扫，把 ${S_i < T_i>}$ 的依次修改；这样就可以得到字典序最小的字符串数组。

D: 模拟。对每一行、每一列都开一个set，二分查找最近的一堵墙，然后删除。

E: DP。设 ${dp_i}$ 为以 $i$ 结尾的方案数，则有方程 ${dp_i = \sum_{sum(j+1,i)!=k}dp_j}$。考虑优化，正难则反，那么可以考虑统计所有的 ${j:(1\le j \le i-1)}$ 符合 $sum(j+1,i)=k$的情况，并记录下来。

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
#include <bits/stdc++.h>
using namespace std;
const int Maxn=2e5+5,mod=998244353;
long long n,k;
long long a[Maxn];
long long f[Maxn];
map<long long ,long long> bot;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	f[0]=1;
	bot[0]=1;
	long long nowsum=1;
	long long sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		long long tmp=0;
		if(bot.find(sum-k)!=bot.end())
		{
			tmp = bot[sum-k];
		}
		f[i] = (nowsum + mod - tmp)%mod;
		nowsum += f[i];nowsum%=mod;
		bot[sum] += f[i];bot[sum]%=mod;
	}
	cout<<f[n]<<"\n";
	return 0;
}

F: 二分+拆环成链+倍增优化。对于每个值 $mid$ ，考虑把环拆成链。如果对于每个 位置，要遍历全部判定的话，效率会变成 $O(n^2)$ ；所以这里用倍增去跳。

设 $dp_{i,j}$ 为 跳 $2^j$ 次能到达的最近的一个位置。（符合条件下）按倍增的思路，则有 ${dp_{i,j} = dp_{dp_{i,j-1},j-1} }$ 。

注意数组大小。

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
#include <bits/stdc++.h>
using namespace std;
const int Maxn=4e5+5;
long long n,k;
long long a[Maxn];
long long sum[Maxn];
long long dp[Maxn][31];
pair<long long ,bool> check(int mid)
{
	for(int i=1,j=1;i<=(n<<1);i++)
	{
		while(j<(n<<1)&&sum[j]-sum[i-1]<mid) j++;
		dp[i][0]=j+1;
	}
	dp[(n<<1|1)][0]=(n<<1|1);

	for(int j=1;j<=20;j++)
	{
		for(int i=1;i<=(n<<1|1);i++)
		{
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
	bool flag=false;
	long long res=0;
	for(int i=1;i<=n;i++)
	{
		int pos = i;
		for(int j=20;j>=0;j--)
		{
			if(k&(1<<j))
			{
				pos = dp[pos][j];
			}
		}
		if(pos<=i+n)
		{
			flag=true;
		}
		else
		{
			res++;
		}
	}
	return make_pair(res,flag);
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[n+i]=a[i];
	}
	for(int i=1;i<=(n<<1);i++)
	{
		sum[i] = sum[i-1] + a[i];
	}
	long long l=1,r=2e9;
	long long res=-1;
	long long res2=-1;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		pair<long long ,bool> ck = check(mid);
		if(ck.second)
		{
			l=mid+1;
			res=mid;
			res2=ck.first;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<res<<" "<<res2<<"\n";
	return 0;
}

abc 371

A: 其实只需要三个判断！如果是 $B$ 的话，那么就是 ${s1=s2 :and: s2=s3}$ ，否则，只符合前者的是 $C$ ，只符合后者的是 $A$ 。

B: 按题意模拟。

C: 看数据范围，可知可以直接枚举节点 $1-n$ 的全排列，再答案统计。

D: 离散化+前缀和。离线读取数据，将所有坐标离散化，用前缀和实现区间查询。

E: 计数。考虑对每一类数对答案贡献，发现贡献如下：

令 ${T_n = (1+n)*n/2}$ ，$M_i$ 为两个该种数字每一段间隔的长度（包括头和尾的空段）。则对每种数字有贡献：

$$
Ans = T_n - \Sigma T_{M_i}
$$

效率为 $O(n)$

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
#include <bits/stdc++.h>
using namespace std;
const int Maxn=2e5+5;
int n;
int Pos[Maxn];
int nxt[Maxn];
long long T[Maxn];
bool vis[Maxn];
int main()
{

	cin>>n;
	for(int i=1;i<=n;i++) T[i] = (long long) (1+i)*i/2;
	long long res=0;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		nxt[Pos[x]] = i;
		Pos[x] = i;
		if(!vis[x])
		{
			res+=T[n];
			vis[x]=1;
		}
	}
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			res -= T[i-1];
			vis[i]=true;
		}
		if(!nxt[i])
		{
			res-= T[n-i];
		}
		else
		{
			res -= T[nxt[i]-1-i];
			vis[nxt[i]] = true;
		}
	}
	cout<<res<<"\n";
	return 0;
}

F: 二分+线段树。

按题意模拟，考虑暴力修改。这里只讨论向右边走的情况，向右走需要找到一整段需要修改的最右边的那个人，如何判定？

设当前向右走的人是第 $x$ 个人，需要走到的坐标为 $G$，如果第 $y$ 个人需要被挪动，那么挪动后的位置应该为：$G+y-x$

若当前位置 $Pos(y)<G+y-x$ 则需要被挪动。

二分查找找到最右边的这个人即可。效率为 $O(nlog^2n)$

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <bits/stdc++.h>
using namespace std;
const int Maxn=2e5+5;
int n,q;
int X[Maxn];
int Tree[Maxn<<2];
void spread(int p)
{
	if(Tree[p])
	{
		Tree[p<<1]=Tree[p<<1|1]=Tree[p];
		Tree[p]=0;
	}
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		Tree[p]=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
int ask_num(int p,int l,int r,int x)
{
	if(l==r)
	{
		return Tree[p];
	}
	int mid=(l+r)>>1;
	spread(p);
	if(x<=mid)
	{
		return ask_num(p<<1,l,mid,x);
	}
	else
	{
		return ask_num(p<<1|1,mid+1,r,x);
	}
}

int get_pos(int x)
{
	int res = ask_num(1,1,n,x);
	return X[res]+(x-res);
}

void update(int p,int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R)
	{
		Tree[p] = x;
		return ;
	}
	int mid=(l+r)>>1;
	spread(p);
	if(L<=mid)
	{
		update(p<<1,l,mid,L,R,x);
	}
	if(R>mid)
	{
		update(p<<1|1,mid+1,r,L,R,x);
	}
}

long long ans = 0;

long long calc(int l,int r)
{
	long long res=0;
	int nowR = r;
	int nowL = 0;
	while(nowR>=l)
	{
		nowL = max(ask_num(1,1,n,nowR),l);
		res += (long long) (get_pos(nowL)+get_pos(nowR))*(nowR-nowL+1)/2;
		nowR = nowL-1;
	}
	return res;
}

void Go_Right(int x,int G)
{
	int l=x,r=n;
	int y=-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(get_pos(mid)<=G+mid-x)
		{
			y=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	ans-=calc(x,y);
	update(1,1,n,x,y,x);
	X[x] = G;
	ans+=calc(x,y);
}

int Find_Right(int x)
{
	int l=x+1,r=n;
	int res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(ask_num(1,1,n,mid)<=x)
		{
			res=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	return res;
}

void Go_Left(int x,int G)
{
	int l=1,r=x;
	int y=-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(G-x+mid<=get_pos(mid))
		{
			r=mid-1;
			y=mid;
		}
		else
		{
			l=mid+1;
		}
	}

	int z = Find_Right(x);
	if(z!=0)
	{
		X[x+1] = get_pos(x+1);
		update(1,1,n,x+1,z,x+1);
	}
	ans+=calc(y,x);
	X[y] = G-x+y;
	update(1,1,n,y,x,y);
	ans-=calc(y,x);
}
/*
想找需要修改的最右边那个人。

如何找？

如果第 y 个人，如果需要被挪动，那么挪动后的位置应该是：G+y-x
若当前位置 get_pos(y)<G+y-x 则需要被挪动。


G-x+y

G-x+y<get_pos(y)

*/

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>X[i];
	}
	build(1,1,n);
	cin>>q;
	while(q--)
	{
		int T,G;
		cin>>T>>G;
		int nowP = get_pos(T);
		if(nowP<G)
		{
			Go_Right(T,G);
		}
		else if(nowP>G)
		{
			Go_Left(T,G);
		}
	}
	cout<<ans<<"\n";
	return 0;
}