欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51nod1617(codeforces117D)奇偶数组

程序员文章站 2022-03-03 07:59:29
...

题目大意

a是一个包含n个元素的数组。对a中的元素进行1-n编号。
定义“偶数组” even, eveni=a2i(1≤2i≤n) ,即“偶数组” even是由数组a中编号为偶数的元素组成的。
定义“奇数组” odd, oddi=a2i1(1≤2i−1≤n) ,即“奇数组”odd是由数组a中编号为奇数的元素组成的。

然后,我们定义一个转换方程F(a),F(a)的结果为一个数组,过程如下:
当n>1时,F(a)=F(odd)+F(even),
其中”+”是合并的意思(如[1,3]+[2,4]=[1,3,2,4]),odd和even为前面所描述的数组。
当n=1时,F(a)=a。

a的初始值为n个数,元素的值为1,2,3……n。
b为a经过变换后的数组,即b=F(a)。题目将会给出m个查询(l,r,u,v)。
你的任务是对b中第l个到第r个元素(含),并且元素的值在[u,v]区间内的元素进行求和,并对mod取模。
用公式表示如下: (∑u≤bi≤v&&l≤i≤r bi) % mod 。

Input

单组测试数据
第一行有三个正整数n,m,mod(1≤n≤10^18,1≤m≤10^5,1≤mod≤10^9)
分别表示a中元素的数量,查询的个数和取模的底数。
接下来有m行
每行有四个整数l,r,u,v(1≤l≤r≤n,1≤u≤v≤10^18)

Output

m行,每行一个整数,查询的结果。

Input示例
4 5 10000
2 3 4 5
2 4 1 3
1 2 2 4
2 3 3 5
1 3 3 4

Output示例
0
5
3
3
3

Solution

题目中奇偶数组的分组是递归进行的,基本没什么规律,而n又有很大,无法直接模拟。从“奇偶数组”的角度考虑,是行不通的。

但我们如果只看题目的要求,就是求l到r区间的和,再加上一些限制条件——这不是线段树吗?而且只需log的复杂度就能完成。
再手动模拟一些小数据,发现线段树每个节点上记下的排列都是等差数列。以lay表示层数,则每个节点上等差数列的公差是2lay1,且如果每个节点的第一项是headi,那么它左儿子节点的第一项headlefti=headi,它的右儿子节点的第一项headrighti=headi+2lay1。不用建出这棵线段树,也能直接计算出这个节点的值。

关于限制条件u,v,我们可以先计算1~u-1的区间,再计算1~v的区间,就能较方便地解决问题。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mi[1000],mo;
ll read()
{
    ll ans=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9')
    {
        ans=ans*(ll)10+(ll)(ch-'0');
        ch=getchar();
    }
    return ans;
}
ll query(ll l,ll r,ll x,ll y,ll k,ll head,int lay)
{
    if (l==r)
    {
        if (head<=k) return head;
        return 0;
    }
    if (l==x&&y==r)
    {
        if (head>k) return 0;
        ll x1=r-l+1LL;
        ll x2=((k-head)/mi[lay-1])+1LL;
        x1=min(x1,x2);
        if (!x1) return 0;
        ll fir=head,las=head+(x1-1LL)*mi[lay-1];
        fir+=las;
        if (fir&1) x1>>=1;
        else fir>>=1;//计算时小心一点,先把2除掉再取模。
        ll sum1=((fir%mo)*(x1%mo))%mo;
        return sum1;
    }
    ll mid=(l+r)>>1;
    if (mid<x) return query(mid+1,r,x,y,k,head+mi[lay-1],lay+1);
    if (mid>=y) return query(l,mid,x,y,k,head,lay+1);
    return (query(l,mid,x,mid,k,head,lay+1)+query(mid+1,r,mid+1,y,k,head+mi[lay-1],lay+1))%mo; 
} 
int main()
{
    ll n,m;
    scanf("%lld%lld%lld",&n,&m,&mo);
    mi[0]=1LL;
    for (int i=1;i<=62;i++)
    {
        mi[i]=mi[i-1]*2LL;//预处理2的幂次时千万不能取模
    }
    while (m--)
    {
        ll l=read(),r=read(),u=read(),v=read();
        if (l>r||u>v) 
        {
            puts("0");
            continue;
        }
        ll ans=query(1LL,n,l,r,v,1LL,1);
        ans-=query(1LL,n,l,r,u-1LL,1LL,1);
        ans=(ans%mo+mo)%mo;
        printf("%lld\n",ans);       
    }   
    return 0;
}