网站建设加网络营销,网架提升公司,洛阳东翔科技做的网站,wordpress导航怎么弄# 与众不同
## 题目描述
A是某公司的CEO#xff0c;每个月都会有员工把公司的盈利数据送给A#xff0c;A是个与众不同的怪人#xff0c;A不注重盈利还是亏本#xff0c;而是喜欢研究「完美序列」#xff1a;一段连续的序列满足序列中的数互不相同。 A想知道区间[L,R]之…# 与众不同
## 题目描述
A是某公司的CEO每个月都会有员工把公司的盈利数据送给AA是个与众不同的怪人A不注重盈利还是亏本而是喜欢研究「完美序列」一段连续的序列满足序列中的数互不相同。 A想知道区间[L,R]之间最长的完美序列长度。
## 输入格式
第一行两个整数N,MN表示连续N个月编号为0到N−1M表示询问的次数 第二行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^50≤L≤R≤N−1∣ai∣≤10^6。 为何唐氏
下标不按正常人习惯走题目背景纯纯脑残sb老板研究牛魔的完美序列。
浪费了一个小时调题强忍着怒火AC了。
核心思路
注意到 list 数组具有单调不减性
AC 代码
#includebits/stdc.h
using namespace std;
const int N 1e68;
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 (lr)/2;build(p*2,l,mid);build(p*21,mid1,r);mx[p] max(mx[p*2],mx[p*21]);nx[p] min(nx[p*2],nx[p*21]);}node query(int p,int left,int right,int l,int r){if(l leftr right){node ans;ans.mx mx[p];ans.nx nx[p];return ans;}int mid (leftright)/2;if(r mid){return query(p*2,left,mid,l,r);}else if(l mid){return query(p*21,mid1,right,l,r);}else{node L query(p*2,left,mid,l,mid);node R query(p*21,mid1,right,mid1,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];
mapint,intcnt;
int find(int L,int r){int le L,ri r;while(le ri){int mid (leri)/2;if(last[mid] L)ri mid;else le mid1;}return le;
}
int main(){//ios::sync_with_stdio(0);int n,m;cinnm;for(int i 1;i n;i){int num;cinnum;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;cinLr;L,r;int x (find(L,r1));if(x r){int ans1 x-L;coutmax(ans1,t.query(1,1,n,x,r).mx)endl;}else{coutr-L1endl;}}
}
