noip模拟赛浮游大陆的68号岛

题目描述

妖精仓库里生活着黄金妖精们，她们过着快乐，却随时准备着迎接死亡的生活。

换用更高尚的说法，是随时准备着为这个无药可救的世界献身。

然而孩子们的生活却总是无忧无虑的，幼体的黄金妖精们过着天真烂漫的生活，自然也无暇考虑什么拯救世界之类的重任。

有一天小妖精们又在做游戏。这个游戏是这样的。

妖精仓库的储物点可以看做在一个数轴上。每一个储物点会有一些东西，同时他们之间存在距离。

分析：x相对于[l,r]有3种可能的情况，要么在区间里，要么在区间左边，要么在区间右边。分类讨论，如果x在区间左边,ans = bi*(xi - x) + bi+1*(xi+1-x) + ...... + br*(xr - x).其中xi是第i个点的位置，x是x的位置.将结构相同的放在一起：ans=Σbixi - xΣbi.同理，如果x在区间右边：ans=xΣbi - Σbixi,在区间中的话就分左半区间和右半区间分别处理.得到这个式子就好办多了，前缀和就能搞定.只是要mod一个数，在做减法的时候一定要+模数，否则就会出现负数！！！

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = ;

ll n, m, d[], a[], sum[];

int main()

{

    scanf("%lld%lld", &n, &m);

    for (int i = ; i <= n; i++)

    {

        scanf("%lld", &d[i]);

        d[i] += d[i - ];

        d[i] %= mod;

    }

    for (int i = ; i <= n; i++)

        scanf("%lld", &a[i]);

    for (int i = ; i <= n; i++)

    {

        sum[i] = sum[i - ] + ((d[i] * a[i]) % mod);

        sum[i] %= mod;

        a[i] += a[i - ];

        a[i] %= mod;

    }

    for (int i = ; i <= m; i++)

    {

        long long x, l, r;

        scanf("%lld%lld%lld", &x, &l, &r);

        if (x <= l)

        {

            long long temp3 = (a[r] - a[l - ] + mod) % mod;

            long long temp = (temp3 * d[x]) % mod;

            long long temp2 = (sum[r] - sum[l - ] + mod) % mod;

            long long ans = (((temp2 - temp + mod) % mod) + mod) % mod;

            printf("%lld\n", ans);

        }

        else

            if (x >= r)

            {

                long long temp3 = (a[r] - a[l - ] + mod) % mod;

                long long temp = (temp3 * d[x]) % mod;

                long long temp2 = (sum[r] - sum[l - ] + mod) % mod;

                long long ans = (((temp - temp2 + mod) % mod) + mod) % mod;

                printf("%lld\n", ans);

            }

            else

            {

                long long temp5 = (a[r] - a[x] + mod) % mod;

                long long temp6 = (a[x - ] - a[l - ] + mod) % mod;

                long long temp3 = (sum[x - ] - sum[l - ] + mod) % mod;

                long long temp4 = (sum[r] - sum[x] + mod) % mod;

                long long temp1 = (temp5 * d[x]) % mod;

                long long ans1 = (((temp4 - temp1 + mod)%mod) + mod) % mod;

                long long temp2 = (d[x] * temp6) % mod;

                long long ans2 = (((temp2 - temp3 + mod) % mod) + mod) % mod;

                printf("%lld\n", (ans1 + ans2) % mod);

            }

    }

    return ;

}

巴特西

noip模拟赛浮游大陆的68号岛

题目描述

最新文章

热门文章

巴特西

noip模拟赛 浮游大陆的68号岛

题目描述

最新文章

热门文章

noip模拟赛浮游大陆的68号岛