Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 那位大牛 能够帮忙看一下 为什么总是超时

Posted by jiasen_huo at 2011-12-10 16:40:56 on Problem 3419
```#include <iostream>
using namespace std;

int *data,*same,*cur;
int appear[2000001];
void getSame(int n)
{
same[n-1]=1;appear[1000000+data[n-1]]=n-1;cur[n-1]=-1;
for(int i=n-2;i>=0;i--)
{
if(appear[1000000+data[i]]==0)
{
same[i]=same[i+1]+1;
appear[1000000+data[i]] = i;
cur[i] = cur[i+1];
}
else
{
int tem = appear[1000000+data[i]];
if(tem<=(i+same[i+1]))
{
same[i]=tem-i;
cur[i] = i+1;
}
else
{
same[i]=same[i+1]+1;
cur[i] = cur[i+1];
}
appear[1000000+data[i]] = i;
}
}

//cout<<"the same: ";
//for(int i=0;i<n;i++)
//	cout<<same[i]<<" ";
//cout<<endl;

}
int main()
{
int n,m;
cin>>n>>m;
data = new int[n];
same = new int[n];
cur  = new int[n];
for(int i=0;i<n;i++)
{
cin>>data[i];
}
getSame(n);
for(int i=0;i<m;i++)
{
int s,t;
cin>>s>>t;
int max=0;
for(int j=s;j<=t;j=cur[j])
{
if(j==-1)break;
int temp = same[j];
if(temp>(t-j+1))
{
temp = t-j+1;
if(temp>max)
{
max = temp;break;
}
}
if(temp>max)max=temp;
}
cout<<max<<endl;
}
//getchar();
return 0;
}```

Followed by: