欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-13 11:31:01
...

线段树专题 - 线段树+倍增
题意:给出三个操作,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 ;
}