时间戳

首页 > 技术文章 > 线段树区间俩个同样的数

线段树区间俩个同样的数

lipu123 2021-02-06 22:58 原文

题目一：

链接：https://ac.nowcoder.com/acm/contest/9983/E
来源：牛客网

在卖礼物的超市中有n个柜子，每个柜子里都摆放了一个礼物，每个礼物有自己的一个编号，第i个柜子里的礼物编号为ai​。
茶山牛想给牛牛和牛妹买相同编号的礼物，但礼物有可能在某个时刻被其他人买走，而且柜子数量太多，因此茶山牛在某个时刻只想知道某一个柜子区间是否能买到两件相同编号的礼物。
具体来说，有q次操作，格式如下：
1  x，第x个柜子里的礼物被买走，保证此时这个柜子里的礼物还在。
2 l r，茶山牛询问第l到第r个柜子未被买走的礼物中是否有两个礼物编号相同。

输入描述:

 

 

 

输出描述:

对每次茶山牛的询问输出一行一个整数，如果在指定的区间内有两个礼物编号相同则输出1，否则输出0
示例1

输入

复制 
5 5
1 2 1 2 1
2 2 4
2 2 5
1 2
2 2 4
2 2 5

输出

复制 
1
1
0
1

说明

第一次询问的时候可以买到两件编号为2的礼物。第三次询问的时候由于第二件礼物被买走，所以2到4柜子里只有一件编号为1的礼物和一件编号为2的礼物。
第四次询问的时候可以买到两件编号为1的礼物。



这个题就是用线段树维护数组nextt[i](这个数组的含义是后面第一个出现a[i]的下标），这样维护
到时候只需要查询一下[l,r]中的最小值看看是不是小于等于r

pre[i]=book[a[i]];//上一次出现的下标
nextt[book[a[i]]]=i;
book[a[i]]=i;
//这里book[i]是暂时储存a[i]的

修改和查询都是板子

再一个主要的是这里如果修改了这个x，x的pre和nextt都要修改

还有线段树要修改两次:

1.x的后继变成inf,

2.pre[x]的后继变成nextt[pre[x]]

change(1,x,inf);//维护的是后继的下标 
nextt[pre[x]]=nextt[x]; 
if(nextt[x]!=inf){
    pre[nextt[x]]=pre[x];
}
change(1,pre[x],nextt[pre[x]]);//维护的后继的下标，就是他前一个的后继要改

 

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=5e6+9;
ll over=maxn*4;
ll inf=0x3f3f3f3f3f3f3f3f;
struct node{
    ll l,r,mi;
}t[maxn];
ll book[maxn],a[maxn],pre[maxn],nextt[maxn];
int n,q;
void push_up(ll p){
    t[p].mi=min(t[2*p].mi,t[2*p+1].mi);
    return ; 
}
void build(ll p,ll l,ll r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].mi=nextt[l];//维护的下一次出现的位置 
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].mi=min(t[2*p].mi,t[2*p+1].mi); 
} 
void change(ll p,ll x,ll z){
    if(t[p].l==t[p].r){
        t[p].mi=z;
        return ;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid){
        change(2*p,x,z);
    }
    else{
        change(2*p+1,x,z);
    }
    push_up(p);
}
ll query(ll p,ll l,ll r){
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].mi;
    }
    int mid=(t[p].l+t[p].r)/2;
    ll ans=inf;
    if(l<=mid){
        ans=min(ans,query(2*p,l,r));
    }
    if(r>mid){
        ans=min(ans,query(2*p+1,l,r));
    }
    return ans;
} 
int main(){
    cin>>n>>q;
    memset(nextt,inf,sizeof(nextt));
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        pre[i]=book[a[i]];//上一次出现的
        nextt[book[a[i]]]=i;
        book[a[i]]=i;
    }
//    for(int i=1;i<=n;i++){
//        cout<<pre[i]<<" ";
//    } 
//    cout<<endl;
//    for(int i=1;i<=n;i++){
//        cout<<nextt[i]<<" ";
//    } 
//    cout<<endl;
//    for(int i=1;i<=n;i++){
//        cout<<book[i]<<" ";
//    } 
//    cout<<endl;
    build(1,1,n);
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            ll x;
            cin>>x;
            change(1,x,inf);//维护的是后继的下标 
            nextt[pre[x]]=nextt[x]; 
            if(nextt[x]!=inf){
                pre[nextt[x]]=pre[x];
            }
            change(1,pre[x],nextt[pre[x]]);//维护的后继的下标，就是他前一个的后继要改 
        }
        else{
            ll x,y;
            cin>>x>>y;
            ll ans=query(1,x,y);
            if(ans<=y){
                cout<<1<<endl;
            }
            else{
                cout<<0<<endl;
            } 
        }
    } 
}

题目二

题目描述

给你一个长为N的序列A，有Q次询问。每次询问给出一个区间[L,R]，询问AL与AR之间是否存在两个相等的数。

输入

共Q+2行。
第一行，两个整数N,Q。
第二行，N个整数A1,A2……An。
接下来Q行，每行两个整数L,R。

输出

对每个询问输出一行，Yes或No.

样例输入 Copy

4 2
1 2 3 2
1 3
2 4

样例输出 Copy

No
Yes

提示

对于30%的数据，N,Q≤1000，Ai≤1000。
对于60%的数据，N,Q≤10000。
对于100%的数据，1≤Ai≤106，1≤N,Q≤105,1≤L≤R≤N，数据有梯度。
 

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=3e6+9;
int a[maxn];
int ne[maxn];
int pre[maxn];
int book[maxn];
struct node{
    int l,r;
    int mi;
}t[maxn];
void push(int p){
    t[p].mi=min(t[2*p].mi,t[2*p+1].mi);
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].mi=ne[l];
        return ; 
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    push(p);
}
int query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r){
        return t[p].mi;
    } 
    if(r<=t[2*p].r){
        return query(2*p,l,r);
    }
    else if(l>=t[2*p+1].l){
        return query(2*p+1,l,r);
    }
    else{
        return min(query(2*p,l,r),query(2*p+1,l,r));
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    memset(ne,0x3f,sizeof(ne));
    memset(book,-1,sizeof(book));
    for(int i=n;i>=1;i--){
        if(book[a[i]]!=-1){
            ne[i]=book[a[i]];
        }
        book[a[i]]=i;//线段树 
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        if(query(1,l,r)<=r){
            cout<<"Yes"<<"\n";
        }
        else{
            cout<<"No"<<"\n";
        }
    }
}

 

推荐阅读