poj 3419 Difference Is Beautiful (有点思维的题。预处理很强大)
Difference Is BeautifulTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 1863 Accepted: 569
Description
Mr. Flower's business is growing much faster than originally planned. He has now become the CEO of a world-famous beef corporation. However, the boss never lives a casual life because he should take charge of the subsidiary scattered all over the world. Every year, Mr. Flower needs to analyze the performance reports of these subsidiary companies.
Mr. Flower has N companies, and he numbered them with 0 to N – 1. All of the companies will give Mr. Flower a report about the development each year. Among all of the tedious data, only one thing draws Mr. Flower's attention – the turnover. Turnover of a company can be represented as an integer Pi: positive one represents the amount of profit-making while negative for loss-making.
In fact, Mr. Flower will not be angry with the companies running under deficit. He thinks these companies have a large room for future development. What dissatisfy him are those companies who created the same turnover. Because in his eyes, keeping more than one companies of the same turnover is not necessary.
Now we know the annual turnover of all companies (an integer sequence Pi, the ith represents the turnover of the ith company this year.). We say a number sequence is perfect if all of its numbers are different from each other. Mr. Flower wants to know the length of the longest consecutive perfect sequence in a certain interval [L, R] of the turnover sequence, can you help him?
Input
The first line of the input contains two integers N and M. N is the number of companies. M is the number of queries. (1 ≤ N, M ≤ 200000). The second line containsN integer numbers not exceeding 106 by their absolute values. The ith of them represents the turnover of the ith company this year. The following M lines contain query descriptions, each description consists of two numbers: L, R (0 ≤ L ≤ R ≤ N – 1) and represents the interval that Mr. Flower concerned.
Output
The output contains M lines. For each query, output the length of the longest consecutive perfect sequence between [L, R]
Sample Input
9 22 5 4 1 2 3 6 2 40 82 6
Sample Output
65
Hint
The longest perfect sequence of the first query in the sample input is '5 4 1 2 3 6', so the answer for this query is 6.Source
POJ Monthly--2007.10.06, SHOIT@ZSU题意：
给你你含n个整数的数组。整数的绝对值不超过10^6.然后给你q组询问。每组询问。给你一个区间l,r。问你这个区间内
最长连续无重复(没有相同的数字)序列的长度。
思路：
由于查询操作很多。所以只有在预处理上下工夫。用数组p[]来记录数组中的整数。用ml[i]表示以角标i结尾的最长无重复序列的长度。rep[i]表示i结尾的最长无重复序列与前面序列重复元素的位置。维护这个数组方便后面的询问区间定位。
详细见代码：
#include <iostream>#include<stdio.h>#include<string.h>using namespace std;const int maxn=200010;const int up=1000000;//把负数转化为正数int p[maxn],ml[maxn],rep[maxn];bool vis[2000010];//判重int main(){ int n,q,i,tt,pp,l,r,ans; while(~scanf("%d%d",&n,&q)) { memset(vis,0,sizeof vis); for(i=0;i<n;i++) scanf("%d",p+i); ml[0]=1; rep[0]=0; vis[p[0]+up]=true; for(i=1;i<n;i++) { tt=p[i]+up; if(!vis[tt]) { ml[i]=ml[i-1]+1; rep[i]=rep[i-1]; vis[tt]=true; } else { pp=i-ml[i-1];//p-1-ml[i-1]+1.pp为以i-1结尾的序列(简写)的首元素 while(p[pp]!=p[i])//找到重复元素。重复元素之前的元素都不能要 { vis[p[pp]+up]=false; pp++; } ml[i]=i-pp;//以i结尾序列的长度 rep[i]=i;//和前面序列重复的自己 } //printf("ml[%d] %d\n",i,ml[i]); } while(q--) { scanf("%d%d",&l,&r); ans=0; while(1) { if(r-l+1<=ans) break; ans=max(ans,min(ml[r],r-l+1)); r=rep[r]-1; } printf("%d\n",ans); } } return 0;}