1 条题解
-
0
来一个乱搞题解:
先分块,然后散块暴力查,整块开 ST 表合并 bitset, 复杂度 $O(n \sqrt n \times \frac{\log 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 warma = 200; const int maxn = 3e4+13; bitset<maxn> st[220][10]; int a[maxn],n,q; inline void init(){ for(int i=1;i<=n;i=-~i){ st[(i-1)/warma+1][0][a[i]]=1; } for(int j=1;j<=8;j=-~j) for(int i=1;i+(1<<j)-1<=210;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)/warma+1; int br=(r-1)/warma+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*warma;i=-~i){ ans[a[i]]=1; } for(int i=r;i>=(br-1)*warma+1;--i){ ans[a[i]]=1; } } int tot; map<int,int> lsh; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); read(n); for(int i=1;i<=n;i++){ read(a[i]); if(lsh[a[i]]==0) lsh[a[i]]=++tot; a[i]=lsh[a[i]]; } read(q); init(); for(int i=1;i<=q;i++){ int l,r; read(l); read(r); ans.reset(); query(l,r); write(ans.count()); putchar('\n'); } }
- 1
信息
- ID
- 774
- 时间
- 1500ms
- 内存
- 1536MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 4
- 上传者