减半警报器

· · 个人记录

一个很厉害的 Trick，一般通过将信息均摊至若干部分，以一只 \log 的代价去掉一维限制。

有 n 个城市，从 1\sim n 编号，共有 m 次操作：

  • 加入一个监视 x 所有质因子对应城市的监视器，阈值为 y。
  • 在 x 所有质因子对应城市内发生 y 次事件。

请在每次事件后输出恰好达到阈值的监视器编号。

1\le n,m \le 10^5

比较经典的减半情报器。

发现 x\,(\le 10^5) 的质因子个数之多只有 k\,(k \le 6) 个，因此考虑将阈值均摊到每一个质因子上，即在每一个质因子上放一个独立的，阈值为 \frac{y}{k} 的监视器，这样操作就变成了单个城市的修改与查询。

接下来一个比较厉害的处理是，若 x 号监视器的一个均摊出来的监视器的阈值降到 0 以下，那么直接暴力重构 x 号监视器的所有信息。

这显然是可以实现的，考虑时间复杂度为什么是对的。x 号监视器的每一次重构，意味着其阈值至少降低了 \frac y k，也就是说至多重构 \log_{\frac k {k-1}}y 次。k 很小，可以接受。

总时间复杂度 O(mk\log_{\frac k {k-1}}V\log n)。

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int maxn=100010;
il ll read(){
    ll x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
struct info{
    ll x,y;
    info (ll _x=0,ll _y=0){x=_x,y=_y;}
}q[maxn];
int n,m,N,cnt;
int p[maxn],num[maxn];
vector<int>Div[maxn];
bool vis[maxn];
void Oula(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++cnt]=i,num[i]=cnt;
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
void init(){
    Oula(n);
    for(int i=1;i<=n;i++){
        int x=i,qx=sqrt(x);
        for(int j=1;p[j]<=qx;j++)
            if(x%p[j]==0){
                Div[i].push_back(j);
                while(x%p[j]==0) x/=p[j];
            }
        if(x>1)Div[i].push_back(num[x]);
    }
}
int rt[maxn];
int st[maxn],top;
namespace Seg{
    #define MAXN maxn*100
    int ls[MAXN],rs[MAXN],cnt;
    ll dm[MAXN],id[MAXN],lz[MAXN];
    void pushup(int i){
        if(!id[ls[i]]) id[i]=id[rs[i]],dm[i]=dm[rs[i]];
        else if(!id[rs[i]]) id[i]=id[ls[i]],dm[i]=dm[ls[i]];
        else if(dm[ls[i]]<dm[rs[i]]) id[i]=id[ls[i]],dm[i]=dm[ls[i]];
        else if(dm[ls[i]]>=dm[rs[i]]) id[i]=id[rs[i]],dm[i]=dm[rs[i]];
    }
    void pushdown(int i){
        if(!lz[i]) return ;
        if(id[ls[i]]) dm[ls[i]]+=lz[i],lz[ls[i]]+=lz[i];
        if(id[rs[i]]) dm[rs[i]]+=lz[i],lz[rs[i]]+=lz[i];
        lz[i]=0;
    }
    void Am(int &i,int l,int r,int x,ll k){
        if(!i) i=++cnt; 
        if(l==r) return dm[i]=k,id[i]=l,void();
        int mid=l+r>>1;
        pushdown(i); 
        if(mid>=x) Am(ls[i],l,mid,x,k);
        else Am(rs[i],mid+1,r,x,k);
        pushup(i); 
    }
    ll Q(int i,int l,int r,int x){
//      printf("!!!%d\n",x); 
        if(l==r) return dm[i];
        int mid=l+r>>1;
        pushdown(i);
        if(mid>=x) return Q(ls[i],l,mid,x);
        else return Q(rs[i],mid+1,r,x);
    }
    void Dm(int i,int l,int r,int x){
        if(l==r) return id[i]=0,void();
        int mid=l+r>>1;
        pushdown(i);
        if(mid>=x) Dm(ls[i],l,mid,x);
        else Dm(rs[i],mid+1,r,x);
        pushup(i);
    }
    void D(int i,ll k){
        if(!i) return ;
        if(id[i]) dm[i]-=k,lz[i]-=k;
        pushdown(i);
    }
    #undef MAXN
}
void Machine(int t,int x,ll y){
    if(y<0){
        for(int d:Div[x])
            Seg::Dm(rt[d],1,m,t);
        st[++top]=t;
        return ;
    }
    for(int i=0,len=Div[x].size();i<len;i++)
        if(i<y%len) Seg::Am(rt[Div[x][i]],1,m,t,y/len+1);
        else Seg::Am(rt[Div[x][i]],1,m,t,y/len);
}
int main(){
    n=read(),m=read(),init();
    int lt=0,x,opt,t; ll y;
    for(int Case=1;Case<=m;Case++){
        opt=read(),x=read(),y=read()^lt;
        if(opt) --y,q[++N]=info(x,y),Machine(N,x,y);
        else{
            for(int d:Div[x]){
                Seg::D(rt[d],y);
//              printf("D : %d,%d\n",d,y);
//              printf("!!!!%d,%d\n",Seg::dm[rt[d]],Seg::id[rt[d]]);
                while(Seg::dm[rt[d]]<0&&Seg::id[rt[d]]){
                    t=Seg::id[rt[d]],q[t].y=0;
                    for(int g:Div[q[t].x])
                        q[t].y+=Seg::Q(rt[g],1,m,t);
//                  printf("cg : %d[%d]\n",t,q[t].y);
                    Machine(t,q[t].x,q[t].y);
                } 
            }
            printf("%d ",lt=top);
            sort(st+1,st+1+top);
            for(int i=1;i<=top;i++)
                printf("%d ",st[i]);
            printf("\n"),top=0;
        }
    }
    return 0;
}

有 n 个人，从 1\sim n 编号，第 i 个人可以被选中当且仅当区间 [l_i,r_i] 中被选中的人 \ge v_i。求最终哪些人被选中。

1\le n,m \le 10^5

也是很经典的减半警报器模型。

发现问题等价于给定 n 个区间，每个区间有一个权值。每次对包含 x 的区间权值 -1，求出哪些区间权值 \le 0。

其实就是把上一道题的 k 个单点改成了区间。

区间问题，去除限制基本都是去掉一个端点。因此可以考虑找到一个位置 p（先假设存在这样一个位置 p \in 所有的 [l,r]），把所有区间分成两部分。于是每个区间就被分成了一段前缀和一段后缀。此时的修改操作就变成了前缀减或后缀减，于是就可以维护了。

维护后的操作也是一样，若有均摊下去的区间权值 <0 就暴力重构，每个区间只会被重构 \log_2 V 次。

但是注意到上文的 p 不一定存在，所以还需要对序列分治，将每一层的 mid 作为一个 p，以一只 \log 的代价满足了 p 的条件。

总时间复杂度 O(n\log n\log V)。

代码有时间再补。傻逼文化课。