题解 P5068【[Ynoi2015] 我回来了】

· · 题解

题解

提供一种比较好写的在线做法。

考虑对于任意的 1\le x\le n，维护出伤害值 d=x 时法术的施放次数。设 d=x 时答案为 c_x，那就意味着 (0,x],(x,2x],\dots,((c_x-2)x,(c_x-1)x] 都至少有一个血量在这个区间中的随从。所以 \sum_{x=1}^n c_x\le \sum_{x=1}^n \lfloor n/x\rfloor=\mathcal{O}(n\ln n)。

因此，我们只需要维护出，当增加一个随从时，有哪些位置的 c_x 会增加。开一个树状数组记录答案，对于增加的这些位置，在树状数组上单点修改即可。

设 L_x=(c_x-1)x+1,R_x=c_x\cdot x。当增加一个血量为 h 的随从时，我们要做的就是找出所有满足 h\in [L_x,R_x] 的 x，然后对于这些 x 暴力更新 c_x，同时 L_x,R_x 也随之改变。

开一棵线段树，将每个 [L_x,R_x] 拆成线段树上的 \mathcal{O}(\log n) 个区间。在每个线段树节点上开一个 vector<int>，记录这里的区间的下标。对于新加入的血量为 h 的随从，只需要在包含 h 的 \log n 个线段树节点上更新所有的 c_x，然后将 vector 清空。

在线段树上如何更新一个 x 的 c_x？再开一个树状数组记录所有随从的血量，每次更新时看看新的 [L_x,R_x] 之间是否有随从即可。

有一个实现细节：这样做可能导致线段树的 vector 内有一些本应被删除、但未被删除的元素，只需在下一次遍历时，检查 [L_x,R_x] 与线段树节点的区间是否有交即可，若交集为空则直接跳过。

时间复杂度 \mathcal{O}(n\log^2 n+m\log n)。

代码

只写了 1.5k。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
using ll=long long;
const int N=1e5+5;
int n,m,L[N],R[N];
struct BIT{
    int t[N];
    void Add(int p,int k){for(;p<=n;p+=p&-p) t[p]+=k;}
    int Query(int p){int res=0;for(;p;p-=p&-p) res+=t[p];return res;}
}bit,exist;
struct SegTree{
    vector<int> s[N*4];
    void Insert(int p,int id,int l,int r){
        if(L[id]<=l&&r<=R[id]){s[p].push_back(id);return;}
        int mid=(l+r)/2;
        if(L[id]<=mid) Insert(p*2,id,l,mid);
        if(R[id]>mid) Insert(p*2+1,id,mid+1,r);
    }
    void Oper(int p,int pos,int l,int r){
        for(int x:s[p]){
            if(l>R[x]||r<L[x]) continue;
            int tot=0;
            while(L[x]<=n){
                if(exist.Query(R[x])-exist.Query(L[x]-1)==0) break;
                L[x]=min(n+1,L[x]+x),R[x]=min(n,R[x]+x);
                ++tot;
            }
            bit.Add(x,tot);
            if(L[x]<=n) Insert(1,x,1,n);
        }
        s[p].clear();
        if(l==r) return;
        int mid=(l+r)/2;
        if(pos<=mid) Oper(p*2,pos,l,mid);
        else Oper(p*2+1,pos,mid+1,r);
    }
}seg;
int main(){
    #ifndef zyz
    ios::sync_with_stdio(false),cin.tie(nullptr);
    #endif
    cin>>n>>m;
    For(i,1,n) L[i]=1,R[i]=i,seg.Insert(1,i,1,n),bit.Add(i,1);
    For(_,1,m){
        int op;cin>>op;
        if(op==1){
            int h;cin>>h;
            exist.Add(h,1);
            seg.Oper(1,h,1,n);
        }else{
            int l,r;cin>>l>>r;
            cout<<bit.Query(r)-bit.Query(l-1)<<'\n';
        }
    }
    return 0;
}