117 D Not Quick Transformation

再帰タグを作った。

問題

数列aに対して、その偶数番目の項だけを取り出した数列をeven(a),
奇数番目の項だけを取り出した数列をodd(a)とする。
F(a)=F(odd(a))+F(even(a)) (aの項数が2以上)
F(a)=a (aの項数が1)

と定義する。
整数n,u,v,modが与えられる。
a={1,2,3,4,5,...,n}と定義するとき、
F(a)について以下のクエリがm個与えられるので答えよ。

  • F(a)のl項目からr項目までのうち、u以上v以下の項の和を求める。

制約条件

n,u,v≦10^18
m≦10^5
mod≦10^9

方針

F(a)のSegment Treeを考える。(実際には配列は持たないで、添字だけで考える)
例えば数列{1,2,3,4,5,6,7,8}について一回操作を行うと、
{1,3,5,7,2,4,6,8}になる。
次は{1,5,3,7,2,6,4,8}になる。(ここで操作は終了してF(a)が得られる)


これを観察すると、

  • 0回目の操作の後は長さ8,初項1,階差1の等差数列になっている
  • 1回目の操作の後は長さ4,初項1,階差2の等差数列、長さ4,初項2,階差2の等差数列に分かれる
  • 2回目の操作の後は
    • 前半が長さ2,初項1,階差4の等差数列、長さ2,初項3,階差4の等差数列に分かれる
    • 後半が長さ2,初項2,階差4の等差数列、長さ2,初項4,階差4の等差数列に分かれる

……となっている。

範囲に数列がすっぽり入る場合、和は等差数列の和と変わらない(順番を入れ替えただけ)
なので、等差数列の和の公式を使ってやればよい。


範囲に数列が入らない場合、範囲を分割して再帰的に和を取る。Segment Treeと同じ。
そのとき、初項と階差は引数に持たせて管理する。

ソースコード

int mod;
ll u,v;
int query(ll l,ll r,ll a,ll b,ll a0,ll d){
  if(r<a||b<l)return 0;
  if(l<=a&&b<=r){
    ll s=a0,t=a0+d*(b-a);
    if(s<u)s+=((u-s)/d+((u-s)%d!=0))*d;
    if(t>v)t-=((t-v)/d+((t-v)%d!=0))*d;
    
    if(s>t)return 0;
    ll n=(t-s)/d+1;
    s+=t; if(s%2==0)s/=2; else n/=2;
    return n%mod*(s%mod)%mod;
  }
  return (query(l,r,a,(a+b)/2,a0,d*2)+query(l,r,(a+b)/2+1,b,a0+d,d*2))%mod;
}
void run(){
  ll n,l,r; int m;
  cin>>n>>m>>mod;
  rep(i,m){
    cin>>l>>r>>u>>v;
    cout<<query(l,r,1,n,1,1)<<endl;
  }
}