牛客little w and Discretization

本文主要是介绍牛客little w and Discretization，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

玩一下样例发现，只要找到mex就可以知道有((1-mex)的值)所在的位置离散化后和原本的值是一样的，所以询问区间的长度-（1-mex）有几个值就是答案，数据范围3e5，莫队+值域分块求区间mex,计算1-mex有几个位置属于这个值域内，a[i] 1e9,但是可以发现a[i]>3e5后离散化必然和原本的值不一样，所以a[i]=3e5+1;

// Problem: little w and Discretization
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19684/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=3e5+9;
const int M=3e5;
int a[N],c[N],bc[N],vis[N],bv[N];
int L[N],R[N],pos[N];
int LL[N],RR[N],PP[N];
int ans[N];
int t,tt;
struct Q{int l,r,id;friend bool operator < (const Q &a,const Q &b){return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;}
}que[N];
//另一种写法
// void modify(int x,int val){// int loc=PP[x];// if(!c[x] && val==1){// vis[x]=1;// bv[loc]++;// }// if(c[x]==1 && val==-1){// vis[x]=0;// bv[loc]--;// }// c[x]+=val;// bc[loc]+=val;
// }
/*
c,bc,vis,bv
*/
void add(int pos){c[a[pos]]++;bc[PP[a[pos]]]++;if(c[a[pos]]==1 && c[a[pos]]==1){bv[PP[a[pos]]]++;vis[a[pos]]=1;}
}
void del(int pos){c[a[pos]]--;bc[PP[a[pos]]]--;if(c[a[pos]]==0 && !c[a[pos]]){bv[PP[a[pos]]]--;vis[a[pos]]=0;}
}
ll query1(int l,int r){int p=PP[l];int q=PP[r];if(p==q){for(int i=l;i<=r;i++){if(!vis[i]){return i;}}}else{for(int i=l;i<=RR[p];i++){if(!vis[i]){return i;}}for(int i=p+1;i<=q-1;i++){///if(bv[i]!=RR[i]-LL[i]+1){for(int j=LL[i];j<=RR[i];j++){if(!vis[j]){return j;}}}}for(int i=LL[q];i<=r;i++){if(!vis[i]){return i;}}}return r+1;
}
ll query2(int l,int r){ll res=0;int p=PP[l];int q=PP[r];if(p==q){for(int i=l;i<=r;i++){res+=c[i];}}else{for(int i=l;i<=RR[p];i++){res+=c[i];}for(int i=p+1;i<=q-1;i++){res+=bc[i];}for(int i=LL[q];i<=r;i++){res+=c[i];}}return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>300000){a[i]=300001;}}t=sqrt(n);for(int i=1;i<=t;i++){L[i]=(i-1)*t+1;R[i]=i*t;}if(R[t]<n){t++;L[t]=R[t-1]+1;R[t]=n;}for(int i=1;i<=t;i++){for(int j=L[i];j<=R[i];j++){pos[j]=i;}}tt=sqrt(M);for(int i=1;i<=tt;i++){LL[i]=(i-1)*tt+1;RR[i]=i*tt;}if(RR[tt]<M){tt++;LL[tt]=RR[tt-1]+1;RR[tt]=M;}for(int i=1;i<=tt;i++){for(int j=LL[i];j<=RR[i];j++){PP[j]=i;}}int m;cin>>m;for(int i=1;i<=m;i++){cin>>que[i].l>>que[i].r;que[i].id=i;}sort(que+1,que+1+m);int l=1,r=0;for(int i=1;i<=m;i++){while(que[i].l>l){del(l++);}while(que[i].l<l){add(--l);}while(que[i].r>r){add(++r);}while(que[i].r<r){del(r--);}ans[que[i].id]=(que[i].r-que[i].l+1)-query2(1,query1(1,M));}for(int i=1;i<=m;i++){cout<<ans[i]<<'\n';}return 0;
}

这篇关于牛客little w and Discretization的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---