BZOJ 4556 字符串

发表于 | 更新于

Link

Solution

如果没有S[a:b]S[a:b]中bb端点的限制，那就是直接把prefix[a∼b]prefix[a\sim b]和prefix[c]prefix[c]的 取最值再和d−c+1d-c+1。取min\min。这样的话，需要在rank[]rank[]上，查询rank[c]rank[c]在区间[a,b][a,b]中的前驱和后继。可以树套树或者可持久化 加了bb的限制，那就是一部分 会被截掉一段，可能本来是最长的，截掉之后就不是答案了。 然后通过某些神奇思考得到了二分的办法：对于答案midmid，只会出现在[a,b−mid+1][a,b-mid+1]。这样的话加一个二分答案，就巧妙地避免了限制的干扰，可以直接求rank[c]rank[c]的前驱后继再 $height[]$了。 另外，主席树的前驱后继似乎不好像平衡树那样直接走一遍，因为在上面不知道下面的某些点是否存在。

Tips

写出了形式化的条件，但没有想到二分答案的处理策略 应该是想一下去掉限制的想出主席树，再加上限制更容易得到二分答案.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "lucida"
#include "lucida"
using std::min;
using std::max;
using std::partial_sum;
using std::swap;
using std::fill;
const int MAXN=100000+11,LOG=20,INF=0x1f1f1f1f;
int log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i)
		log_2[i]=log_2[i>>1]+1;
}}Auto;
//写出了形式化的条件，但没有想到二分答案的处理策略
//应该是想一下去掉限制的想出主席树，再加上限制更容易得到二分答案.
namespace segTree {//兹瓷在区间中查询数的前驱后继
	const int SIZE=20*MAXN;
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node(int cnt):cnt(cnt) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
	}*_null=null=new Node(0),*_null_son=null->son[0]=null->son[1]=null;
	const int MODE_PRED=1,MODE_SUCC=0;
	struct SegTree {
		Node **root;int n,L,R;
		void Edit(Node *&pos,int L,int R,const int goal) {
			pos=new Node(*pos);//new Node(0)??
			if(L==R) pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal);
				else Edit(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
		int Lowc(Node *pl,Node *pr,int L,int R,const int num) {
			if(L==R) return L<=num && pr->cnt-pl->cnt;// && [...
			else {
				int Mid=(L+R)>>1;
				if(num<=Mid) return Lowc(pl->son[0],pr->son[0],L,Mid,num);
				else return pr->son[0]->cnt-pl->son[0]->cnt+Lowc(pl->son[1],pr->son[1],Mid+1,R,num);
			}
		}
		int Kiss(Node *pl,Node *pr,int L,int R,int K) {
			if(L==R)
				return L;
			else {
				int Mid=(L+R)>>1,sum=pr->son[0]->cnt-pl->son[0]->cnt;
				if(K<=sum) return Kiss(pl->son[0],pr->son[0],L,Mid,K);
				else return Kiss(pl->son[1],pr->son[1],Mid+1,R,K-sum);
			}
		}
		SegTree(){}SegTree(int n,int L,int R,int a[]):n(n),L(L),R(R) {
			root=alloc(Node*,n+1);root[0]=null;
			for(int i=1;i<=n;++i)
				Edit(root[i]=root[i-1],L,R,a[i]);
		}
		int Rank(int l,int r,int num) {
			return Lowc(root[l-1],root[r],L,R,num)+1;
		}
		int Kiss(int l,int r,int K) {
			return K<=r-l+1 && K>=1?Kiss(root[l-1],root[r],L,R,K):-1;
		}
	};
}using segTree::SegTree;
struct SA {
	int rnk[MAXN],sa[MAXN],height[MAXN],st[LOG][MAXN],n;
	SA(){}SA(char *s,int n,int m):n(n) {
		static int temp[2][MAXN],*x=temp[0],*y=temp[1],cnt[MAXN];
		fill(cnt+1,cnt+1+m,0);
		for(int i=1;i<=n;++i) cnt[x[i]=s[i]]++;
		partial_sum(cnt+1,cnt+1+m,cnt+1);
		for(int i=n;i;--i) sa[cnt[x[i]]--]=i;
		for(int len=1;len<n;len<<=1) {
			int p=0;
			for(int i=n-len+1;i<=n;++i) y[++p]=i;
			for(int i=1;i<=n;++i) if(sa[i]-len>0) y[++p]=sa[i]-len;
			fill(cnt+1,cnt+1+m,0);
			for(int i=1;i<=n;++i) cnt[x[y[i]]]++;
			partial_sum(cnt+1,cnt+1+m,cnt+1);
			for(int i=n;i;--i) sa[cnt[x[y[i]]]--]=y[i];
			swap(x,y);p=0;
			for(int i=1;i<=n;++i)
				x[sa[i]]=y[sa[i-1]]==y[sa[i]] && (sa[i-1]+len<=n?y[sa[i-1]+len]:0)==(sa[i]+len<=n?y[sa[i]+len]:0)?p:++p;
			if((m=p)==n) break;
		}
		for(int i=1;i<=n;++i) rnk[sa[i]]=i;
		for(int i=1,len=0;i<=n;++i)
			if(rnk[i]!=1) {
				int j=sa[rnk[i]-1];
				while(s[i+len]==s[j+len]) len++;
				height[rnk[i]]=len;
				len-=(bool)len;
			}
		for(int i=1;i<=n;++i)
			st[0][i]=height[i];
		for(int lg=1;lg<=log_2[n];++lg)
			for(int i=1;i<=n-(1<<lg)+1;++i)
				st[lg][i]=min(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]);
#ifdef debug
		for(int i=1;i<=n;++i)
			os<<i<<' '<<sa[i]<<' '<<height[i]<<' '<<(s+sa[i])<<'\n';
#endif
	}
	int operator () (int p1,int p2) {
		if(p1==p2) return n-p1+1;
		if((p1=rnk[p1])>(p2=rnk[p2])) swap(p1,p2);
		++p1;int lg=log_2[p2-p1+1];
		return min(st[lg][p1],st[lg][p2-(1<<lg)+1]);
	}
}sa;
SegTree seg;int n;
bool Check(int len,int a,int b,int c) {
	int l=a,r=b-len+1,rnk=seg.Rank(l,r,sa.rnk[c]),
		p1=seg.Kiss(l,r,rnk-1),
		p2=seg.Kiss(l,r,rnk);//查到了不存在的东西。没有测合法
	return max(~p1?sa(sa.sa[p1],c):0,~p2?sa(sa.sa[p2],c):0)>=len;
}
int Solve(int a,int b,int c,int d) {
	int L=0,R=min(d-c+1,b-a+1);
	while(L!=R) {
		int Mid=(L+R+1)>>1;
		if(Check(Mid,a,b,c)) L=Mid;
		else R=Mid-1;
	}
	return L;
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXN];
	int m;is>>n>>m;
	is>>(s+1);new(&sa) SA(s,n,255);
	new(&seg) SegTree(n,1,n,sa.rnk);
	for(int i=1;i<=m;++i) {
		int a,b,c,d;is>>a>>b>>c>>d;
		int Ans=Solve(a,b,c,d);
		os<<Ans<<'\n';
	}
	return 0;
}
//11:28 finished