带除法的区间问题

问题一

有一个区间, 要求支持单点加减一个不超过C的数字, 区间除法和求和。

区间在任意时刻保证任意元素都为正。

解法一

除法操作时判断区间内是否有大于等于除数的数, 如果有暴力左右递归处理即可。

均摊复杂度为O(NlogC), 证明: 忽略除数为1, 对于每个数字num, 假设num大于除数, 那么num至多被除上log(num)次就会变成0。每次操作顶多会把某个num加上C, 增加log(C)次对num的访问。总复杂度均摊下来是O(NlogC)。

问题二

有一个区间, 要求支持区间加减一个不超过C的数字, 区间除法和求和求最小值。

区间在任意时刻保证任意元素都为正。

解法二

由于这次是区间加减, 那么仍然使用以上方法每次区间加减为除法贡献的访问次数将会达到NlogC级别, 复杂度就不对了。

先忽略除以1的操作, 不考虑负数的情况, 明确一点, 对于任意一个区间的min和max, 它们在不超过log(max)次操作后会变为相等。

首先用线段树的方式对序列进行区间剖分, 剖分成2N个区间。

对于每次加法操作, 假设加法区间为[l, r], 那么线段树上完全包含区间[l, r]的区间(节点)不超过logN个, 包含点l的区间不超过logN个, 包含点r的区间也不超过logN个。

加法操作只会对线段树2N个区间中以上不超过3logN个区间的min和max差值产生影响, 使这些区间的min和max的差值最多增加C。

那么对于着3logN个区间中的每个区间, 除法操作必须访问至多log(max)次才能让min值和max值重新变为一样的。

形式化地, 设有A次区间加操作, B次除法操作, 除法操作递归的区间总数量为[latex]\sum_{i=1}^B log_2(N)+x_i[/latex], 其中[latex] \sum_{i=1}^B x_i \le A\times log_2(N) log_2(C)[/latex]。

最终总复杂度[latex]O(Nlog_2(N)log_2(C))[/latex]。

问题三

有一个区间, 要求支持区间加减一个不超过C的数字, 区间除法和求和求最小值。

区间 不 在任意时刻保证任意元素都为正, 除法向下取整。

解法三

除法操作时若当前区间[latex]min-\lfloor \frac{min}{d} \rfloor = max-\lfloor \frac{max}{d} \rfloor[/latex]直接转化为区间加, 否然向下递归即可, 复杂度证明类似。代码简单粗暴好写。

例题

source:雅礼2018, Day1

代码/模板

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <iostream>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
const int MAXN = 100010;
namespace IBT {
    const int MAXD = MAXN*5;
    int mx[MAXD], mn[MAXD], lz[MAXD];
    LL sum[MAXD];
    inline void updata (int u) {
        mx[u] = max(mx[u<<1], mx[(u<<1)+1]);
        mn[u] = min(mn[u<<1], mn[(u<<1)+1]);
        sum[u] = sum[u<<1]+sum[(u<<1)+1];
    }
    inline int downdiv (int a, int b) {
        if(a < 0) return (a+1)/b-1;
        else return a/b;
    }
    int * src;
    void build (int u, int l, int r) {
        if(l == r) {mn[u] = mx[u] = sum[u] = src[l]; return ;}
        int mid = (l+r)>>1;
        build(u<<1, l, mid);
        build((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline void addNode (int u, int l, int r, int val) {
        sum[u] += (LL)val*(r-l+1);
        lz[u] += val;
        mx[u] += val, mn[u] += val;
    }
    inline void pushdown (int u, int l, int mid, int r) {
        if(lz[u]) {
            addNode(u<<1, l, mid, lz[u]);
            addNode((u<<1)+1, mid+1, r, lz[u]);
            lz[u] = 0;
        }
    }
    int agl, agr, agv;
    inline void add (int u, int l, int r) {
        if(l > agr || r < agl) return ;
        if(agl <= l && r <= agr) {addNode(u, l, r, agv); return ;}
        int mid = (l+r)>>1;
        pushdown(u, l, mid, r);
        add(u<<1, l, mid);
        add((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline void div (int u, int l, int r) {
        if(l > agr || r < agl) return ;
        if(agl <= l && r <= agr) {
            int delta1 = mx[u]-downdiv(mx[u], agv);
            int delta2 = mn[u]-downdiv(mn[u], agv);
            if(delta1 == delta2) {
                addNode(u, l, r, -delta1);
                return ;
            }
        }
        int mid = (l+r)>>1;
        pushdown(u, l, mid, r);
        div(u<<1, l, mid), div((u<<1)+1, mid+1, r);
        updata(u);
    }
    inline int qmin (int u, int l, int r) {
        if(l > agr || r < agl) return 0x3f3f3f3f;
        if(agl <= l && r <= agr) return mn[u];
        int mid = (l+r)>>1;
        pushdown(u, l, mid, r);
        return min(qmin(u<<1, l, mid), qmin((u<<1)+1, mid+1, r));
    }
    inline LL qsum (int u, int l, int r) {
        if(l > agr || r < agl) return 0;
        if(agl <= l && r <= agr) return sum[u];
        int mid = (l+r)>>1;
        pushdown(u, l, mid, r);
        return qsum(u<<1, l, mid)+qsum((u<<1)+1, mid+1, r);
    }
}
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        ret = ret*10+(ch-'0');
    return flg ? -ret : ret;
}
int A[MAXN];
int main () {
    int N = getInt(), Q = getInt();
    for(int i = 1; i<=N; i++)
        A[i] = getInt();
    IBT::src = A, IBT::build(1, 1, N);
    while(Q --) {
        int typ = getInt();
        IBT::agl = getInt() + 1;
        IBT::agr = getInt() + 1;
        if(typ <= 2) IBT::agv = getInt();
        if(typ == 1) IBT::add(1, 1, N);
        else if(typ == 2) IBT::div(1, 1, N);
        else if(typ == 3) printf("%d\n", IBT::qmin(1, 1, N));
        else printf("%lld\n", IBT::qsum(1, 1, N));
    }
}