洛谷P 1972 HHのネックレス
标题:ある区間の色数を問い合わせる
考え方:固定区間では,色数は各種色が初めて現れる位置にのみ関係する.この位置を1とする、この色の残りの位置を0とする.
メンテナンス方法:オフラインで、クエリーを左端でソートします.次の色の場所をクエリーするにはジャンプテーブルnext配列が必要です
考え方:固定区間では,色数は各種色が初めて現れる位置にのみ関係する.この位置を1とする、この色の残りの位置を0とする.
メンテナンス方法:オフラインで、クエリーを左端でソートします.次の色の場所をクエリーするにはジャンプテーブルnext配列が必要です
#include
using namespace std;
typedef long long LL;
typedef pair pii;
typedef pair piii;
const LL maxn =500000 + 100;
const LL maxv =1000000 + 100;
const LL maxq = 500000 + 100;
const LL inf = 0x3f3f3f3f3f3f;
LL vis[maxv],a[maxn],last[maxv],b[maxn],n,ne[maxn],ans[maxq];
vector ve;
void init( LL n ){
for( LL i = 0;i <= n;i++ ) b[i] = 0;
}
LL lowbit( LL x ){
return x &(-x);
}
void add( LL x,LL v ){
for( LL i = x;i <= n;i += lowbit( i ) ){
b[i] += v;
}
}
LL ask( LL x ){
LL re = 0;
while( x ){
re += b[x];
x -= lowbit( x );
}
return re;
}
int main()
{
LL m,x,y;
scanf("%lld",&n);
init(n);
for( LL i = 1;i <= n;i++ ){
scanf("%lld",&a[i]);
}
scanf("%lld",&m);
for( LL i =1;i <= m;i++ ){
scanf("%lld%lld",&x,&y);
ve.push_back( piii( x,pii(y,i) ) );
}
sort( ve.begin(),ve.end() );
memset( vis,0,sizeof( vis ) );
memset( last,0x3f,sizeof( last ) );
for( LL i = n;i >= 1;i-- ){
ne[ i ] = last[ a[i] ];
last[ a[i] ] = i;
}
for( LL i = 1;i <= n;i++ ){
if( !vis[ a[i] ] ){
add( i,1 );
vis[ a[i] ] = 1;
}
}
LL L = 1;
for( LL i = 0;i < ve.size();i++ ){
LL l = ve[i].first;
LL r = ve[i].second.first;
LL id = ve[i].second.second;
if( l > L ){
for( ;L < l;L++ ){
add( L,-1 );
if( ne[L] < inf )
add( ne[L],1 );
}
}
ans[id] = ask( r ) - ask( L-1 );
}
for( LL i = 1;i <= m;i++ ){
printf("%lld
",ans[i]);
}
return 0;
}