HDU6562-Lovers(硬核线段树)

题目链接:HDU6562-Lovers

题意:

有n个空串,然后有两种操作:1)给区间内每个字符串首尾加上x,例如1->212。2)把每个字符串当作数字,求区间和。

题解:

硬核线段树。

用sum1维护区间和,sum2维护区间长度,lazy1维护高位,lazy2维护低位,lazy3维护长度,tag标记区间是否被操作。

因为mod只有在除法时需要用逆元,在其他地方几乎可以任意使用,这道题甚至截取一段数字用mod。。。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int T;
int n, m;
int sum1[MAXN << 2], sum2[MAXN << 2];
//sum1维护区间和 sum2维护区间长度和
int lazy1[MAXN << 2], lazy2[MAXN << 2], lazy3[MAXN << 2], tag[MAXN << 2];
//lazy1维护高位 lazy2维护低位 lazy3维护长度 tag当前区间是否被操作
void pushup(int rt)
{
    sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % mod;
    sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % mod;
}
void pushdown(int l, int r, int rt)
{
    if (tag[rt])
    {
        int mid = (l + r) >> 1;
        tag[rt << 1] = tag[rt << 1 | 1] = 1;
        //向下更新lazy1
        lazy1[rt << 1] = (1ll * lazy3[rt << 1] * lazy1[rt] % mod + lazy1[rt << 1]) % mod;
        lazy1[rt << 1 | 1] = (1ll * lazy3[rt << 1 | 1] * lazy1[rt] % mod + lazy1[rt << 1 | 1]) % mod;
        //向下更新lazy2
        lazy2[rt << 1] = (1ll * lazy3[rt] * lazy2[rt << 1] + lazy2[rt]) % mod;
        lazy2[rt << 1 | 1] = (1ll * lazy3[rt] * lazy2[rt << 1 | 1] + lazy2[rt]) % mod;
        //向下更新lazy3
        lazy3[rt << 1] = 1ll * lazy3[rt << 1] * lazy3[rt] % mod;
        lazy3[rt << 1 | 1] = 1ll * lazy3[rt << 1 | 1] * lazy3[rt] % mod;
        //向下更新sum1
        sum1[rt << 1] = ((1ll * sum2[rt << 1] * lazy3[rt] % mod * lazy1[rt] % mod + 1ll * sum1[rt << 1] * lazy3[rt] % mod) % mod + 1ll * lazy2[rt] * (mid - l + 1) % mod) % mod;
        sum1[rt << 1 | 1] = ((1ll * sum2[rt << 1 | 1] * lazy3[rt] % mod * lazy1[rt] % mod + 1ll * sum1[rt << 1 | 1] * lazy3[rt] % mod) % mod + 1ll * lazy2[rt] * (r - mid) % mod) % mod;
        //向下更新sum2
        sum2[rt << 1] = 1ll * sum2[rt << 1] * lazy3[rt] % mod * lazy3[rt] % mod;
        sum2[rt << 1 | 1] = 1ll * sum2[rt << 1 | 1] * lazy3[rt] % mod * lazy3[rt] % mod;
        //取消标记
        tag[rt] = 0;
        lazy1[rt] = lazy2[rt] = 0;
        lazy3[rt] = 1;
    }
}
void build(int l, int r, int rt)
{
    //初始化
    lazy1[rt] = lazy2[rt] = 0;
    lazy3[rt] = 1;
    tag[rt] = 0;
    sum1[rt] = 0;
    sum2[rt] = 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int L, int R, int x, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        tag[rt] = 1;
        lazy1[rt] = (1ll * lazy3[rt] * x % mod + lazy1[rt]) % mod;
        lazy2[rt] = (10ll * lazy2[rt] + x) % mod;
        lazy3[rt] = 10ll * lazy3[rt] % mod;
        sum1[rt] = (10ll * ((1ll * sum2[rt] * x % mod + sum1[rt] % mod) % mod) % mod + x * (r - l + 1)) % mod;
        sum2[rt] = 100ll * sum2[rt] % mod;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        update(L, R, x, l, mid, rt << 1);
    if (R > mid)
        update(L, R, x, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum1[rt];
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid)
        res += query(L, R, l, mid, rt << 1);
    res %= mod;
    if (R > mid)
        res += query(L, R, mid + 1, r, rt << 1 | 1);
    res %= mod;
    return res;
}
int main()
{
    scanf("%d", &T);
    int icase = 0;
    while (T--)
    {
        scanf("%d%d", &n, &m);
        build(1, n, 1);
        printf("Case %d:\n", ++icase);
        while (m--)
        {
            char op[10];
            int l, r, x;
            scanf("%s", op);
            scanf("%d%d", &l, &r);
            if (op[0] == 'w')
            {
                scanf("%d", &x);
                update(l, r, x, 1, n, 1);
            }
            else
                printf("%d\n", query(l, r, 1, n, 1));
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。