维护区间出现次数大于2的数的个数
显然可以用莫队来解
和之前那道hhh的项链一样 只不过那道是维护是维护出现一次的数的个数
和那道类似的做法 将询问按 l 排序 将每个出现两次的点维护到最右边即可
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=2e6+10; int t[N]; void add(int x,int v) { for(;x<=N;x+=x&-x)t[x]+=v; } int qsum(int x) { int ans=0;for(;x;x-=x&-x)ans+=t[x];return ans; } struct node { int l,r,id; }s[N]; int nex[N],nnex[N],first[N],a[N],cnt[N],ans[N]; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); rep(i,1,n)scanf("%d",&a[i]); repp(i,n,1) { nex[i]=first[a[i]]; first[a[i]]=i; } rep(i,1,n) nnex[i]=nex[nex[i]]; rep(i,1,n) if(++cnt[a[i]]==2)add(i,1); rep(i,1,k) { scanf("%d%d",&s[i].l,&s[i].r);s[i].id=i; } sort(s+1,s+1+k,[](node a,node b){return a.l<b.l;}); int pos=1; rep(i,1,k) { for(;pos<=s[i].l-1;++pos) { if(nex[pos] )add(nex[pos],-1); if(nnex[pos])add(nnex[pos],1); } ans[s[i].id]=qsum(s[i].r)-qsum(s[i].l-1); } rep(i,1,k) printf("%d ",ans[i]); return 0; }