HDU 4267グループセグメントツリー
2012年长春网赛的题目,光头了...悲剧
今はやったことを知っています.
パケットは[a,b]区間内でk余mを除いたグループに分けられる.このようにグループごとに更新すれば良いのです.
この問題の突破点はkが小さいことにある.
線分ツリー:
今はやったことを知っています.
パケットは[a,b]区間内でk余mを除いたグループに分けられる.このようにグループごとに更新すれば良いのです.
この問題の突破点はkが小さいことにある.
線分ツリー:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MN 50010
using namespace std;
int tree[MN<<2][55];
int flag[MN<<2];
int b[11][11],num[MN];
void build( int l,int r,int rt )
{
flag[rt]=0;
for( int i=0;i<55;i++ )
tree[rt][i]=0;
if( l==r )
return ;
int m=(l+r)>>1;
build( l,m,rt<<1 );
build( m+1,r,rt<<1|1 );
}
void pushDown( int rt )
{
if( flag[rt] )
{
flag[rt<<1|1]=flag[rt<<1]=flag[rt];
flag[rt]=false;
for( int i=0;i<55;i++ )
{
tree[rt<<1][i]+=tree[rt][i];
tree[rt<<1|1][i]+=tree[rt][i];
tree[rt][i]=0;
}
}
}
int query( int pos,int l,int r,int rt )
{
if( l==r )
{
int ret=0;
for( int i=1;i<=10;i++ )
ret+=tree[rt][b[i][pos%i]];
return ret;
}
pushDown(rt);
int m=(l+r)>>1;
if( pos<=m )
return query( pos,l,m,rt<<1 );
else
return query( pos,m+1,r,rt<<1|1 );
}
void update( int mod,int L,int R,int k,int c,int l,int r,int rt )
{
if( L<=l&&r<=R )
{
tree[rt][b[k][mod]]+=c;
flag[rt]=true;
return ;
}
int m=(l+r)>>1;
if( L<=m )
update( mod,L,R,k,c,l,m,rt<<1 );
if( m<R )
update( mod,L,R,k,c,m+1,r,rt<<1|1 );
}
int main()
{
int cnt=0;
for( int i=1;i<11;i++ )
for( int j=0;j<i;j++ )
b[i][j]=cnt++;
int N,M;
while( scanf("%d",&N)!=EOF )
{
build(1,N,1);
for( int i=1;i<=N;i++ )
scanf( "%d",&num[i] );
scanf( "%d",&M );
getchar();
while( M-- )
{
char str[111];
gets(str);int a,b,k,c;
if( sscanf( str,"2 %d",&a ) )
printf( "%d
",query(a,1,N,1)+num[a] );
else if( sscanf( str,"1 %d %d %d %d",&a,&b,&k,&c) )
update( a%k,a,b,k,c,1,N,1 );
}
}
return 0;
}
配列配列:#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MN 55555
using namespace std;
int tree[MN][11][11];
int N;
void update( int mod,int pos,int k,int c )
{
int x=pos;
while( x )
{
tree[x][k][mod]+=c;
x-=x&(-x);
}
}
int query( int a,int x )
{
int ret=0;
while( x<=N )
{
for( int i=1;i<=10;i++ )
ret+=tree[x][i][a%i];
x+=x&(-x);
}
return ret;
}
int main()
{
while( scanf("%d",&N)!=EOF )
{
memset( tree,0,sizeof(tree) );
int num[MN];
for( int i=1;i<=N;i++ )
scanf( "%d",&num[i] );
int M;
scanf( "%d",&M );
getchar();
while( M-- )
{
char str[111];
gets(str);
int a,b,k,c;
if( sscanf(str,"2 %d",&a) )
printf( "%d
",query(a,a)+num[a] );
else if( sscanf(str,"1 %d %d %d %d",&a,&b,&k,&c) )
{
update( a%k,b,k,c );
update( a%k,a-1,k,-c );
}
}
}
return 0;
}