好写程度:\(E>D>C\)。
好想程度:\(C>D=E\)。
总结:C 是全场最难。
我们考虑把两个操作对全体的 \(a_i,b_i\) 都做一遍,会发现我们只会做这两遍,不会再有嵌套的了,因为都做过一遍后 \(\{a\}\) 中 0 的数量只会减少,而且即使再做一遍也无法给 \(\{b\}\) 改成不一样的了,比较显然。
下文中令 \(\{a\},\{b\}\) 分别表示修改过的数组,\(\{\overline a\},\{\overline b\}\) 表示原数组。
然后观察我们可以知道,对于任意一对满足 \(r-l>2\) (即区间长度大于等于 4)的 \((l,r)\),\(\{b\}\) 中受影响的只有左右端点,那么 \(\{a\}\) 中受影响的就会是左右边界的各两个字符,所以我们考虑做前缀和,将不受影响的直接前缀和求出,受影响的就直接加上 \(\overline a_l\) 和 \(\overline a_l\),然后结合 \(\overline b\) 和 \(b\) 求出另外两个。
至于区间长度小于 4 的,直接暴力即可。
时间复杂度 \(O(\sum n+\sum q)\)。
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define ull unsigned long long
#define m_p make_pair
#define m_t make_tuple
#define N 200010
using namespace std;
using namespace __gnu_pbds;
int sum[N], n, q;
int A[N], B[N], B1[N];
void all_in()
{ // all in!
char c;
for (int i = 1; i <= n; i++)
{
cin >> c;
sum[i] = A[i] = (c == '1');
}
for (int i = 1; i <= n; i++)
{
cin >> c;
B1[i] = B[i] = (c == '1');
}
return;
}
void mksum()
{
for (int i = 2; i < n; i++)
B1[i] |= !(A[i - 1] | A[i + 1]);
for (int i = 2; i < n; i++)
sum[i] |= (B1[i - 1] & B1[i + 1]);
for (int i = 1; i <= n; i++)
sum[i] += sum[i - 1];
return;
}
void query()
{
int x, y;
while (q--)
{
cin >> x >> y;
if (y == x)
cout << A[x] << "\n";
else if (y - x == 1)
cout << A[x] + A[y] << "\n";
else if (y - x == 2)
cout << A[x] + A[y] + ((B[x] & B[y]) | A[x + 1]) << "\n";
else
cout << sum[y - 2] - sum[x + 1] + A[x] + A[y] + ((B[x] & B1[x + 2]) | A[x + 1]) + ((B[y] & B1[y - 2]) | A[y - 1]) << "\n";
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--)
{
cin >> n;
all_in();
mksum();
cin >> q;
query();
}
return 0;
}
标签:overline,int,题解,sum,long,Machine,B1,CF1978E,define
From: https://www.cnblogs.com/wryyy-233/p/18262380