題目描述：
給一個長度不超過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
西月弦 閱讀(252)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告