关于区间内的子区间查询问题的探究

这是一类什么问题，在一个区间内要想求得某个区间，你需要什么样的复杂度？
n*(n-1) /2 ？你需要暴力出所有的情况。
能否找到一个方法使得我们所得到的满足子区间是最优的且一定使我们想要的？
这里存在两种方法：尺取法（两个指针）和二分。

那么先来说说尺取和二分，尺取是固定一边去寻找另一边，同样的看是一个n^2，快的地方是如果满足的一定是r边界的第一个为最优解，那么可以采取这个方法；二分很明显，如果能够得到一个区间的“单调性”或者“边界”，我们可以采取二分。单调性容易看的出来，但是边界问题难以琢磨（二分逼近的侧面边界）

来看题

问题1：https://codeforces.ml/contest/1732/problem/C1

大意是给出一个数组a，给定一个范围l和r，求出在l和r内所能得到的f(l,r)的最大值，存在多个输出区间内数量最少的那一个。f(l,r)定义为区间和 - 区间异或

分析：一个区间内找一个最大值且数量最小区间。需要考虑到一个想法。一个数加上一个数，一定比一个数异或一个数大或者等于。
所以，最大的值一定是l和r 的值。那么只需要找到一个等于它的最小的数量的值就可以了。

采用尺取法：固定左端点，找到第一个右端点符合条件的，更新ans即可。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn = 1e5+10;
ll a[nn];
ll yihuo[nn];
ll s[nn];
void solve()
{
	memset(a,0,sizeof a);
	memset(yihuo,0,sizeof yihuo);
	memset(s,0,sizeof s);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		yihuo[i]=yihuo[i-1]^a[i];
	}
	ll ans = s[n]-yihuo[n];
	int ansl,ansr;
	while(q--){
		cin>>ansl>>ansr;
		int l=ansl,r=ansl;
		ans = (s[ansr]-s[ansl-1]) - (yihuo[ansr]-yihuo[ansl-1]);//区间最大值 
		
		for(l=ansl;l<=ansr;l++){
			if(r<l) r=1;
			while(s[r]-s[l-1]-(yihuo[r]^yihuo[l-1])<ans&&r<=n)//然后找到一个小区间是区间内最大值，其实是排除了一些0和相同的数 
				r++;
			if(r>n) break;
			if(r-l<ansr-ansl)
				ansl = l,ansr = r;
		}
		cout<<ansl<<' '<<ansr<<endl;
	} 
	
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

https://codeforces.ml/contest/1732/problem/C2

题目强化版，查询次数大。
这个就需要考虑规律。因为我们易知0一定是一个不影响的因素，所以我们前后缀记录非0元素，然后循环一定的次数就可以解决这个问题，因为每次我们可以从位上解决问题，而不单单是从计算上解决问题。

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,q,nex[N],pre[N];
long long a[N],b[N];
long long get(int l,int r)
{
	return a[r]-a[l-1]-(b[r]^b[l-1]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>q;
		for (int i=1;i<=n;i++) cin>>a[i];
		int la=0;
		for (int i=1;i<=n;i++)//前缀非0 
		{
			pre[i]=la;
			if (a[i]) la=i;
		}
		la=n+1;
		for (int i=n;i;i--)//后缀非0 
		{
			nex[i]=la;
			if (a[i]) la=i;
		}
		for (int i=1;i<=n;i++) b[i]=b[i-1]^a[i],a[i]+=a[i-1];
		while (q--)
		{
			int l,r;
			cin>>l>>r;
			int al=l,ar=r;
			for (int i=0,p=l;i<35 && p<=r;i++,p=nex[p])//只需要找到一定次数以内前缀或后缀非0 
				for (int j=0,q=r;j<35 && q>=p;j++,q=pre[q])//位运算问题一定要考虑到位的问题 
				{
					if (get(p,q)==get(l,r)) 
					{
						if (q-p<ar-al) al=p,ar=q; 
					}
				}
			if (get(l,r)==0) al=ar=l;//最后特判一下 
			cout<<al<<' '<<ar<<'\n';
		}
	}
	return 0;
}

问题2：https://codeforces.ml/contest/1736/problem/C1

大意是给出一个数组，这个数组有多少个连续的子序列，在重置下标i后，可以使得b[i] >=i ，求这样子序列的数量。

分析：我们易知，在固定以l之后，遇到的第一个不符合条件的之前所有的数都可以以l为起点构造序列。把每个ai作为l，不断的更新r即可。

运用二分的题找不到了，但我很明确在区间内查找的时候是可以存在一个可二分的边界l和r

搜索

标签

存档