problem

luogu-P3755

solution

這題第一眼矩陣內的點權值和，馬上就是 $\text{K-D?tree}$ 不過腦子的敲。

這其實就是個二維數點問題，完全可以樹狀數組。

將矩陣差分成四個以原點為左下角的矩陣。

然后將基站按 $x$ 軸排序，矩陣按右上角的 $(x,y)$ 的 $x$ 排序。

樹狀數組維護 $y$ 軸信息即可。

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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[CQOI2017] 老C的任务（差分 + 树状数组 / K-D tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。