P5068 我回来了

题面

题解

根据题意，发现我们只关心 \((ud,(u+1)d]\) 这种区间（下称关键区间）内是否含有 \(1\)，而这种区间只有 \(O(n\ln n)\) 个。
我们可以记 \(d_i\) 每个 \(a_i\) 变为 \(1\) 的时间，用 ST 表维护 \(d_i\) 的区间最小值，从而在 \(O(n\log n+m)\) 的时间内计算出每个关键区间出现 \(1\) 的时刻。
然后处理询问，我们在遇到修改时激活相应的关键区间 \((ud,(u+1)d]\)，并单点修改 \(d\) 点答案，查询就是区间求和。使用树状数组维护即可。
复杂度 \(O(n\log^2n+m\log n)\)，常数较小，可以轻松通过。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tp[1000005],x[1000005],y[1000005];
int *f[100005],memory[5000005];
int d[100005];
struct node{
    int t,u,v;
    bool operator<(const node &b)const{
        return t<b.t;
    }
};
node s[2000005]; int k;
int h[100005],bt[100005];
void add(int u){
    while(u<=n){
        bt[u]++;
        u+=u&-u;
    }
}
int getsum(int u){
    int res=0;
    while(u){
        res+=bt[u]; u&=u-1;
    }return res;
}
int st[100005][20];
int ln2[100005];
void getst(){
    for(int i=1;i<=n;i++) if(d[i]==0) d[i]=0x3f3f3f3f;
    for(int i=2;i<=n;i++) ln2[i]=ln2[i>>1]+1;
    for(int i=1;i<=n;i++){
        st[i][0]=d[i];
    }
    for(int i=1;i<=ln2[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
        }
    }
}
inline int getmin(int l,int r){
    if(l>n) return 0x3f3f3f3f;
    if(r>n) r=n;
    int x=ln2[r-l+1];
    return min(st[l][x],st[r-(1<<x)+1][x]);
}
inline void upd(int u,int v){
    while(f[u][h[u]+1]<=f[u][v]) h[u]++,add(u);
}
inline int qry(int l,int r){
    return getsum(r)-getsum(l-1);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>tp[i]>>x[i]; if(tp[i]==2) cin>>y[i];
        if(tp[i]==1){
            if(!d[x[i]]) d[x[i]]=i;
        }
    }
    f[1]=memory;
    for(int i=1;i<=n;i++){
        f[i+1]=f[i]+n/i+5;
    }
    getst();
    for(int i=1;i<=n;i++){
        for(int j=1;j*i<=n+i+i;j++){
            f[i][j]=getmin(i*j-i+1,i*j);
            s[++k]={f[i][j],i,j};
        }
    }
    sort(s+1,s+1+k);
    int np=1;
    for(int i=1;i<=m;i++){
        if(tp[i]==1){
            while(s[np].t==i){
                upd(s[np].u,s[np].v); np++;
            }
        }else{
            cout<<qry(x[i],y[i])+y[i]-x[i]+1<<'\n';
        }
    }
    return 0;
}