2022ICPC亚洲网络选拔赛A.01 Sequence（线段树 | 前缀和）

题目链接：The 2022 ICPC Asia Regionals Online Contest (I) (pintia.cn)

在PTA可以补题。

题意 / Problem

给定一个长度为N的01串，有Q次询问。

对于一个01串，每次可以代价为0的删除任意一个1以及和它相邻的两个数字，或者代价为1的将某个0翻转为1。

注意这个01串是环形的，也就是头尾相连，比如100也可以代价为0的进行一次删除，第1个数字的左边是第N个数字。

每次询问给定一个长度为3的倍数的区间\([l, r]\)，问将这个区间组成的01串删除的最小代价。

思路 / Thought

先考虑对于一个长度为3的倍数的01串，至少需要多少代价能够删完。

考虑一下对于一个1，他可以0代价地带走3个数字，也就是1和它相邻的两个。但是可能出现连续的1，比如一个区间110000，就需要翻转一次，代价为1，因为不管用哪一个1去删除，都会带走一个1，所以我们称这两个连续的1，有效的1只有1个。

不难发现，对于任意一段连续的长度为x的1，有效的1个数为x / 2向上取整，也就是\(ceil(x * 1.0 / 2)\)，当然在C++当中直接写(x + 1) / 2也是向上取整。

那么我们就是要维护一个区间的有效1的个数，对于这么多次的询问，可以用线段树来维护，但是并不是简单地记录“区间内有效1的个数”，因为这是一个环区间，所以应该拆分开来记录，将一个节点记录4个属性：{左连续1个数，除去左右连续1中间部分的有效1个数，右连续1个数，是否全部都是1}。

线段树记录下来之后通过query得到一个Node，再得到这个区间内完整的有效1个数，记录左右连续1是为了合并操作和计算环的完整的有效1个数。

难点在于节点的合并，需要分4中情况，分别是（普遍情况就是“非全1”的情况）：

• 左节点全1，右节点全1
• 左节点全1，右节点普遍
• 左节点普遍，右节点全1
• 左节点普遍，右节点普遍

分这四种情况进行合并，每种情况的合并方法看代码吧。

在query得到一个区间的节点o之后，需要根据o是否是全1来判断有效1的个数，具体看代码里的实现。

最后就是计算了，假如有\(cnt\)个有效1，区间为\([l, r]\)，那么代价应该是\(max(0, (r - l + 1) / 3 - cnt)\)，其中\((r - l + 1) / 3\)表示需要的有效1个数，减去当前有的有效1个数，就是需要翻转的，也就是代价。

方法一代码 / Code 1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;

int a[maxn], N, Q;

struct Node
{
     int cl, c1, cr, all_one;//c1为除去左右连续1有效1的个数，cl, cr分别为左右连续1的个数 
}tree[maxn * 4];

int f(int x){return (x + 1) / 2;}

Node Merge(Node &a, Node &b)
{
	if(a.all_one)//左全1 
	{
		if(b.all_one)//右全1 
		   return {a.cl + b.cl, 0, a.cr + b.cr, 1};
		else//右普遍 
		   return {a.cl + b.cl, b.c1, b.cr, 0};
	}
	else//左普遍 
	{
		if(b.all_one)//右全1 
		   return {a.cl, a.c1, b.cr + a.cr, 0};
		else//右普遍 
		   return {a.cl, a.c1 + b.c1 + f(a.cr + b.cl), b.cr, 0};
	}
}

void build(int s = 1,int e = N, int o = 1)
{
     if(s == e)return tree[o] = (a[s] ? (Node){1, 0, 1, 1} : (Node){0, 0, 0, 0}), void();
     int mid = (s + e) >> 1;
     build(s, mid, o << 1);
     build(mid + 1, e, o << 1 | 1);
     tree[o] = Merge(tree[o << 1], tree[o << 1 | 1]);
}

Node query(int l,int r,int s = 1, int e = N,int o = 1)
{
     if(l <= s && e <= r)return tree[o];
     int mid = (s + e) >> 1;
     if(r <= mid)return query(l, r, s, mid, o << 1);
     else if(l > mid)return query(l, r, mid + 1, e, o << 1 | 1);
     auto res1 = query(l, r, s, mid, o << 1);
     auto res2 = query(l, r, mid + 1, e, o << 1 | 1);
     return Merge(res1, res2);
}

signed main()
{
     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
     
     cin >> N >> Q;
     char s[maxn];cin >> s + 1;
     for(int i = 1;i <= N; ++ i)a[i] = s[i] ^ 48;
     build();
     
     while(Q --)
     {
          int l, r;cin >> l >> r;
          auto o = query(l, r);
          int cnt1 = o.cl == r - l + 1 ? f(o.cl) : o.c1 + f(o.cl + o.cr);
          cout << max(0LL, (r - l + 1 - cnt1 * 3 + 2) / 3) << '\n';
     }
     
     return 0;
}

因为并不需要修改，只需要维护区间的特殊的和，所以用前缀和维护也可以，并且速度比线段树快几倍。

方法二代码 / Code 2

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int a[maxn], pre[maxn], lst[maxn], prefix[maxn], N, Q;

int f(int x){return (x + 1) / 2;}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q;
	char s[maxn];cin >> s + 1;
	for(int i = 1;i <= N; ++ i)a[i] = s[i] ^ 48;
	
	for(int i = 1, j = 0, k = 0;i <= N; ++ i)
	{
		if(!a[i])prefix[i] = prefix[pre[i - 1]] + f(k), j = i, k = 0;
		else ++ k;
		pre[i] = j;
	}
	for(int i = N, j = N + 1;i >= 1; -- i)
	{
		if(!a[i])j = i;
		lst[i] = j;
	}
	while(Q --)
	{
		int l, r;cin >> l >> r;
		int cnt1 = min(f(r - l + 1), prefix[pre[r]] - prefix[lst[l]] + f(r - pre[r] + lst[l] - l));
		cout << max(0LL, (r - l - cnt1 * 3 + 3) / 3) << '\n';
	}
	return 0;
}