HDU 4267 A Simple Problemwith Integers(ツリー配列)
2796 ワード
HDU 4267 A Simple Problemwith Integers(ツリー配列)
分析:特定のkに対して、0からk-1までのk個の残数がある可能性がある.各1 a b k cコマンドについては、[a,b]に属するiおよびi%k=a%kのiにcを加えるだけでよいので、与えられたkおよびaを表すツリー配列C[k][a%k][MAXN]を構築し、ツリー配列C[k][a%k][MAXN]に対して操作を行う.私たちはcを加える必要がある数がもともとa,a+k,a+2*k,…(b/k)*k+a%kであることを知っています.だから私たちはC[k][a%k][MAXN]という木状の配列を与えられたkとaの時、下のマークだけを維持します.a,a+k,a+2*k,…(b/k)*k+a%kの値です.では、この木の配列の最初の要素であるA[k][a%k][1]に対応する元の配列A[MAXN]の下付きは?
K=1の場合、剰余は0しかないので、A[1]はA[1][0][1]を指す.
K=2の場合、残数が0の場合、A[2]はA[2][0][1]を指す.
K=2の場合、残数が1の場合、A[1]はAを指す[2][1][1].
では、命令1 a b k cについて、aがA[k][a%k][MAXN]の何番目の数なのか、どうやって知るのでしょうか.区間[a,b]がA[k][a%k][MAXN]に与える影響区間はどのくらいですか?
A[k][a%k][1]の頭元素はA[a%k]である場合もあれば、A[a%k+k]である場合もある(a%k=0の場合、A[0]は無効であるため).読み込みのたびにa-とb-を実行することで、全体区間を左に1桁ずらすことができます:A[0]からA[MAXN-1]まで、実行コマンド1 a b k cに影響はありません.検索するときはa-1の位置を検索すればいいです.
a-とb-を実行すると、
A[k][a%k][MAXN]が管理できる要素は小さいものから大きいものまで順に:a%k,a%k+k,...a%k+n*k
A[k][a%k][i]要素はa%k+(i-1)*kであるため(a/k)+1はA[k][a%k][MAXN]におけるaの番号であり、同様に[a,b]が管理できる最後の実行可能値の番号はp則:a%k+(p-1)*k<=b
コマンド2 aが得られた場合:
まずa-、次にsum(k,a%k,(a/k)+1)(ここでKが1から10まで、10回要求することに注意)で求めるのがA[a]の現在値である.
ACコード:296 ms
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=50000+100;
int c[11][10][MAXN];
int A[MAXN];
int lowbit(int x)
{
return x&(-x);
}
int sum(int k,int r,int x)
{
int res=0;
while(x>0)
{
res +=c[k][r][x];
x-=lowbit(x);
}
return res;
}
void add(int k,int r,int x,int v)
{
while(x<MAXN)
{
c[k][r][x]+=v;
x+=lowbit(x);
}
}
int main()
{
int n;
while(scanf("%d",&n)==1&&n)
{
for(int i=0;i<n;i++)
scanf("%d",&A[i]);
memset(c,0,sizeof(c));
int Q;
scanf("%d",&Q);
while(Q--)
{
int type;
scanf("%d",&type);
if(type==1)
{
int a,b,k,p;
scanf("%d%d%d%d",&a,&b,&k,&p);
a--;
b--;
add(k,a%k,a/k+1,p);
add(k,a%k,(b-a%k)/k+2,-p);
}
else if(type==2)
{
int a;
scanf("%d",&a);
a--;
int ans=A[a];
for(int k=1;k<=10;k++)
ans+=sum(k,a%k,a/k+1);
printf("%d
",ans);
}
}
}
return 0;
}