51nod1617(codeforces117D)奇偶数组
题目大意
a是一个包含n个元素的数组。对a中的元素进行1-n编号。
定义“偶数组” even,
定义“奇数组” odd,
然后,我们定义一个转换方程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表示层数,则每个节点上等差数列的公差是
关于限制条件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;
}