ACM模版

描述


题解

这个题的题意有些繁琐，看了好久才看懂。

首先给定一个 1 n 序列，要你进行一系列变换，直到没有变化后，然后对该序列进行区间查询。

说起区间查询，很容易想到的就是线段树，可是这个题和线段树有一些差异，因为这个序列变化后是有规律的，划开奇偶看，分别是一个等差数列，所以我们需要处理出来等差数列的第一项就好了。剩下的区间查询就和线段树差不多了，不过不用建树，这倒是一个很有趣的变化。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

long long n, m, mod;
long long l, r, u, v;

long long cal(long long a, long long b, long long c)
{
    a -= b;
    if (a < 0)
    {
        a = -1;
    }
    else
    {
        a = a >> c;
    }

    long long B = b + a * (1ll << c);
    long long s;
    if ((++a) & 1)
    {
        s = (((B + b) >> 1) % mod) * (a % mod);
    }
    else
    {
        s = ((B + b) % mod) * ((a >> 1) % mod);
    }

    return s % mod;
}

long long _cal(long long ll, long long rr, long long c, int d)
{
    if (u > n)
    {
        return 0;
    }

    long long ans = 0;
    if (l > ll || r < rr)
    {
        long long m = (ll + rr) >> 1;
        if (l <= m)
        {
            ans += _cal(ll, m, c, d + 1);
        }
        if (r > m)
        {
            ans += _cal(m + 1, rr, c + (1ll << d), d + 1);
        }
        if (ans >= mod)
        {
            ans -= mod;
        }
    }
    else
    {
        ans = cal(v, c, d) - cal(u - 1, c, d);
        if (ans < 0)
        {
            ans += mod;
        }
    }

    return ans;
}

int main()
{
    scanf("%lld%lld%lld", &n, &m, &mod);

    while (m--)
    {
        scanf("%lld%lld%lld%lld", &l, &r, &u, &v);

        v = min(v, n);
        long long ans = _cal(1, n, 1, 0);

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

    return 0;
}