首页 > 代码库 > bzoj2752

bzoj2752

2024-10-10 18:47:39   213人阅读

线段树+概率

今天这道题爆零了，奥妙重重。

其实我们可以把式子化成这样:sigma((i-l+1)*(r-i+1)*ai) 这里r减了1

然后展开,(1-l)*(r+1)*ai+(r+l)*i*ai-i*i*ai

我们发现除了含有i的项其他都可以提到外面，也就是说我们要维护ai,i*ai,i*i*ai三个量。

那么就用线段树维护，打标记时用数列公式即可。

技术分享 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, m;
struct seg {
    ll tag[N << 2], tree[N << 2][4];
    void pushdown(int x, int l, int r)
    {
        if(!tag[x]) return;
        tag[x << 1] += tag[x];
        tag[x << 1 | 1] += tag[x];
        int mid = (l + r) >> 1;
        tree[x << 1][1] += tag[x] * (ll)(mid - l + 1ll);
        tree[x << 1 | 1][1] += tag[x] * (ll)(r - mid);
        tree[x << 1][2] += tag[x] * (ll)(l + mid) * (ll)(mid - l + 1) / 2ll;
        tree[x << 1 | 1][2] += tag[x] * (ll)(r + mid + 1ll) * (ll)(r - mid) / 2ll;
        tree[x << 1][3] += tag[x] * ((ll)mid * (ll)(mid + 1ll) * (ll)(2ll * mid + 1ll) - (ll)(l - 1ll) * (ll)l * (ll)(2ll * l - 1ll)) / 6ll;
        tree[x << 1 | 1][3] += tag[x] * ((ll)r * (ll)(r + 1ll) * (ll)(2ll * r + 1ll) - (ll)mid * (ll)(mid + 1ll) * (ll)(2ll * mid + 1ll)) / 6ll;
        tag[x]= 0ll;
    }
    void update(int l, int r, int x, int a, int b, ll delta)
    {
        if(l > b || r < a) return;
        if(l >= a && r <= b)
        {
            tag[x] += delta;
            tree[x][1] += (ll)(r - l + 1ll) * delta;
            tree[x][2] += (ll)(l + r) * (ll)(r - l + 1) / 2ll * delta;
            tree[x][3] += ((ll)r * (ll)(r + 1ll) * (2ll * r + 1) - (ll)(l - 1ll) * (ll)l * (ll)(2ll * l - 1ll)) / 6ll * delta;
            return;
        }
        pushdown(x, l, r);
        int mid = (l + r) >> 1;
        update(l, mid, x << 1, a, b, delta);
        update(mid + 1, r , x << 1 | 1, a, b, delta);
        for(int i = 1; i <= 3; ++i)
            tree[x][i] = tree[x << 1][i] + tree[x << 1 | 1][i];
    }
    ll query(int l, int r, int x, int a, int b, int type)
    {
        if(l > b || r < a) return 0ll;
        if(l >= a && r <= b) return tree[x][type];
        pushdown(x, l, r);
        int mid = (l + r) >> 1;
        return (query(l, mid, x << 1, a, b, type) + (query(mid + 1, r, x << 1 | 1, a, b, type)));
    }
} t;
ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a % b); 
}
int main()
{
//    freopen("c.in", "r", stdin);
//    freopen("c.out", "w", stdout);
    scanf("%d%d", &n, &m);
    --n;
    while(m--)
    {
        char s[10]; int l, r; ll delta; scanf("%s", s);
        if(s[0] == ‘C‘)
        {
            scanf("%d%d%lld", &l , &r, &delta);
            --r;
            t.update(1, n, 1, l, r, delta);
        }
        if(s[0] == ‘Q‘)
        {
            scanf("%d%d", &l, &r);
            --r;
            ll T1 = t.query(1, n, 1, l, r, 1);
            ll T2 = t.query(1, n, 1, l, r, 2);
            ll T3 = t.query(1, n, 1, l, r, 3);
            ll ans = (ll)(1ll - l) * (ll)(r + 1ll) * T1 + (ll)(r + l) * T2 - T3;
            ll T4 = (ll)(r - l + 2ll) * (ll)(r - l + 1ll) / 2ll;
            ll T = gcd(ans, T4);
            printf("%lld/%lld\n", ans / T, T4 / T);
        }
    }
//    fclose(stdin); fclose(stdout);
    return 0;
}
View Code

 

bzoj2752


联系
我们