牛客網Different Integers題解
4663 ワード
タイトルの説明
Given a sequence of integers a1, a2, ..., an and q pairs of integers (l1, r1), (l2, r2), ..., (lq, rq), find count(l1, r1), count(l2, r2), ..., count(lq, rq) where count(i, j) is the number of different integers among a1, a2, ..., ai, aj, aj + 1, ..., an.
説明の入力
The input consists of several test cases and is terminated by end-of-file.The first line of each test cases contains two integers n and q.The second line contains n integers a1, a2, ..., an.The i-th of the following q lines contains two integers li and ri.
出力の説明
For each test case, print q integers which denote the result.
サンプル入力
3 2
1 2 1
1 2
1 3
4 1
1 2 3 4
1 3サンプル出力
2
1
3コメント
* 1 ≤ n, q ≤ 105
* 1 ≤ ai ≤ n
* 1 ≤ li, ri ≤ n
* The number of test cases does not exceed 10.意味の理解
問題はN個の数,Q回のクエリ,各クエリ区間[1,l]と[r,n]の間の異なる数の数を与える.
考える
Q回のクエリは,範囲が10^5であり,時間的複雑度O(N)が外部ループで予め定められている.hash配列で重複を記録すると,その区間のヘッダ列挙から末尾まで異なる数を求めるたびに,更新複雑度を1クエリー複雑度をNとするか,更新複雑度をNクエリー複雑度を1とするか,時間複雑度をO(N)とし,総時間複雑度O(N^2)は受け入れられない.
本題にはキーワード区間照会,区間更新があり,当然,ツリー配列メンテナンスという2つの操作を利用して,ツリー配列アルゴリズムの時間複雑度はO(logn),総時間複雑度O(Nlogn)であり,タイムアウトしないことが考えられる.
簡略化問題:サイズnの配列を2倍に拡大し、新しい拡張された空の配列を元の配列で再充填すると、クエリ区間[1,l]と[r,n]の2つの区間がクエリ[r,n+l]の1つの区間に簡略化される.
コードで実現
構造体の作成
struct Q
{
int l,r;//
int pos;//
}q[200005];カスタム構造体ソート規則
//
int cmp(Q a, Q b)
{
return a.l < b.l;
}ツリー配列基本関数
//lowbit
int lowbit(int k)
{
return k&(-k);
}//
void modify(int n,int v)
{
while(n <= N)
{
c[n] += v;
n += lowbit(n);
}
}//
int sum(int n)
{
int ans = 0;
while(n > 0)
{
ans += c[n];
n -= lowbit(n);
}
return ans;
}末尾から遍歴して処理する
for(int i=N;i>=1;i--)
{
if(!show[A[i]])//show
{
show[A[i]] = i;
fir[i] = true;//
}
else
{
//show
Next[i] = show[A[i]];//
fir[Next[i]] = false;//
fir[i] = true;//
show[A[i]] = i;//
}
}上記の遍歴により、配列全体の各数字に、最初に出現するかどうか、その次に出現する位置の情報があり、ツリー配列にこれらの情報を利用して更新され、クエリーされる.
クエリ結果処理{{くえりけっか:しょり}}
// [r,l] sum(l)-sum(r-1)
res[q[i].pos] = sum(q[i].r) - sum(q[i].l-1);完全なコード
#include
#include
#include
#include
using namespace std;
int N,M;
const int SIZE = 250005;
int c[SIZE];
int A[SIZE];
int Next[SIZE];
int res[200005];
int show[2000005];
bool fir[SIZE];
struct Q
{
int l,r;
int pos;
}q[200005];
int lowbit(int k)
{
return k&(-k);
}
void modify(int n,int v)
{
while(n <= N)
{
c[n] += v;
n += lowbit(n);
}
}
int sum(int n)
{
int ans = 0;
while(n > 0)
{
ans += c[n];
n -= lowbit(n);
}
return ans;
}
int cmp(Q a, Q b)
{
return a.l < b.l;
}
int main()
{
while(~scanf("%d",&N)){
memset(res,0,sizeof(res));
memset(c,0,sizeof(c));
memset(A,0,sizeof(A));
memset(Next,0,sizeof(Next));
memset(fir,0,sizeof(fir));
memset(show,0,sizeof(show));
scanf("%d",&M);
for(int i=1;i<=N;i++) scanf("%d",&A[i]);//A
for(int i=1;i<=N;i++) A[N+i]=A[i];//A
N=N*2;
for(int i=N;i>=1;i--)
{
if(!show[A[i]])//show
{
show[A[i]] = i;
fir[i] = true;//
}
else
{//show
Next[i] = show[A[i]];//
fir[Next[i]] = false;//
fir[i] = true;//
show[A[i]] = i;//
}
}
for(int i=1;i<=M;i++)
{
int l,r;
scanf("%d%d",&l,&r);
q[i].l=r;
q[i].r=l+N/2;
q[i].pos = i;
}
sort(q+1,q+1+M,cmp);
for(int i=1;i<=N;i++)
if(fir[i])//
{
modify(i,1);//
}
int qtemp = q[1].l;//
int ptr = 1;//
for(int i=1;i<=M;i++)
{
for(;ptr