[51Nod 1617] 奇偶数组

原题：CodeForces 117D

Description

是一个包含n个元素的数组。对a中的元素进行1-n编号。
定义“偶数组”even，eveni=a2i(1≤2i≤n） ，即“偶数组” even是由数组a中编号为偶数的元素组成的。
定义“奇数组” odd，oddi=a2i−1(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 ≤ rbi) % mod 。

样例解释：
b=F(a)=F([1,2,3,4])
第1步，F([1,2,3,4])= F([1,3])+ F([2,4])
第2步，F([1,3])= F([1])+ F([3])=[1]+[3]=[1,3]
第3步，F([2,4])= F([2])+ F([4])=[2]+[4]= [2,4]
第4步，b=F(a )=F([1,2,3,4])= F([1,3])+ F([2,4])= [1,3]+ [2,4]=[1,3,2,4]

所以b= [1,3,2,4].

Solution

既然询问是同时在变换后序列[L,R]内以及变换前[u,v]内

我们不妨只考虑在变换后[1,R]内以及变换前[1,v]内，减一减就可以得到答案

可以发现原序列一开始为公差为1的等差数列，变换后就变成左右两个公差为2的等差数
列

考虑分治
设solve(lim,first,num,d,len)表示我们当前处理的是首项为first，公差为d，项数为len的等差数列。要计算这个序列变换完以后区间[1,num]中所有不超过lim的数的和

设mid=⌈len2⌉

当前等差数列经过一次变换会变成一个首项为first，公差为d*2，项数为mid的等差数列（原等差数列的第奇数项）加上一个首项为first+d,公差为d*2，项数为len-mid的等差数列（原等差数列的第偶数项）

如果num≥mid，那么左边的等差数列无论怎么变换，它都是要全部算进去的，那么直接计算其中不超过lim的数的和即可，然后递归右边solve(lim,first+d,num−mid,d∗2,len−mid)

否则，递归左边solve(lim,first,num,d∗2,mid)
这样回答一次询问就是logN的，总复杂度O(mlogN)

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define LL long long
using namespace std;
LL n,mo;
int m;
LL calc(LL fs,LL num,LL lim,LL d)
{
    if(lim<fs) return 0; 
    lim=(lim-fs)/d*d+fs;
    LL ls=min(lim,fs+d*(num-1));
    LL v1=((ls-fs)/d+1),v2=(fs+ls);
    if(v1%2==0) v1/=2;
    else v2/=2;
    return (v1%mo)*(v2%mo)%mo;
}
LL doit(LL lim,LL fs,LL d,LL num,LL le)
{
    if(num==0) return 0;
    if(le==1) return (fs<=lim)?fs:0;
    LL mid=(le+1)/2;
    if(num>=mid) return (calc(fs,mid,lim,d*(LL)2)+doit(lim,fs+d,d*(LL)2,num-mid,le-mid))%mo;
    else return doit(lim,fs,d*(LL)2,num,mid);
}
int main()
{
    freopen("1617.in","r",stdin);
    freopen("1617.out","w",stdout);
    cin>>n>>m>>mo;
    fo(i,1,m)
    {
        LL l,r,x,y;
        scanf("%lld%lld%lld%lld",&l,&r,&x,&y);
        printf("%lld\n",((doit(y,1,1,r,n)-doit(x-1,1,1,r,n)+mo)%mo-(doit(y,1,1,l-1,n)-doit(x-1,1,1,l-1,n)+mo)%mo+mo)%mo);
    }
}