首页 » 树状数组 » 正文

牛客网暑期ACM多校训练营(第一场)Different Integers(莫队/树状数组)


来源:https://www.nowcoder.com/acm/contest/139/J

题目描述

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.

示例1

输入

复制

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.

思路

  1. 莫队算法,将前面的后面的都放到num数组里面计数,当数从1变为0则结果-1,从0到1则+1。由莫队分块来处理。
  2. 树状数组,将所有的查询以r从小到大排序,然后逐个处理。当去掉的点是某个数的最后一个时,如果之后的 l 在该数的第一个点之前,就要加上该数的一次。采用的是将该数的第一个点前面的count+1,来维护树状数组处理。

代码

莫队算法

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+100;
const int MAXM=1e5+100;
int arr[MAXN];
int num[MAXN],unit;
int answer[MAXM];
struct qnode_t{
    int l,r,id;
    bool operator < (const qnode_t &b) const {
        if(l/unit!=b.l/unit) return l/unit<b.l/unit;
        else return r<b.r;
    }
}quest[MAXM];
void work(int n,int q){
    int temp=0;
    memset(num,0,sizeof(num));
    int L=quest[1].l,R=quest[1].r;
    for(int i=1;i<=L;i++)  //算第一个的左边 
    {
        if(num[arr[i]]==0) temp++;
        num[arr[i]]++;
    }
    for(int i=R;i<=n;i++)  //算第一个的右边 
    {
        if(num[arr[i]]==0) temp++;
        num[arr[i]]++;
    }
    answer[quest[1].id]=temp;
    for(int i=2;i<=q;i++)  //算第二个到第q个 
    {
        while(R<quest[i].r)
        {
            num[arr[R]]--;
            if(num[arr[R]]==0) temp--;
            R++;
        }
        while(R>quest[i].r)
        {
            R--;
            if(num[arr[R]]==0) temp++;
            num[arr[R]]++;
        }
        while(L<quest[i].l)
        {
            L++;
            if(num[arr[L]]==0) temp++;
            num[arr[L]]++;
        }
        while(L>quest[i].l)
        {
            num[arr[L]]--;
            if(num[arr[L]]==0) temp--;
            L--;
        }
       /* printf("L->R id :%d :%d %d %d\n",quest[i].id,L,R,temp);*/
        answer[quest[i].id]=temp;
    }
}
int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        for(int i=1;i<=q;i++)
        {
            quest[i].id=i;  //记录 id 
            scanf("%d%d",&quest[i].l,&quest[i].r);
        }
        unit=500+1;  //标准采用sqrt(n),这里过不了,采用500+1反而能过 
        sort(quest+1,quest+q+1);
        work(n,q);
        for(int i=1;i<=q;i++)
            printf("%d\n",answer[i]);
    }
    return 0;
}

树状数组

#include <bits/stdc++.h>

struct Query
{
    int l, r, id;
};

bool operator < (const Query& u, const Query& v)  //重载 
{
    return u.r < v.r;
}

int main()
{
    //freopen("2.txt", "r", stdin);
    int n, q;
    while (scanf("%d%d", &n, &q) == 2) {
        std::vector<int> a(n+1), first(n+1, -1), last(n+1);
        int total = 0;
        for (int i = 1; i <= n; ++ i) {  //输入数据 
            scanf("%d", &a[i]);
            last[a[i]] = i;
            if (first[a[i]] == -1) {
                total ++, first[a[i]] = i;
            }
        }
        std::vector<Query> queries;
        for (int i = 0, l, r; i < q; ++ i) {
            scanf("%d%d", &l, &r);
            queries.push_back(Query {l, r, i});
        }
        std::sort(queries.begin(), queries.end());
        std::vector<int> count(n+1), result(q+1);
        for (int i = 1, k = 0; i <= n; ++ i) {  //将i从第一个开始尝试最后一个数在 r 左边 
            while (k < q && queries[k].r == i) {  //计算一个查询 
                int& ref = result[queries[k].id] = total;
                for (int j = queries[k].l; j <= n; j += j & -j) {  //算上数的第一个去掉最终答案所去掉的值 
                    ref -= count[j];
                }
                k ++;
            }
            if (last[a[i]] == i) {  //该数为最后一个,如果 l 小于该数的第一个点,则需要减去一个数 
                for (int j = first[a[i]] - 1; j > 0; j -= j & -j) {
                    count[j] ++;  //之后的计算直接记删除
                }
            }
        }
        for (int i = 0; i < q; ++ i) {  //输出最终的答案 
            printf("%d\n", result[i]);
        }
    }
}

发表评论