线段树专题 - 线段树+倍增
程序员文章站
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 ;
}
上一篇: MySql 5.7 windows 安装
下一篇: 线段树专题