【唐氏题目 nt题】与众不同

# 与众不同

## 题目描述

A是某公司的CEO，每个月都会有员工把公司的盈利数据送给A，A是个与众不同的怪人，A不注重盈利还是亏本，而是喜欢研究「完美序列」：一段连续的序列满足序列中的数互不相同。  
A想知道区间[L,R]之间最长的完美序列长度。

## 输入格式

第一行两个整数N,M，N表示连续N个月，编号为0到N−1，M表示询问的次数；  
第二行N个整数，第i个数表示该公司第i个月的盈利值ai；  
接下来M行每行两个整数L,R，表示A询问的区间。

## 输出格式

输出M行，每行一个整数对应询问区间内的完美序列的最长长度。

## 样例 #1

### 样例输入 #1

```
9 2
2 5 4 1 2 3 6 2 4
0 8
2 6
```

### 样例输出 #1

```
6
5
```

## 提示

1≤N,M≤2×10^5，0≤L≤R≤N−1，∣ai∣≤10^6。

为何唐氏

下标不按正常人习惯走，题目背景纯纯脑残，sb老板研究牛魔的完美序列。

浪费了一个小时，调题，强忍着怒火AC了。

核心思路

注意到 list 数组具有单调不减性

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+8; 
struct node{int mx,nx;
};
struct sgt{int a[1010000];int mx[4000010],nx[4000010];int n;void build(int p,int l,int r){if(l == r){mx[p] = nx[p] = a[l];return;}int mid = (l+r)/2;build(p*2,l,mid);build(p*2+1,mid+1,r);mx[p] = max(mx[p*2],mx[p*2+1]);nx[p] = min(nx[p*2],nx[p*2+1]);}node query(int p,int left,int right,int l,int r){if(l == left&&r == right){node ans;ans.mx = mx[p];ans.nx = nx[p];return ans;}int mid = (left+right)/2;if(r <= mid){return query(p*2,left,mid,l,r);}else if(l > mid){return query(p*2+1,mid+1,right,l,r);}else{node L = query(p*2,left,mid,l,mid);node R = query(p*2+1,mid+1,right,mid+1,r);node ans;ans.mx = max(L.mx,R.mx);ans.nx = min(L.nx,R.nx);return ans;}}
}t;
int n,m;
int last[N],f[N];
map<int,int>cnt;
int find(int L,int r){int le = L,ri = r;while(le < ri){int mid = (le+ri)/2;if(last[mid] >= L)ri = mid;else le = mid+1;}return le;
}
int main(){//ios::sync_with_stdio(0);int n,m;cin>>n>>m;for(int i = 1;i <= n;i++){int num;cin>>num;last[i] = max(last[i-1],cnt[num]+1);f[i] = i-last[i]+1;cnt[num] = i;t.a[i] = f[i];}t.build(1,1,n);for(int i = 1;i <= m;i++){int L,r;cin>>L>>r;L++,r++;int x = (find(L,r+1));if(x <= r){int ans1 = x-L;cout<<max(ans1,t.query(1,1,n,x,r).mx)<<endl;}else{cout<<r-L+1<<endl;}}
}