企业网站 设,代理平台注册网站建设,wordpress md5工具,前端网页设计流程problem
luogu-P3755
solution
这题第一眼矩阵内的点权值和#xff0c;马上就是 K-D tree\text{K-D tree}K-D tree 不过脑子的敲。
这其实就是个二维数点问题#xff0c;完全可以树状数组。
将矩阵差分成四个以原点为左下角的矩阵。
然后将基站按 xxx 轴排序#xff0…problem
luogu-P3755
solution
这题第一眼矩阵内的点权值和马上就是 K-D tree\text{K-D tree}K-D tree 不过脑子的敲。
这其实就是个二维数点问题完全可以树状数组。
将矩阵差分成四个以原点为左下角的矩阵。
然后将基站按 xxx 轴排序矩阵按右上角的 (x,y)(x,y)(x,y) 的 xxx 排序。
树状数组维护 yyy 轴信息即可。
code-树状数组
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 1000005
int n, m, cnt, tot;
struct point { int x, y, w; }p[maxn];
struct node { int x, y, k, id; }g[maxn];
int val[maxn], ret[maxn];void read( int x ) {x 0; int f 1; char s getchar();while( s 0 or s 9 ) {if( s - ) f -1;s getchar();}while( 0 s and s 9 ) {x ( x 1 ) ( x 3 ) ( s ^ 48 );s getchar();}x * f;
}void print( int x ) {if( x 0 ) putchar(-), x -x;if( x 9 ) print( x / 10 );putchar( x % 10 0 );
}namespace BIT {int t[maxn];void add( int x, int y ) {for( ;x cnt;x x -x ) t[x] y;} int ask( int x ) {int ans 0;for( ;x;x - x -x ) ans t[x];return ans;}
}signed main() {read( n ), read( m );for( int i 1;i n;i ) {read( p[i].x ), read( p[i].y ), read( p[i].w );val[ cnt] p[i].y;}for( int i 1, xi, yi, xj, yj, w;i m;i ) {read( xi ), read( yi ), read( xj ), read( yj );g[ tot] (node){ xj, yj, 1, i };g[ tot] (node){ xi - 1, yj, -1, i };g[ tot] (node){ xj, yi - 1, -1, i };g[ tot] (node){ xi - 1, yi - 1, 1, i };val[ cnt] yj;val[ cnt] yi - 1;}sort( val 1, val cnt 1 );cnt unique( val 1, val cnt 1 ) - val - 1;for( int i 1;i n;i ) p[i].y lower_bound( val 1, val cnt 1, p[i].y ) - val;for( int i 1;i tot;i )g[i].y lower_bound( val 1, val cnt 1, g[i].y ) - val;sort( p 1, p n 1, []( point a, point b ) { return a.x b.x; } );sort( g 1, g tot 1, []( node a, node b ) { return a.x b.x; } );for( int i 1, j 1;i tot;i ) {for( ;j n and p[j].x g[i].x;j ) BIT :: add( p[j].y, p[j].w );ret[g[i].id] BIT :: ask( g[i].y ) * g[i].k;}for( int i 1;i m;i ) print( ret[i] ), putchar(\n);return 0;
}code-KDtree
#include bits/stdc.h
using namespace std;
#define maxn 100005
#define int long long
struct point { int x, y, p; }g[maxn];
struct node { point Max, Min, id; int lson, rson, sum; }t[maxn];
int n, m, dim, X1, Y1, X2, Y2, ans;void read( int x ) {x 0; int f 1; char s getchar();while( s 0 or s 9 ) {if( s - ) f -1;s getchar();}while( 0 s and s 9 ) {x ( x 1 ) ( x 3 ) ( s ^ 48 );s getchar();}x * f;
}void print( int x ) {if( x 0 ) putchar( - ), x -x;if( x 9 ) print( x / 10 );putchar( x % 10 0 );
}bool cmp( point a, point b ) {if( dim 0 ) return a.x b.x;if( dim 1 ) return a.y b.y;
}void chkmin( point a, point b ) {a.x min( a.x, b.x );a.y min( a.y, b.y );
}void chkmax( point a, point b ) {a.x max( a.x, b.x );a.y max( a.y, b.y );
}void pushup( int now ) {t[now].sum t[now].id.p;if( t[now].lson ) {chkmin( t[now].Min, t[t[now].lson].Min );chkmax( t[now].Max, t[t[now].lson].Max );t[now].sum t[t[now].lson].sum;}if( t[now].rson ) {chkmin( t[now].Min, t[t[now].rson].Min );chkmax( t[now].Max, t[t[now].rson].Max );t[now].sum t[t[now].rson].sum;}
}int build( int l, int r, int d ) {if( l r ) return 0;dim d; int mid l r 1;nth_element( g l, g mid, g r 1, cmp );t[mid].Max t[mid].Min t[mid].id g[mid];t[mid].lson build( l, mid - 1, d ^ 1 );t[mid].rson build( mid 1, r, d ^ 1 );pushup( mid );return mid;
}void query( int now ) {if( ! now ) return;if( t[now].Max.x X1 or t[now].Min.x X2 or t[now].Max.y Y1 or t[now].Min.y Y2 ) return;if( X1 t[now].Min.x and t[now].Max.x X2 andY1 t[now].Min.y and t[now].Max.y Y2 ) {ans t[now].sum; return;}if( X1 t[now].id.x and t[now].id.x X2 andY1 t[now].id.y and t[now].id.y Y2 ) ans t[now].id.p;query( t[now].lson );query( t[now].rson );
}signed main() {read( n ), read( m );for( int i 1;i n;i ) read( g[i].x ), read( g[i].y ), read( g[i].p );int root build( 1, n, 0 );for( int i 1;i m;i ) {read( X1 ), read( Y1 ), read( X2 ), read( Y2 );ans 0, query( root );print( ans );putchar( \n );}return 0;
}
