算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    给一个长度不超过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 西月弦 阅读(185) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理