luogu P7603 [THUPC2021] 鬼街

https://www.luogu.com.cn/problem/P7603

和gym 102331 F. Fast Spanning Tree 这题一样的套路

把监控事件的 y y y平均分配到每个管辖的区域里，作为其中一个阈值限制，然后每次加的时候如果有一个点碰到阈值就暴力把剩下的重新分配。

假设管辖的区域不超过 6 6 6个，因为每次碰到阈值，至少会让阈值减少 1 6 frac{1}{6} 61​,也就是说至少会变为原来的 5 6 frac{5}{6} 65​，容易得到时间复杂度为
O ( 6 n l o g n l o g 6 5 y ) O(6nlognlog_{frac{6}{5}}y) O(6nlognlog56​​y)

代码实现不难

code:

#include
#define fi first
#define se second
#define ll long long
#define N 400050
using namespace std;
vector d[N], ans;
void init(int n) {
    for(int i = 2; i <= n; i ++) if(!d[i].size()) 
        for(int j = i; j <= n; j += i) d[j].push_back(i);
}
int sz, ha[N], ban[N];
ll lim[N], a[N];
priority_queue > q[N];
void add(int u, ll o) {
    a[u] += o;
    while(q[u].size()) {
        auto x = q[u].top(); q[u].pop();
        if(ban[x.se]) continue;
        if(- x.fi <= a[u]) {    
            int gs = 0; ll s = 0;
            for(int y : d[ha[x.se]]) gs ++, s += a[y];

            if(s >= lim[x.se]) ban[x.se] = 1, ans.push_back(x.se);
            else {
                ll o = (lim[x.se] - s - 1) / gs + 1;
                for(int y : d[ha[x.se]]) q[y].push(make_pair(- (a[y] + o), x.se));
            }            
        } else {
            q[u].push(x); break;
        }
    }
}
int n, m;
int main() {
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%d%d", &n, &m); init(n);
    int lst = 0;
    while(m --) {
        int o, x; ll y;
        scanf("%d%d%lld", &o, &x, &y); y ^= lst;
        if(!o) {
            for(int it : d[x]) add(it, y);
            sort(ans.begin(), ans.end());
            lst = ans.size();
            printf("%d ", lst);
            for(int x : ans) printf("%d ", x); printf("n"); 
            vector xx; xx.clear();
            ans.swap(xx);
        } else {
            ++ sz; lim[sz] = y; ha[sz] = x;
            if(!y) {ans.push_back(sz); continue;}
            int gs = 0; ll s = 0;
            for(int y : d[x]) gs ++, lim[sz] += a[y], s += a[y];
            ll o = (lim[sz] - s - 1) / gs + 1;
            for(int y : d[x]) q[y].push(make_pair(- (a[y] + o), sz));
        }
    }
    return 0;
}