- Я хочу рассказать о очень тупой и бесполезной структуре данных — дерево отрезков на bitset.
- В чём смысл?-мы сможем решать количество уникальных чисел на отрезке за O(log n * x/logx)(на запрос ответа и изменения), где n-длина массива, а x-максимальное значение элемента массива.
- Если в массиве есть отрицательные числа — просто прибавьте ко всем числам abs(X), где X-минимальный элемент
- Вот код(если будут идеи оптимизации — пишите )
#include <bits/stdc++.h>
using namespace std;
vector<bitset<1000>> tree;
bitset<1000> getsum(int v, int Tl, int Tr, int l, int r){
if(l>r)return 0;
if(Tl==l&&Tr==r){
return tree[v];
}
int Tm=(Tl+Tr)>>1;
return getsum(v<<1,Tl,Tm,l,min(Tm,r))|getsum(v<<1|1,Tm+1,Tr,max(Tm+1,l),r);
}
int m=1, x;
void update(int v,int val){
v+=m;
tree[v]=0;
tree[v][m]=1;
v>>=1;
while(v){
tree[v]=tree[v<<1]|tree[v<<1|1];
v>>=1;
}
}
void solve(){
int n;
cin>>n;
while(m<n){
m<<=1;
}
tree.resize(m<<1);
for(int i=0;i<n;i++){
x=(rand()%1000+1000)%1000;
cout<<x<<' ';
tree[i+m][x]=1;
}
for(int i=m-1;i>=1;i--){
tree[i]=tree[i<<1]|tree[i<<1|1];
}
cout<<endl;
int q, l, r;
cin>>q;
while(q--){
cin>>l>>r;
--l;--r;
cout<<getsum(1,0,m-1,l,r).count()<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
На самом деле предела этой структуре данных нет. Можно реализовать K-я статистика на отрезке