linkkkk
题意：
给出一个长度为n的序列，每次询问[ 1 , l ]和[ r , n ]里不同数的个数。
思路：
先求出[ 1 , n ]不同数的个数，每次减去[ l + 1 , r − 1 ]的贡献就好了，莫队维护。
代码：
// Problem: Different Integers // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/20322/J // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7,maxm=1e6+7; int n,m,a[maxn]; struct node{ int id,l,r; }q[maxm]; int cnt[1000010],res[maxn]; int len;//分块的长度 int tot=0; bool cmp(node a,node b){ ///第一关键字是左端点的块编号，第二关键字是右端点的大小 int xa=a.l/len,xb=b.l/len; if(xa==xb) return a.r<b.r; return xa<xb; } void add(int w,int &tot){ if(cnt[w]==0) tot++; cnt[w]++; } void del(int w,int &tot){ cnt[w]--; if(cnt[w]==0) tot--; } bool st[maxn]; void solve(){ int tmp_ans=0; memset(cnt,0,sizeof cnt); for(int i=1;i<=n;i++){ a[i]=read; if(!cnt[a[i]]) tmp_ans++; cnt[a[i]]++; } len=sqrt(n); for(int i=1;i<=m;i++){ q[i].l=read,q[i].r=read;q[i].id=i; } sort(q+1,q+1+m,cmp); tot=tmp_ans; int i=2,j=1;///实际上i在j后面，初始条件表示区间为空 for(int k=1;k<=m;k++){ int id=q[k].id,l=q[k].l,r=q[k].r; if(l==r){ res[id]=tmp_ans;continue; } while(i<r) del(a[i],tot),i++; while(j<l) add(a[j+1],tot),j++; while(j>l) del(a[j],tot),j--; while(i>r) add(a[i-1],tot),i--; res[id]=tot; } for(int i=1;i<=m;i++) cout<<res[i]<<"\n"; } int main(){ while(cin>>n>>m) solve(); return 0; }
