牛客网暑期ACM多校训练营（第一场） J - Different Integers 主席树 and 树状数组 一题多解

博客目录

原题传送门

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述 

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.

题目大意

给定一个数列，给q个询问，每次询问给出一个区间l,r，输出两个区间1~l 和r~n的并集不同元素个数。

思路

1.树状数组

推荐一下对这一类题总结的博客：总结一类题的思路——线段树/树状数组 之 离线+重复出现生效

将数列复制一份贴到原数列的后面，也就是co[i+n]=co[i]，这样头尾就相连，求两边区间就转化为求连续区间的不同数的个数。可以用离线+树状数组（线段树）来做。（线段树树状数组入门讲解-->>传送门）

2.主席树

主席树本来就是线段树的升级版，记录了线段树每次修改的每个副本，利用主席树就可以在线做，如果题目强制在线那就只能主席树了。主席树/题目讲解详细版-->>传送门

注意，不要用map存放最后出现的位置，会TLE掉，使用普通数组为上

AC代码1（树状数组）

树状数组效率高多了，稳稳的AC。主席树还得扣常数

#include<bits/stdc++.h>
#define regi register int
int const maxn=2e5+10;
using namespace std;
int co[maxn];
int c[maxn];
int n,q;
#define Lowbit(i) (i&-i)
void pushup(int i, int x) //i点增量为x
{
    while(i <= n)
    {
        c[i] += x;
        i += Lowbit(i);
    }
}

int query(int x)//区间求和 [1,x]
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];//从后面的节点往前加
        x-=Lowbit(x);//同层中向前移动一格，如果遇到L=1的节点会减成0
    }
    return sum;
}
struct node{
    int l,r,ans,i; 
};
node qry[maxn];
bool operator<(node a,node b)
{
    return a.l<b.l; 
} 
bool cmp(node a,node b){
    return a.i<b.i;
}
int main()
{
    while(cin>>n>>q)
    {
        memset(c,0,sizeof(c));
        for(regi i=1;i<=n;i++)
        {
            scanf("%d",co+i);
        }
        int a,b;
        for(regi i=1;i<=q;i++)
        {
            scanf("%d%d",&a,&b);
            qry[i].l=b;
            qry[i].r=a+n;
            qry[i].i=i;
        }
        sort(qry+1,qry+1+q);
        for(regi i=1;i<=n;i++)
        {
            co[i+n]=co[i];
        } 
        n*=2;
        int p=n;
        map<int,int>mp;
        mp.clear();
        for(int i=q;i>=1;i--)
        {
            for(;p>=qry[i].l;p--)
            {
                if(mp.find(co[p])!=mp.end())//有前驱 
                {
                    pushup(mp[co[p]],-1);//把前驱删掉 
                }
                pushup(p,1); //标记最后一个 
                mp[co[p]]=p;//更新前驱 
            }
            qry[i].ans=query(qry[i].r);
        }
        sort(qry+1,qry+1+q,cmp);
        for(regi i=1;i<=q;i++)
        {
            printf("%d\n",qry[i].ans);
        }
    }
}

AC代码2（主席树）

下面代码优化不好，评测机一会儿AC一会儿TLE，我也是醉了

评测机繁忙的时候TLE，闲的时候AC，输入外挂也救不了

在TLE的边缘疯狂试探

#include<bits/stdc++.h>
#define regi register int
int const maxn=2e5+10;
using namespace std;
int co[maxn];
 
int n,q;
int const maxRoot=5e7; 
int lson[maxRoot];//左孩子索引
int rson[maxRoot];//右孩子索引
int c[maxRoot]; //节点值
    int tot;//分配空间
    int T[maxn];//根
int build(int l,int r){
        //建立空白线段树 l和r表示当前节点应当表示的区间范围
        int root=tot++;//申请空间
        c[root]=0;  //节点置为0
        if(l!=r){
            int mid=(l+r)>>1;
            lson[root]=build(l,mid);//递归建立左树，跟线段树一样
            rson[root]=build(mid+1,r);//建立右树
        }
        return root;
    }
    inline int update(int root,int pos,int add){  //更新叶子，参数：在这个根节点的基础上生成新根、更新位置、增加的值
        int newroot=tot++;  //申请空间 增加新的根  newroot为工作指针，感觉这里变量名起反了
        int tmp=newroot;  //新的根备份下来用作返回值
        c[newroot]=c[root]+add;  //因为是给叶子增加一个值，所以路径每个节点都增加一个值，不用PushUp()来更新了。
        int l=1,r=n;  //根节点表示的范围是1~n
        while(l<r){
            int mid=(l+r)>>1;
            if(pos<=mid){
                  //叶子位置在左子树，所以左子树新建链，右子树继承 newroot是新树节点，root是旧树节点
                  //参照上面的图
                lson[newroot]=tot++;   //左子树新建链
                rson[newroot]=rson[root];  //右子树继承旧的
                newroot=lson[newroot];  //继续向下建树，因为右子树已经继承了所以只建左子树就可以了
                root=lson[root];  //因为要建新树的左链，所以只用参照旧树的左链。
                r=mid;
            }
            else{
                  //叶子的位置在右子树
                rson[newroot]=tot++;  //右子树重建链
                lson[newroot]=lson[root];  //左子树继承
                newroot=rson[newroot];  //因为左子树已经继承，所以只建右子树
                root=rson[root];   //跟随新树
                l=mid+1;
            }
            //更新值
            c[newroot]=c[root]+add;
        }
           
        return tmp;   //返回新树根
    }
     
inline int query(int root,int pos){ //查询1到pos的区间和，参数：根节点（历史记录），查询位置
        root=T[root];
        int ret=0;
        int l=1,r=n;
        while(pos<r){
            int mid=(l+r)>>1;
            if(pos<=mid){
                r=mid;
                root=lson[root];
            }
            else{
                ret+=c[lson[root]];
                root=rson[root];
                l=mid+1;
            }
        }
        return ret+c[root];//最后加上叶子自己。
    }
 
int last[maxn];//注意，如果使用map存放会TLE掉
 
int main(){
    while(cin>>n>>q){
        tot=0;
        for(regi i=1;i<=n;i++){
            scanf("%d",&co[i]);
        }
        //复制粘贴 ,将求两边转化为求中间
        for(regi i=1;i<=n;i++){
            co[i+n]=co[i];
        }
        n*=2;
        //主席树求解区间不同元素的值
        T[n+1]=build(1,n);  //在第n+1个根上建立初始线段树
        memset(last,0,sizeof(last));
        for(regi i=n;i>=1;i--){
            if(last[co[i]]==0){
                //不存在
                T[i]=update(T[i+1],i,1);
            }
            else{
                //出现过
                int tmp=update(T[i+1],last[co[i]],-1);
                T[i]=update(tmp,i,1);
            }
            last[co[i]]=i;  //记录位置
        }
        int a,b;
        for(regi i=1;i<=q;i++){
            scanf("%d%d",&a,&b);
            printf("%d\n",query(b,a+n/2));
        }
         
    }
}