题目描述：
给一个长度不超过1,000,000的数列S。询问Q(Q<100,000)次，在区间[l,r]里，查询最长的元素互不相同的字串的长度。
吐槽：
1.为什么要捉这题呢，因为曾经被这题虐过... 今天在忽然发现原题了，不切一切真是....
2.题目样例错了，没有数据范围... (范围是我自己猜的) 而且有l>r的情况 (果然不靠谱)
3.又是zkw版线段树.... 因为我不会树状数组和朴素版线段树... 是不是只会zkw版的就可以了啊 ..... .... ...
算法分析：
先预处理一遍，对S[i]，计算满足S[j]=S[i]且j<i的最大的j是多少(记为T[i])，不存在记为-1 .... 这个排序一遍就知道了...
然后我们要知道对于S[i]，满足从 S[j]到S[i]都互不相同的最小的j是多少，显然是 max(T[i],T[i-1],...,T[0]) +1，计算这个扫一遍就好了.... (记为P[i])
那么以j结尾的满足题意的最大子串长应该是(i-T[i]+1)，于是我们可以想到用RMQ来搞。
但是必须保证这个以j结尾的子串要完全落在[l,r]中，于是我们只能取满足P[i]>=l的最大值。
由于P是不递减序列，我们二分一个分界点，分界点左边O(1)就可以算出,右边O(log n)求RMQ
加上添加，删除，更新操作ms就要上splay了？？ 求这种题....
1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cstdlib>
5 using namespace std;
6 #define re(i,n) for(int i=0;i<n;i++)
7 #define re3(i,n) for(int i=1;i<n;i++)
8 template <typename T> inline
void chkmax(T &a,
const T b){
if(a<b) a=b;}
9 const int N = 1000005;
10 const int inf = ~0u>>2;
11 struct node{
12 int val,id;
13 }temp[N];
14 bool cmp(node a,node b){
15 return a.val == b.val ? a.id <b.id : a.val <b.val;
16 }
17 int M;
18 int num[N];
19 int seg[N*4];
20 int base[30];
21 int find(
int l,
int r){
22 if(l>r)
return 0;
23 int ans = 0;
24 for(l=M+l-1,r=M+r+1;l^r^1;l>>=1,r>>=1){
25 if(l&1^1) chkmax(ans,seg[l^1]);
26 if(r&1) chkmax(ans,seg[r^1]);
27 }
28 return ans;
29 }
30 int n;
31 void build(){
32 int k;
33 re(i,30)
if(
base[i] > n+1) {k=i;M=
base[i];
break;}
34 re(i,2*M) seg[i] = 0;
35 re(i,n) seg[i+M+1]= i-num[i];
36 for(
int i = k-1; i>=0;i--)
37 for(
int j = 1<<i; j<(1<<i+1);j++)
38 seg[j] = max(seg[j<<1],seg[j<<1^1]);
39 }
40 int main(){
41 int q;
42 base[0] = 1;
for(
int i=1;i<30;i++)
base[i] =
base[i-1]*2;
43 while(~scanf("%d",&n)){
44 re(i,n) {
45 scanf("%d",&temp[i].val);
46 temp[i].id = i;
47 }
48 sort(temp,temp+n,cmp);
49 re(i,n){
50 if(!i || temp[i].val!=temp[i-1].val)
51 num[temp[i].id] = -1;
52 else num[temp[i].id] = temp[i-1].id;
53 }
54 re3(i,n) {
55 chkmax(num[i],num[i-1]);
56 }
57 build();
58 scanf("%d",&q);
59 int a,b;
60 while(q--){
61 scanf("%d%d",&a,&b);
62 if(a>b) swap(a,b);
63 a--;b--;
64 int l = a, r = b+1;
65 while(l<r){
66 int mid= l+r >> 1;
67 if(num[mid] < a) l = mid+1;
68 else r = mid;
69 }
70 int v1 = l-a;
71 int v2 = find(l+1,b+1);
72 printf("%d\n",max(v1,v2));
73 }
74 }
75 }
76 posted on 2012-05-04 22:59
西月弦 阅读(231)
评论(0) 编辑 收藏 引用 所属分类:
解题报告