题解 【P7811 [JRKSJ R2] 你的名字。】

· · 题解

dX 的题解 目前已经不能通过本题，但是加上一个又合理又奇怪（？）的特判，便可通过本题。

令阈值为 B，考虑 k\le B 的情况，我们需要 O(n) 计算出 a_i \bmod k 的值，但如果当前的 k 的询问数很少，其实不如将这些询问与 k\ge B 的询问一起处理，这样做可以省下计算 a 数组取模后的值的开销。

由此可以很自然地想到一个特判：如果 \min(\frac{a}{i},\frac{a}{w})\times|q|\le \alpha n，那么就将当前的询问放在最后处理。 其中，\min(\frac{a}{i},\frac{a}{w}) 表示通过 bitset 计算一个答案的花费，|q| 表示询问数量，\alpha 是可以通过手动二分得到的平衡因子。

不难发现，由于 \frac{a}{i} 随 i 增大而减小，所以我们可以不设置阈值，让它完全自适应测试数据。

实际测试中，这个特判表现得相当优秀，我在多次调整阈值后仍TLE的点，在加上这个特判后只跑了 0.2s，当然也不排除出题人还能造出来卡掉这个特判的数据。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxa=1e5+1,maxn=3e5+1;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
static char pbuf[1000000],*p1=pbuf,*p2=pbuf,obuf[1000000],*o=obuf;
#define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (o-obuf<1000000)?(*o++=(x)):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*o++=(x))
inline int qr(){
    ri in=0;register char ch;
    while(!isdigit(ch=getchar()));
    do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar()));
    return in;
}
template<class T>
void qw(T out){
    if(out>9)qw(out/10);
    putchar(out%10|48);
}
struct flusher{~flusher(){fwrite(obuf,o-obuf,1,stdout);}}autoflush;
int a[maxn],_a[maxn],BB,m,n;
struct qry{
    int l,r,k,id,bel;
    inline qry(int l_=0,int r_=0,int k_=0,int id_=0):l(l_),r(r_),k(k_),id(id_){}
    inline bool operator<(const qry &rhs)const{return bel!=rhs.bel?l<rhs.l:(bel&1)?r<rhs.r:r>rhs.r;}
};
vector<qry>bq,sq[maxa];
typedef unsigned long long ull;
template<int siz>
struct bset{
    ull b[((siz+63)>>6)+1];int len;
    inline bset(){len=(siz+63)>>6;}
    inline void set0(int p){b[p>>6]&=~(1llu<<p);}
    inline void set1(int p){b[p>>6]|=(1llu<<p);}
    inline int find_first(){for(ri i=0;i<len;++i)if(b[i])return (i<<6)|__builtin_ctzll(b[i]);return siz;}
    inline int find_next(int p){
        if(++p>=siz)return siz;
        ri hi=p>>6,lo=p&63;
        if(b[hi]>>lo)return p+__builtin_ctzll(b[hi]>>lo);
        for(ri i=hi+1;i<len;++i)if(b[i])return (i<<6)|__builtin_ctzll(b[i]);
        return siz;
    }
};
bset<maxa>b;
int ans[maxn],cnt[maxn];
int main(){
    n=qr(),m=qr();
    for(ri i=1;i<=n;++i)a[i]=qr();
    for(ri i=1;i<=m;++i){
        ri x=qr(),y=qr(),z=qr();
        sq[z].emplace_back(x,y,z,i);
    }
    for(ri i=2;i<maxa;++i)
        if(sq[i].size()){
            if(min(maxa/i,maxa>>6)*sq[i].size()<(n<<2)){
                bq.insert(bq.end(),sq[i].begin(),sq[i].end());
                continue;
            }
            BB=n/sqrt(sq[i].size())+1;
            for(qry &j:sq[i])j.bel=j.l/BB;
            sort(sq[i].begin(),sq[i].end());
            for(ri j=1;j<=n;++j)_a[j]=a[j]%i;
            ri pl=1,pr=0;
            for(const qry &j:sq[i]){
                while(pl>j.l)if(!cnt[_a[--pl]]++)b.set1(_a[pl]);
                while(pr<j.r)if(!cnt[_a[++pr]]++)b.set1(_a[pr]);
                while(pl<j.l)if(!--cnt[_a[pl++]])b.set0(_a[pl-1]);
                while(pr>j.r)if(!--cnt[_a[pr--]])b.set0(_a[pr+1]);
                ans[j.id]=b.find_first();
            }
            while(pr>=pl)b.set0(_a[pr]),--cnt[_a[pr--]];
        }
    if(bq.size()){
        BB=n/sqrt(bq.size())+1;
        for(qry &i:bq)i.bel=i.l/BB;
        sort(bq.begin(),bq.end());
        ri pl=1,pr=0;
        for(const qry &i:bq){
            while(pl>i.l)if(!cnt[a[--pl]]++)b.set1(a[pl]);
            while(pr<i.r)if(!cnt[a[++pr]]++)b.set1(a[pr]);
            while(pl<i.l)if(!--cnt[a[pl++]])b.set0(a[pl-1]);
            while(pr>i.r)if(!--cnt[a[pr--]])b.set0(a[pr+1]);
            ans[i.id]=i.k;
            for(ri j=b.find_first();ans[i.id]&&j<maxa;j=b.find_next((j/i.k+1)*i.k-1))if(j<maxa)ckmin(ans[i.id],j%i.k);
        }
    }
    for(ri i=1;i<=m;++i)qw(ans[i]),putchar(10);
    return 0;
}