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; } }