[C++] 純文本查看 復制代碼
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
using namespace std;
struct node{
int sum;
int l,r;
};
node data[5000000] = {0,0,0};
inline int sum(int i){ return i?data.sum:0; }
//MEMCT
int _id;
void init(){
_id=0;
}
int copy(int c)
{
int newid = ++_id;
data[newid] = data[c] ;
return newid;
}
//RMQ
int modify(int res,int i,int v,int L,int R)
{
int n = copy(res);
if( L == R )
{
data[n].sum += v;
return n;
}
int M = (L+R)/2;
if( i <= M )data[n].l = modify( data[n].l ,i, v , L , M );
else data[n].r = modify( data[n].r ,i, v ,M+1, R );
data[n].sum = sum(data[n].l) + sum(data[n].r) ;
return n;
}
int query(int r1,int l,int r,int L,int R)
{
if(L==l&&R==r)
return sum(r1);
int M = (L+R)/2;
if( r <= M ) return query( data[r1].l , l , r , L , M );
if( M < l ) return query( data[r1].r , l , r , M+1,R );
return query( data[r1].l , l , M , L , M ) +
query( data[r1].r , M+1,r , M+1,R ) ;
}
int head[ 100001 ];
int last[ 100001 ];
int buf [ 100001 ];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T,tmp,N,M,a,b;
cin>>T;
set<int> st;
map<int,int> mp;
while(T--)
{
cin>>N>>M;
st.clear();
mp.clear();
init();
for(int i=1;i<=N;++i)
{
cin>>buf;
st.insert(buf);
}
tmp=0;
for(int c:st)
mp[c]=tmp++;
for(int i=1;i<=N;++i)
buf=mp[buf];
int L = 0;
int R = N;
//BUILD
memset(last,0,sizeof(last));
for(int i=1;i<=N;++i)
{
int z = last[ buf ];
if( z != 0 )
head = modify(head[i-1],z,-1,L,R);
else
head = head[i-1];
last[ buf ] = i;
head = modify(head,i,1,L,R);
}
while(M--)
{
cin>>a>>b;
if(a>b)swap(a,b);
cout<<query(head,a,b,L,R)<<'\n';
}
}
}
[C++] 純文本查看 復制代碼
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
int a[100010];
int b[100010];
struct ques{
int l,r;
int qid,bid;
}qs[100010];
int ans[100010];
bool cmp(ques a,ques b)
{
if(a.bid!=b.bid) return a.bid<b.bid;
else return a.r<b.r;
}
int mp[100010],cou;
inline void add(int n)
{
if(mp[n]==0)
cou++;
mp[n]++;
// cout<<"add "<<n<<endl;
}
inline void sub(int n)
{
mp[n]--;
if(mp[n]==0)
cou--;
// cout<<"sub "<<n<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a;
//discretization
//discretization way-1-lower_bound (1291 ms)
for(int i=0;i<n;i++)
b=a;
sort(b,b+n);
for(int i=0;i<n;i++)
a=lower_bound(b,b+n,a)-b;
//discretization way-2-pair (1242 ms)
// vector<pair<int,int>> tmp(n);
// for(int i=0;i<n;i++)
// tmp=make_pair(a,i);
// sort(tmp.begin(),tmp.end());
// int lst=0,k=0;
// for(int i=0;i<n;i++)
// {
// if(tmp.first!=lst)k++;
// a[tmp.second]=k;
// lst=tmp.first;
// }
//solve
int K=sqrt(n);
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
qs={l-1,r-1,i,(l-1)/K};
}
sort(qs,qs+m,cmp);
memset(mp,0,sizeof mp);
cou=0;
int l=0,r=-1;
for(int i=0;i<m;i++)
{
while(qs.r>r)
{
r++;
add(a[r]);
}
while(qs.l<l)
{
l--;
add(a[l]);
}
while(qs.r<r)
{
sub(a[r]);
r--;
}
while(qs.l>l)
{
sub(a[l]);
l++;
}
ans[qs.qid]=cou;
}
for(int i=0;i<m;i++)
cout<<ans<<'\n';
}
}