hdu 4267--A Simple Problemwith Integers(ツリー配列)

タイトルリンク:クリックしてリンクを開く
n個の数のシーケンスがあり、1 a b k cの区間[a,b]内のiを2つの操作があり、(i-a)%k==0を満たすとi番目の数にcが加算され、
2 a番目のa番目の数の値は何かを尋ね、まずn番目の数の初期値を与え、それからq回の操作で、毎回の操作を完了し、質問であれば、その値を出力する.
最初に線分ツリーを用いて、1回の操作1 a b k cにおける[a,b]が現在の線分ツリーの1つの小段[l,r]を覆うことができれば、この小段におけるiに対して、
(i-a)%k==0を満たすと、i番目の数の値にcが加算され、式を変形して((i-l)+(l-a))%k==0とする.これは、与えられたiにとって、(i-l)の値が決定されるので、k(1〜10)を列挙するだけで、i番目の数にどの程度の操作が影響するかを計算することができ、異なる操作に対してkと(l-a)%kの値が同じであれば、では、彼らの役割のiは同じで、合併することができます.cl[rt][k][(l-a)%k]は、線分ツリーがこのように構築され、質問ごとにlog(n)できる時間クエリのi番目の数の修正状況に対して、初期値を加えると最終的な結果となる.
しかし、これはずっとMLEなので、木の配列に変換し、1回の修正を2つの部分に分解します.
1 a b k cは1 a n k cと1(b-a)/k*k+a+k n k-cに分解され、(r-l)/k*k+l+kはaからkの最初のbを超える数を絶えず加算し、従来の動作が変わらないことを保証することができる.
配列に変換すると,元の各セグメントのlを累積したときのノードの位置に変換し,同じ方法でデータを格納し,その前に存在するすべての操作がその影響を求めることで最終結果を算出する.

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
#include <algorithm>
using namespace std ;
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL __int64
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define root 1,n,1
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define int_rt int l,int r,int rt
const int mod=1e9+7;
const int MAXN = 50000+10 ;
int cl[MAXN][11][11] , a[MAXN] ;
int n , q ;
int lowbit(int x) {
    return x & -x ;
}
void add(int a,int k,int c) {
    int i = a , temp ;
    while( i <= n ) {
        temp = (i-a)%k ;
        if( temp == 0 ) temp = k ;
        cl[i][k][temp] += c ;
        i += lowbit(i) ;
    }
}
int sum(int a) {
    int i = a , j , temp , ans = 0 ;
    while( i ) {
        for(j = 1 ; j < 11 ; j++)
            ans += cl[i][j][ j-(a-i)%j ] ;
        i -= lowbit(i) ;
    }
    return ans ;
}
int main() {
    int i , j , k , l , r , c ;
    while( scanf("%d", &n) != EOF ) {
        for(i = 1 ; i <= n ; i++)
            scanf("%d", &a[i]) ;
        memset(cl,0,sizeof(cl)) ;
        scanf("%d", &q) ;
        while( q-- ) {
            scanf("%d", &i) ;
            if( i == 1 ) {
                scanf("%d %d %d %d", &l, &r, &k, &c) ;
                add(l,k,c) ;

                add((r-l)/k*k+l+k,k,-c) ;
            }
            else {
                scanf("%d", &i) ;
                printf("%d
", sum(i)+a[i]) ;
            }
        }
    }
    return 0 ;
}