线段树专题 - 线段树+倍增

题意：给出三个操作，1 x y 【x，y】区间内的人都去下一个城市
2 x x的倍数的人去下一个城市
3 x查询x人在哪个城市

输入给出每个城市的下一个城市以及初始每个人在哪个城市。

思路：
先预处理出每个城市走2^0 , 2 ^1 ….2^n 步到哪个城市以及数据范围内的每个数的因子，然后对于2操作，累加次数，对于1操作，线段树更新加和，对于3操作，对其因子的累积加和并且加上区间的统计，然后利用预先的倍增处理得到最终城市。

线段树的m写成n，RE我一上午，吐血啊。

Code：

#include <bits/stdc++.h>
using namespace std;
const int AX = 4e5+66;
const int MAXN = 2e5+66;
int n , m ;
char a[AX];
int num[AX];
int s[AX<<2];
int lazy[AX<<2];
int site[AX];
std::vector<int> v[AX];
int bz[30][30];   //bz[i][j] i 城市的人走(1<<j)步到的城市
void init(){
    for( int i = 1 ; i < MAXN ; i++ ){
        for( int j = i ; j < MAXN ; j += i ){
            v[j].push_back(i);
        }
    }
    memset( lazy , 0 , sizeof(lazy) );
}

void pushDown( int rt , int L , int R ){
    if( lazy[rt] ){
        int mid = ( L + R ) >> 1 ;
        s[rt<<1] += ( mid - L + 1 ) * lazy[rt] ;
        s[rt<<1|1] += ( R - mid ) * lazy[rt];
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }
    return ;
}

void pushUp( int rt ){
    s[rt] = s[rt<<1] + s[rt<<1|1];
    return ;
}

void update( int  L , int R , int l , int r , int rt ){
    if( L <= l && R >= r ){
        s[rt] += ( r - l + 1 );
        lazy[rt] += 1;
        return ; 
    }
    pushDown(rt,l,r);
    int mid = ( l + r ) >> 1  ;
    if( L <= mid ) update( L , R , l , mid , rt << 1 );
    if( R > mid ) update( L , R , mid + 1 , r , rt << 1 | 1 );
    pushUp(rt);
}

int querry( int L , int R , int l , int r , int rt ){
    if( L <= l && R >= r ){
        return s[rt];
    }
    pushDown(rt,l,r);
    int ans = 0;
    int mid = ( l + r ) >> 1;
    if( L <= mid ) ans += querry( L , R , l , mid , rt << 1 );
    if( R > mid ) ans += querry( L , R ,mid + 1 , r , rt << 1 | 1 );
    return ans ;
}

int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",a);

    for( int i = 0 ; i < n ; i++ ){   //倍增
        bz[i][0] = a[i] - 'A';
    }
    for( int i = 1 ; i < 20 ; i++ ){
        for( int j = 0 ; j < n ; j++ ){
            bz[j][i] = bz[bz[j][i-1]][i-1]; 
        }
    }

    scanf("%s",a);
    for( int i = 1 ; i <= m ; i++ ){
        site[i] = a[i-1] - 'A' ;
    }

    int q ; 
    scanf("%d",&q);
    int x, y ;
    init();
    int op ;
    while( q-- ){
        scanf("%d",&op);
        if( op == 1 ){
            scanf("%d%d",&x,&y);
            update( x , y , 1 , m , 1 );
        }else if( op == 2 ){
            scanf("%d",&x);
            num[x] ++;
        }else{
            scanf("%d",&x);
            int ans = 0 ;
            for( int i = 0 ; i < (int)v[x].size() ; i++ ){
                ans += num[v[x][i]] ;
            }
            ans += querry( x , x , 1 , m , 1 );
            int pos = site[x];
            for( int i = 19 ; i >= 0 ; i-- ){
                if( ans & ( 1 << i ) ) pos = bz[pos][i];
            }
            printf("%c\n",(char)(pos+'A'));
        }
    }
    return 0 ;
}