牛客暑假多校第一场J-Different Integers

一、题目描述：

链接：https://www.nowcoder.com/acm/contest/139/J
Given a sequence of integers a₁, a₂, ..., a_n and q pairs of integers (l₁, r₁), (l₂, r₂), ..., (l_q, r_q), find count(l₁, r₁), count(l₂, r₂), ..., count(l_q, r_q) where count(i, j) is the number of different integers among a₁, a₂, ..., a_i, a_j, a_{j + 1}, ..., a_n.

大概是说，给一个长为n的数组，要求进行m次查询，每次给出l,r要求统计数组内，除了(l,r)区间内的其他元素的种类数。

二、思路

考虑一个元素有两个属性：第一次出现的地方和最后一次出现的地方：记为first[x]和last[x]

则答案应为，总元素个数 - 只在给定区间内出现的元素个数。

则问题实际上转化为求count（first[x],last[x] ∈ (l,r)）。

考虑实际上对于每个元素来说，first[x],和last[x]可以理解为二元组——或者二维空间的坐标，则问题实际转化为二维空间内的点统计问题。因为元素太多，所以考虑使用主席树的方式来构造二维线段树。

但是进一步观察可得，每一行每一列都只有一个元素可能存在。于是如果保证二元组（first[x],last[x]）中last[x]保持递增顺序其实就没必要一定要构造主席树来进行数字统计——直接用树状数组挂vector之后用lower_bound查出现位置即可。

#include<bits/stdc++.h>

using namespace std;

#define pp pair<int,int>

#define veci vector<int>

#define vecp vector<pp>

const int MAXN=;

vecp p;

int first[MAXN];

int last[MAXN];

int arr[MAXN];

int n,m;

int summ ;

class Node

{

    public:

        veci arr;

};

Node arr_1[MAXN];

void insert(int a,int b)

{

    // cout<<a<<" "<<b<<endl;

    a += ;

    while(a<n+)

    {

        arr_1[a].arr.push_back(b);

        a += a &(-a);

    }

}

int count(int a,int b)

{

    // cout<<"query: "<<a<<" "<<b<<endl;

    a += ;

    int cnt = ;

    while(a)

    {

        int tmp = lower_bound(arr_1[a].arr.begin(),arr_1[a].arr.end(),b)-arr_1[a].arr.begin();

        // if(tmp != arr_1[a].arr.size() && arr_1[a].arr[tmp] == b)tmp ++;

        cnt += tmp;

            // cout<< "tmp: "<<tmp<<" size"<<arr_1[a].arr.size()<<endl;

        a-=a&(-a);

    }

    return cnt;

}

bool cmp(pp p1,pp p2)

{

    return p1.second<p2.second;

}

void init()

{

    summ = ;

    memset(first,-,sizeof(first));

    memset(last,-,sizeof(last));

    p.clear();

    for(int i=;i<n;++i)scanf("%d",&arr[i]);//cin>>arr[i];

    for(int i=;i<n+;++i)arr_1[i].arr.clear();

    for(int i=;i<n;++i)

    {

        int a = i;

        int b = n--i;

        int ta = arr[a];

        int tb = arr[b];

        if(first[ta] == -)

        {

            summ++;

            first[ta] = a;

            if(last[ta] != -)

                p.push_back(make_pair(first[ta],last[ta]));

        }

        if(last[tb] == -)

        {

            last[tb] = b;

            if(first[tb]!= -)

                p.push_back(make_pair(first[tb],last[tb]));

        }

    }

    sort(p.begin(),p.end(),cmp);

    int len = p.size();

    for(int i=;i<len;++i)

    {

        insert(p[i].first,p[i].second);

    }

    for(int i=;i<m;++i)

    {

        int a,b;

        // cin>>a>>b;

        scanf("%d%d",&a,&b);

        a--;b--;

        cout<<summ-(count(b-,b) - count(a,b))<<"\n";

    }

}

int main()

{

    while(cin>>n>>m)init();

    return ;

}

巴特西

牛客暑假多校第一场J-Different Integers

一、题目描述：

二、思路

最新文章

热门文章