#C241122E. ABC381E - 11/22 Subsequence

标签（Label）

思维
二分答案
倍增

网址（Website）

E - 11/22 Subsequence (atcoder.jp)

题目（Problem）

问题陈述

本问题中 11/22 字符串的定义与问题 A 和 C 中的定义相同。

当字符串 $T$ 满足以下所有条件时，我们称它为 11/22 字符串：

$|T|$ 是奇数。这里， $|T|$ 表示 $T$ 的长度。
从 $1$ 到 $(\frac{|T|+1}{2} - 1)$ 的字符都是 “1”。
第 $(\frac{|T|+1}{2})$ 字符是/。
第 $(\frac{|T|+1}{2} + 1)$ 到第 $|T|$ 字符都是 “2”。

例如，11/22、111/222和/是 11/22 字符串，但1122、1/222、11/222、22/11和/2/2/211则不是。

给定长度为 $N$ 的字符串 $S$ ，由1、2和/组成，处理 $Q$ 个查询。

每个查询提供两个整数 $L$ 和 $R$ 。假设 $T$ 是 $S$ 中从第 $L$ 到第 $R$ 字符的连续子串。求 $T$ 的不连续子串的最大长度，该子串是一个 11/22 字符串。如果不存在这样的子序列，则打印 0。

限制因素

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$S$ 是长度为 $N$ 的字符串，由 1、2 和 /组成。
$1 \leq L \leq R \leq N$
$N$ 、 $Q$ 、 $L$ 和 $R$ 是整数。

输入

输入信息来自标准输入，格式如下。这里的 $\mathrm{query}_i$ 表示 $i$ -th 查询。

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询按以下格式给出：

$L$ $R$

输出

打印 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

输入样本 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

输出样本 1

对于第一个查询，从 $S$ 的第 $1$ 到第 $7$ 字符的子串是 111/212。这个字符串包含 11/22 作为子串，它是属于 11/22 字符串的最长子串。因此，答案是 $5$ 。

对于第二个查询，从 $S$ 的第 $9$ 到第 $12$ 字符的子串是 1122。这个字符串不包含任何 11/22 字符串的子串，所以答案是 $0$ 。

题解（Solution）

Atcoder 好题。

由大佬 junjunccc 提供的思路，二分答案。

知道答案 $mid$ 之后，直接倍增或二分找出点 $i$ 满足 $s[l:i]$ 中 $1$ 的个数是 $mid$ 个，以及点 $j$ 满足 $s[j,r]$ 中 $2$ 的个数是 $mid$ 个，如果 $i\le j$ 且 $s[i:j]$ 中存在一个 / ，当前 $mid$ 满足条件。

时间复杂度：$O(n\log^2n)$ 。

代码（Code）

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,b) cerr<<a[i]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;

string s;
int a[N],b[N],c[N];
int n,m;
P q[N];

inline int ask1(int l,int r){return a[r] - a[l-1];}
inline int ask2(int l,int r){return b[r] - b[l-1];}
inline int ask(int l,int r){return c[r] - c[l-1];}

void Solve(){
	cin>>n>>m>>s;s=" "+s;
	For(i,1,n) a[i]=a[i-1]+(s[i]=='1');
	For(i,1,n) b[i]=b[i-1]+(s[i]=='2');
	For(i,1,n) c[i]=c[i-1]+(s[i]=='/');
	while(m--){
		int L=rd(),R=rd();
		if(ask(L,R)==0){
			cout<<0<<'\n';
			continue;
		}
		int l=0,r=R-L+1,mid,res=-1;
		while(l<=r){
			mid = (l+r)>>1;
			int i=L-1,j=R+1;
			
			Rof(p,20,0) if(i+(1<<p)<=R && ask1(L,i+(1<<p))<mid) i+=(1<<p);i++;
			Rof(p,20,0) if(j-(1<<p)>=L && ask2(j-(1<<p),R)<mid) j-=(1<<p);j--;
			if(i<=j && ask(i,j)) res=mid, l=mid+1;
			else r=mid-1;
		}cout<<res*2+1<<'\n';
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
    while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}