牛客一 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.

示例

输入

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.

题解

这场比赛的签到题 有很多种方法：莫队，主席树等 不过我不会

标程是树状数组，树状数组可以对区间进行跳跃性的操作。首先是题意，题意要求我们找[0,l]与[r,n]两个区间加起来不同的数，我看到标程将数组扩大一倍，就相当于找[r,l]区间不同的数，不过我觉得没有这个必要。
首先把那三个函数写好，套模板。
我们可以标记每个数字出现的前后位置，当遍历到一个数的最后一个数字后，从这个数开始的位置向上更新，这样可以快速更新这个位置之前有多少种数，（l前有多少种数并且结束的-r前有多少开始并结束的）=空缺区间有多少种数开始并已经结束，然后总的减去这个数就可以
下面是在百度辛苦折腾下终于AC的代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
struct node
{
    int l,r,num;
}f[maxn];
int s[maxn];
int pre[maxn];
int las[maxn];
int ans[maxn];
int tree[maxn];
int n;
bool cmp(node a,node b)
{
    return a.r<b.r;
}
/* 树状数组函数模板*/
void add(int i, int v) {
    while(i <= n+1) {
        tree[i] += v;
        i += i&-i;
    }
}

int query(int i) {
    int ret = 0;
    while(i) {
        ret += tree[i];
        i -= i&-i;
    }
    return ret;
}
/*******************/
int main() {
   int q;
   int tot=0;
   while(scanf("%d%d",&n,&q)!=EOF){
        memset(pre,0,sizeof(pre));
        memset(tree,0,sizeof(tree));
        memset(las,0,sizeof(las));
        tot=0;
       for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        if(!pre[s[i]]){
            tot++;
            pre[s[i]]=i;
        }
        las[s[i]]=i;
       }
       for(int i=1;i<=q;i++){
        scanf("%d %d",&f[i].l,&f[i].r);
        f[i].num=i;
       }
       int nowl=1;
       sort(f+1,f+1+q,cmp);
       for(int i=1;i<=n;i++){
        while(nowl<=q&&f[nowl].r==i){
            int num=f[nowl].num;
            ans[num]=tot-(query(f[nowl].r)-query(f[nowl].l));
            nowl++;

        }
        if(las[s[i]]==i) add(pre[s[i]],1);
       }
       for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
   }
}