1 条题解

  • 0
    @ 2021-8-27 17:35:24

    传送门

    欢迎踩博客

    前置知识:

    SA 数组。

    题意:

    • 给出 nn 个在 [1,n][1,n] 内的数 aia_i

    • qq 次询问,每次给出 s,l,rs,l,r,问是否 b[1,n]\exists b\in[1,n] 使 k[0,rl]\forall k\in[0,r-l]al+k+ab+k=sa_{l+k}+a_{b+k}=s

    • n,q4×105n,q\le4\times10^5

    为叙述方便,设以 ss 的第 ii 个元素为首个元素的后缀为 suff(s,i)\operatorname{suff}(s,i)

    分析:

    • Subtask 0:n,q500n,q\le500

    暴力枚举每一个 bb 进行判断。

    • Subtask 1:n,q8×103n,q\le8\times10^3

    O(nq)O(nq) 的 KMP 写法,并不是正解。

    对于每一个询问,设 ck=sal+kc_k=s-a_{l+k}k[0,rl]k\in[0,r-l]),那么如果存在 bb 满足 ab+k=cka_{b+k}=c_k,就满足条件,否则不满足。

    原问题转换成了能否在 aa 中找到一个子串和 cc 相同,可以用 KMP 解决。这个过程是 O(n)O(n) 的,qq 次询问就是 O(nq)O(nq)

    这个 Subtask 虽然和正解使用的算法不同,但对思路有一定帮助。

    • Subtask 2:ss 相同。

    ss 相同,就说明 sais-a_i 相同。所以每次得出的 cc 是另一个串 dddi=said_i=s-a_i) 的子串。问题转换成求 dd 的一个子串是否在 aa 中出现过。

    ddaa 一起求 SA,假设询问的 dd 的子串是 dl,dl+1,,drd_l,d_{l+1},\dots,d_r,那么只需要判断 suff(d,l)\operatorname{suff}(d,l)aa 的所有后缀的 lcp 的最大值是否不小于 rl+1r-l+1 即可。

    可以二分求以 ll 开始的后缀在 rank 中的前驱和后继,复杂度 O((n+q)logn)O((n+q)\log n),已经能过了。

    • Subtask 3:无限制。

    注意到 al+k+ab+k=sa_{l+k}+a_{b+k}=sal+k+1+ab+k+1=sa_{l+k+1}+a_{b+k+1}=s 可以推出 (al+k+1al+k)+(ab+k+1ab+k)=0(a_{l+k+1}-a_{l+k})+(a_{b+k+1}-a_{b+k})=0,即差分数组是相反数。

    求出差分数组 aa' 以及差分的相反数数组 dd'。问题等价于求所有满足 ab+al=sa_b+a_l=ssuff(d,b)\operatorname{suff}(d',b)suff(a,l)\operatorname{suff}(a',l) 的最长公共前缀的最大值是否不小于 rlr-l

    以样例为例,各数组如下表:

    ii 1 2 3 4 5 6
    aa 1 3 4 2 1
    aa' 0 2 1 -2 -1 /
    dd' -2 -1 2 1

    对于询问三,suff(a,l)={2,1}\operatorname{suff}(a',l)=\{-2,-1\}

    满足 ab+al=sa_b+a_l=sbb112266。所有 suff(d,b)\operatorname{suff}(d',b) 为:suff(d,1)={0,2,1,2,1}\operatorname{suff}(d',1)=\{0,-2,-1,2,1\}suff(d,2)={2,1,2,1}\operatorname{suff}(d',2)=\{-2,-1,2,1\}suff(d,6)={}\operatorname{suff}(d',6)=\{\}

    其中 suff(d,2)\operatorname{suff}(d',2)suff(a,4)\operatorname{suff}(a',4) 的公共前缀长度为 22。这意味着 a2+a4=0a'_2+a'_4=0a3+a5=0a'_3+a'_5=0,并且由于因为已经保证了 a2+a4=sa_2+a_4=s,所以:

    a3+a5=(a2+a2)+(a4+a4)=sa_3+a_5=(a_2+a'_2)+(a_4+a'_4)=sa4+a6=(a3+a3)+(a5+a5)=sa_4+a_6=(a_3+a'_3)+(a_5+a'_5)=s,满足条件。

    注意到所有 ab+al=sa_b+a_l=saba_b 是相同的废话,所以可以对于每一个 vv,将所有 ab=va_b=vbb 放在一个数组里,按 rank 排序,询问时二分 suff(a,l)\operatorname{suff}(a',l) 的 rank 在哪个位置即可。


    思路:

    • 求出差分数组与差分的相反数数组。

    • 对于每一个询问,求出 $\max\limits_{a_b+a_l=s}\{\operatorname{lcp}(\operatorname{suff}(a',l),\operatorname{suff}(d',b))\}$ 是否不小于 rlr-l


    #include <bits/stdc++.h>
    #define rep(i, l, r) for(int i=l; i<=r; ++i)
    #define rrep(i, r, l) for(int i=r; i>=l; --i)
    #define ll long long
    #define il inline
    #pragma GCC diagnostic ignored "-Wparentheses"
    using namespace std;
    const int mN=4e5+100, mM=2*mN, mD=21;
    il int read() {
    	int res=0; char c=getchar(); while(c<'0' || c>'9') c=getchar();
    	while(c>='0' && c<='9') res=(res<<1)+(res<<3)+(c^48), c=getchar(); return res;
    }
    il int max_(int a, int b) {return a>b? a: b;}
    il int min_(int a, int b) {return a<b? a: b;}
    int n, q, m, a[mN], lg[mM], mn[mD][mM], f[mN], fl[mN], fr[mN];
    int c[mM];
    il int cal_min(int l, int r) {return min(mn[lg[r-l+1]][l], mn[lg[r-l+1]][r-(1<<lg[r-l+1])+1]);}
    
    //begin 板子
    int ork, rk[2][mM*2], rak[mM], sa[mM], lcp[mM], buc[mM], tmp1[mM], tmp2[mM]; 
    il void get_buc(int *a) {
    	rep(i, 0, ork) buc[i]=0;
    	rep(i, 1, m) ++buc[a[i]];
    	rep(i, 1, ork) buc[i]+=buc[i-1];
    }
    void get_sa() {
    	rep(i, 1, m) rk[0][i]=c[i];
    	int t=0; ork=m;
    	for(; t<=lg[m]; ++t) {
    		get_buc(rk[t&1]+(1<<t));
    		rep(i, 1, m) tmp1[buc[rk[t&1][i+(1<<t)]]--]=i;
    		get_buc(rk[t&1]);
    		rrep(i, m, 1) tmp2[buc[rk[t&1][tmp1[i]]]--]=tmp1[i];
    		ork=0;
    		rep(i, 1, m) {
    			if(rk[t&1][tmp2[i]]!=rk[t&1][tmp2[i-1]] || rk[t&1][tmp2[i]+(1<<t)]!=rk[t&1][tmp2[i-1]+(1<<t)]) ++ork;
    			rk[t&1^1][tmp2[i]]=ork;
    		}
    		if(ork==m) {++t; break;}
    	}
    	rep(i, 1, m) sa[rak[i]=rk[t&1][i]]=i;
    }
    #define j lcp[rak[i]]
    il void get_lcp() {rep(i, 1, m) for(j=max_(lcp[rak[i-1]]-1, 0); c[i+j]==c[sa[rak[i]+1]+j]; ++j);}
    #undef j
    //end 板子 
    
    il bool sol(int s, int l, int r) {	//处理询问 (s,l,r) 
    	int v=s-a[l], L=fl[v], R=fr[v];
    	if(v<=0 || v>n || fl[v]>fr[v]) return 0;	//没有 a[i]=v, 直接返回 
    	while(L<=R) if(f[L+R>>1]<rak[l]) L=(L+R>>1)+1; else R=(L+R>>1)-1;	//二分 rak[l] 的位置 
    	//二分的结果满足 f[R]<rak[l]<f[L] 
    	return max_(fl[v]<=R? cal_min(f[R], rak[l]-1): 0, L<=fr[v]? cal_min(rak[l], f[L]-1): 0)>=r-l;
    	//如果在范围内就求 lcp,否则为 0 
    }
    int main() {
    	n=read(), q=read(), m=2*n;
    	rep(i, 2, m) lg[i]=lg[i>>1]+1;
    	rep(i, 1, n) a[i]=read();
    	rep(i, 1, n-1) c[i]=a[i+1]-a[i]+n+1, c[i+n]=a[i]-a[i+1]+n+1;	//c[1]~c[n] 为 a', c[n+1]~c[2n] 为 d' 
    	c[n]=c[m]=1;
    	get_sa(), get_lcp();	//SA
    	rep(i, 1, m) mn[0][i]=lcp[i];
    	rep(t, 1, lg[m]) rep(i, 1, m-(1<<t)+1) mn[t][i]=min_(mn[t-1][i], mn[t-1][i+(1<<t-1)]);	//ST
    
    	rep(i, 0, n) buc[i]=0;
    	rep(i, 1, n) ++buc[a[i]];
    	rep(i, 1, n) buc[i]+=buc[i-1];
    	rep(i, 1, n) fl[i]=buc[i-1]+1, fr[i]=buc[i];	//值为 v 的 a[i] 在 fl[v] 到 fr[v] 的范围内 
    	rep(i, 1, n) f[buc[a[i]]--]=rak[i+n];	//把 a[i]=v 的 rank[d'[i]] 放进 f[fl[v]~fr[v]] 
    	rep(i, 1, n) if(fl[i]<=fr[i]) sort(f+fl[i], f+fr[i]+1);
    	int s, l, r;
    	do s=read(), l=read(), r=read(), puts(sol(s, l, r)? "Yes": "No"); while(--q);
    	return 0;
    }
    

    特别申明:本题解为团队成员 ATue 所写。

    • 1

    信息

    ID
    184
    时间
    800ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    24
    已通过
    10
    上传者