P3901

DDF_ · 2025-11-19 20:15:14 · 题解

题意

有一个长度为 n 的序列 a，q 次询问，问 [l,r] 中是不是互不相同。

题解

题解区里一车子莫队，但我不会莫队，用一个非常神秘的算法交一发过了，故写题解。

令 lst_{i} 为 a 中与其相同的上一个数的位置，如果一个区间不合法，他肯定同时包含 lst_{i} 和 i。

然后就可以把所有区间拉出来，按照左端点排序并离线处理。

让 i 在 1 \sim n 从小到大枚举，如果遇到左端点就把这个区间加入到一个容器里，遇到右端点就把这个区间从容器里退出。

重头戏来了：每遇到一个 i，就把看容器里的区间有几个其左节点在 lst_{i} 前，那么这些区间里肯定都不互不相同，答案就是 No。

跑完一遍没有跑出来上面这个情况的，答案就是 Yes。

至于这个容器……可以用 set 啊，又满足加入，还满足删除，甚至可以按照左端点把加入的节点排序！

加个具体实现：

枚举 i \in [1,n]，遇到一个左端点为 i，将其加入 set 里。

然后对于 i，枚举左端点在 lst_{i} 前的所有区间将其退掉，然后让其答案为 No，借助 set 强大的排序功能，可以很轻松的找这些。

最后退掉右端点在 i 的，用一个堆将所有在 set 里的按右端点从小到大排序，那么如果存在，右端点在 i 的一定在堆顶（右端点小于 i 的已经被退了），接着就把这些在 set 里使用 find() 函数找一下，找到就退，找不到（可能之前答案已经设定了）就不用退了。

STL 很好玩吧！

然后就做完了，复杂度 O(n \log q)。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define si set<pair<int,int> >::iterator
using namespace std;
const int N=1e5+5;
int n,q;
int a[N],lst[N],lsta[N],reff[N];
struct query {
    int l,r,id;
    bool ans;
} s[N];
bool cmp(query a,query b) {
    return a.l<b.l;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        lst[i]=lsta[a[i]];
        lsta[a[i]]=i;
    }
    for(int i=1;i<=q;i++) cin>>s[i].l>>s[i].r,s[i].id=i;
    sort(s+1,s+1+q,cmp);
    for(int i=1;i<=q;i++) reff[s[i].id]=i;
    set<pii> S;
    priority_queue<pii> del;
    int x=1;
    for(int i=1;i<=n;i++) {
        while(i==s[x].l) S.insert({s[x].l,x}),del.push({-s[x].r,x}),x++;
        //加入左端点在 i 的区间 
        for(si j=S.begin(),ERASE;(*j).first<=lst[i]&&j!=S.end();) { //左端点在 lst[i] 及以前的答案都是 No
            s[(*j).second].ans=1;
            ERASE=j,j++;
            S.erase(ERASE); //删掉，让每个区间至多被判一次，这样复杂度正确的
        }
        while(del.size()&&-del.top().first==i) {
            int xx=del.top().second;
            del.pop();
            si FIND=S.find({s[xx].l,xx});
            if(FIND!=S.end()) S.erase(FIND);
        } //堆会按照第一关键字排序，可以轻松把右端点在 i 的退掉 
    }
    for(int i=1;i<=q;i++) {
        if(s[reff[i]].ans) puts("No");
        else puts("Yes");
    }
    return 0;
}