Different Integers 牛客网暑期ACM多校训练营（第一场） J 离线+线状数组或者主席树

Given a sequence of integers a1, a2, ..., an and q pairs of integers (l 1, 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 a 1, 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 a 1, a2, ..., an. The i-th of the following q lines contains two integers l i and ri .

输出描述： For each test case, print q integers which denote the result.

备注 * 1 ≤ n, q ≤ 10 5 * 1 ≤ ai ≤ n * 1 ≤ l i , ri ≤ n * The number of test cases does not exceed 10.

示例1:

输入

3 2 1 2 1 1 2 1 3 4 1 1 2 3 4 1 3

输出

2 1 3

题意就是求去掉(i-1,j-1)区间得数以后剩余的不同数的个数

也就是求(1,l)和(r,n)中不同数的个数,因为这两个区间不能直接合并在一起，所以比赛的时候我是通过倍增区间使两个区间合并在一起

倍增区间后，我们所要求的区间就是(r,n+l)，然后就是一个求区间不同数的问题了

比赛的时候我用的是主席树，比赛结束后叉姐直播说用的树状数组，于是看了别人的博客用树状数组写了遍

参考博客：https://www.cnblogs.com/kkrisen/p/3879517.html

下面是树状数组的用法：

我的做法是把区间排好序，针对某个区间在树状数组上更新以及查询相应值，这样能准确查出结果，但又不影响之后的查询

具体来说，先把区间按右端点进行排序，然后从小区间开始，树状数组的含义就是指以当前r为结尾的前缀区间的元素种类数，简单点说，就是我当前扫到l _ r区间，把l - r区间还没在树状数组上更新的值，更新一遍，在之前已经存在了的值先删掉再更新一遍，确保我确定的元素都是往r靠的，这样才能保证求取区间正确

比如我 1 2 2 1 3，当我r移到3的时候，加入前面的1还没在树状数组里更新过（但其实之前已经有读过1了）那就把之前的1的影响删掉，重新在这个3左边这个下标为4的位置给树状数组 add 1.这样确保之后不管我是查询 4 5 或者 1 5，元素1都只算了一次，但都没遗落（想想如果元素1一直在下标1那里，我查询4 5，就不会有1了）

总之：

所以这就是这个离线用法的妙处，尤其要理解树状数组在这个题目代表的含义是什么，即当前以r结尾的区间的元素种类个数，为了维护这个值的准确性，必须把没出现过的，加入到树状数组中，之前已经出现过了并且再次出现的，以再次出现的位置为准。

每次对区间不用一开始就扫，每个就只要扫一次就可以了，用个vis数组记录哪个出现了，出现在什么位置，就不用重新扫了，否则会超时，这样，总共也就扫了n下而不是n*q（这里数字小用vis更快，用map会tle）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

const int N = 300010*2;

int n, vis[N];

struct BIT {

    int c[N];

    void init(int n) {

        for (int i=0;i<=n;i++) c[i]=0;

    }

    void add(int loc,int v) {

        while (loc<=2*n) {

            c[loc]+=v;

            loc+=loc&(-loc);

        }

    }

    int sum(int loc) {

        int ret=0;

        while (loc) {

            ret+=c[loc];

            loc-=loc&(-loc);

        }

        return ret;

    }

}T;

struct node {

    int l,r,id;

    bool operator <(const node&rhs) const {

        //if (l==rhs.l) return r<rhs.r;

        return r<rhs.r;

    }

}query[2000000+10];

int ans[2000000+10];

int A[N];

int main() {

    while (scanf("%d",&n)!=EOF) {

        int q;

        scanf("%d",&q);

        memset( vis, 0, sizeof(vis) );

        T.init(2*n);

        for (int i=1;i<=n;i++) scanf("%d",&A[i]), A[n+i] = A[i];

        for (int i=0;i<q;i++) {

            int le, ri;

            scanf("%d%d",&le,&ri);

            query[i].l = ri, query[i].r = n+le;

            //scanf("%d%d",&query[i].l,&query[i].r);

            query[i].id=i;

        }

        sort(query,query+q);

        int cur=1;

        for (int i=0;i<q;i++) {

            for (int j=cur;j<=query[i].r;j++) {

                if (vis[A[j]]) {

                    T.add(vis[A[j]],-1);

                }

                T.add(j,1);

                vis[A[j]] = j;

            }

            cur=query[i].r+1;

           ans[query[i].id]=T.sum(query[i].r)-T.sum(query[i].l-1);

        }

        for (int i=0;i<q;i++) {

            printf("%d\n",ans[i]);

        }

    }

    return 0;

}

在贴一份主席树的代码，比赛时候A的代码，他优化数据后还是过了

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e6 + 10;

int n,q;

int cnt = 0;

struct Node

{

    int l,r,sum;

} p[maxn << 3];

int la[maxn << 3];

int a[maxn << 3];

int root[maxn << 3];

int build(int l,int r)

{

    int nc = ++cnt;

    p[nc].sum = 0;

    p[nc].l = p[nc].r = 0;

    if (l == r) return nc;

    int m = l + r >> 1;

    p[nc].l = build(l,m);

    p[nc].r = build(m+1,r);

    return nc;

}

int update(int pos,int c,int v,int l,int r)

{

    int nc = ++cnt;

    p[nc] = p[c];

    p[nc].sum += v;

    if (l == r) return nc;

    int m = l+r>>1;

    if (m >= pos)

    {

        p[nc].l = update(pos,p[c].l,v,l,m);

    }

    else

    {

        p[nc].r = update(pos,p[c].r,v,m+1,r);

    }

    return nc;

}

int query(int pos,int c,int l,int r)

{

    if (l == r) return p[c].sum;

    int m = l + r >> 1;

    if (m >= pos)

    {

        return p[p[c].r ].sum + query(pos,p[c].l,l,m);

    }

    else return query(pos,p[c].r,m+1,r);

}

int main()

{

    while(scanf("%d %d",&n,&q) != EOF)

    {

        cnt=0;

        memset(la,-1,sizeof la);

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

        {

            scanf("%d",a+i);

            a[n+i]=a[i];

        }

        root[0] = build(1,2*n);

        for (int i = 1 ; i <= 2*n; ++i)

        {

            int v = a[i];

            if (la[v] == -1)

            {

                root[i] = update(i,root[i-1],1,1,2*n);

            }

            else

            {

                int t = update(la[v],root[i-1],-1,1,2*n);

                root[i] = update(i,t,1,1,2*n);

            }

            la[v] = i;

        }

        while(q--)

        {

            int x,y;

            scanf("%d %d",&x, &y);

            printf("%d\n",query(y,root[n + x],1,2*n));

            ///printf("%d\n",query(1,root[x],1,2*n)+query(y,root[n],1,2*n));

        }

    }

    return 0;

}

巴特西

Different Integers 牛客网暑期ACM多校训练营（第一场） J 离线+线状数组或者主席树

最新文章

热门文章