P5629-区间与除法-线段树
题意
给定 \(n\) 个数，如果可以通过除以给定的 \(d\) 得到 \(m\) 个原数中的一个，则称为可消除的，每次询问区间 \(l\) ， \(r\) 中消除所有可消除的数所需的最少原数个数。
写题ing
要不是题目是我挑的，不然真的看不出来除了线段树还有什么。
区间问题，线段树是没跑的了（不过静态查询还可以用 \(st\) 表），那我要维护什么东西呢？维护每个可消除的数最后得到的原数，因为如果一个树可以得到多个原数，那么这多个原数都可以得到最小的那个。然后线段树维护。。。有哪些原数？长度 \(62\) 的 \(bool\) ？够是够的，但时间复杂度？是一样的。 \(1.2e8\) ，这和字典树什么关系？
不对，这样维护会 \(T\) 还好我又看了一眼，查询的 \(q logn m = 1.2e9\) 算错了。要么把维护的东西换了，或者换成 \(bitset\) ？不想烧烤了，直接换 \(bitset\) 。
写的时候才发现想要预处理出原数间的关系还挺难的。确实要用字典树?不然每除一次（\(63\)）在 \(60\) 个里面找一次。刚好炸了。。。这不就是一个映射吗。
正文：我写题的过程都在上面，我就只在这总结一下，发现如果原数可以被除成原数，则小的一定更优。所以作一遍去重和映射。在把原数组可以变成的最小原数小标记录。用线段树维护存在的原数，并使用 \(bitset\) 优化。让我想了有一会的就这两优化和映射有没有的问题，题目挺简单的。
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e5+10;
constexpr int maxm = 3.5e7;void read(int&);int n,m,d,q;
int wi[maxn];
int ki[100];
int cov[100];// id->w
unordered_map<int,int> ch;// w->id
int to[maxn];// wi->ki
bitset<64> tr[maxn<<2];void pushup(int p)
{tr[p]=tr[p<<1] | tr[p<<1|1];
}void build(int p=1,int l=1,int r=n)
{if(l==r){if(to[l]){tr[p][to[l]]=1;}return;}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
}bitset<64> query(int x,int y,int p=1,int l=1,int r=n)
{if(x<=l && r<=y){return tr[p];}bitset<64> ret;int mid=(l+r)>>1;if(x<=mid){ret |= query(x,y,p<<1,l,mid);}if(mid<y){ret |= query(x,y,p<<1|1,mid+1,r);}return ret;
}signed main()
{#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);freopen("1.out","w",stdout);#endif // ONLINE_JUDGEread(n);read(m);read(d);read(q);for(int i=1;i<=n;++i){read(wi[i]);}for(int i=1;i<=m;++i){read(ki[i]);}sort(ki+1,ki+1+m);m=unique(ki+1,ki+1+m)-ki-1;for(int i=1;i<=m;++i){cov[i]=ki[i];ch[ki[i]]=i;}for(int i=1;i<=m;++i){int tmp=ki[i];while(tmp){tmp/=d;if(ch.count(tmp)){ch[ki[i]]=ch[tmp];}}cov[i]=cov[ch[ki[i]]];// cerr<<i<<" "<<ch[cov[i]]<<"\n";}for(int i=1;i<=n;++i){int tmp=wi[i];while(tmp){if(ch.count(tmp)){to[i]=ch[tmp];break;}tmp/=d;}// cerr<<i<<" "<<to[i]<<'\n';}build();for(int i=1,x,y ;i<=q;++i){read(x);read(y);printf("%lld\n",(int)query(x,y).count());}return 0;
}void read(int &x)
{x=0;int f=1;signed c=getchar_unlocked();while(!isdigit(c)){if(c=='-'){f=-1;}c=getchar_unlocked();}while(isdigit(c)){x=x*10+(c^48);c=getchar_unlocked();}x*=f;
}