P3901 分块解法

· · 题解

先把问题变成求区间内不同数数量是否等于区间长度。

考虑分块。

发现对于散块可以暴力查询，现在的问题是怎么快速查询连续的整块。

然后其实我们发现因为只要记录每个数是否出现，所以可以用 bitset 来压缩单个块内的信息。

但是查询的时候合并 \sqrt n 个 bitset 不现实，所以考虑 ST 表。

显然，是否出现这个信息是可重复贡献的。

那现在发现就只需要在预处理时合并 \sqrt n \log \sqrt n 个 bitset 以及在查询时每次合并一个 bitset 就可以了。

那么复杂度就是 O(n \sqrt n \times \frac{\log \sqrt n}{w} + \frac{n \times q}{w})。

卡卡常可以过。

虽然这个算法虽然在这个题目上时间很劣，但是可拓展性很强，比如可以用同样的方法解决两个区间中出现多少种不同的数的问题。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    const int SIZE=1<<21;
    static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
    #define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
    #define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
    #define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
    #define puts(x) IO::Puts(x)
    template<typename T>
    inline void read(T&x){
        for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
        for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
        x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
        for(int i=0;s[i];i++)
            putchar(s[i]);
        putchar('\n');
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
const int B = 318;
const int maxn = 1e5+13;
bitset<maxn> st[320][10];
int a[maxn],n,q;
inline void init(){
    for(int i=1;i<=n;i=-~i){
        st[(i-1)/B+1][0][a[i]]=1;
    }
    for(int j=1;j<=9;j=-~j)
        for(int i=1;i+(1<<j)-1<=318;i=-~i)
            st[i][j]=st[i][j-1]|st[i+(1<<(j-1))][j-1];
}
bitset<maxn> ans;
inline void query(int l,int r){
    int bl=(l-1)/B+1;
    int br=(r-1)/B+1;
    if(bl==br){
        for(int i=l;i<=r;i=-~i){
            ans[a[i]]=1;
        }
        return ;
    }
    if(br!=bl+1){
        int k=log2((br-1)-(bl+1)+1);
        ans|=(st[bl+1][k]|st[(br-1)-(1<<k)+1][k]);
    }
    for(int i=l;i<=bl*B;i=-~i){
        ans[a[i]]=1;
    }
    for(int i=r;i>=(br-1)*B+1;--i){
        ans[a[i]]=1;
    }
}
int tot;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read(n);
    read(q);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    init();
    for(int i=1;i<=q;i++){
        int l,r;
        read(l);
        read(r);
        ans.reset();
        query(l,r);
        if(ans.count()==(r-l+1)){
            putchar('Y');
            putchar('e');
            putchar('s');
            putchar('\n');
        }
        else{
            putchar('N');
            putchar('o');
            putchar('\n');
        }
    }
}