【COGS】577 蝗灾 cdq分治

本文主要是介绍【COGS】577 蝗灾 cdq分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【COGS】577 蝗灾

题目分析：cdq分治入门题= =。。。。用差分思想将矩阵分成四块来计算。。排序一维，另一维用树状数组解决。

代码如下：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define mid ( ( l + r ) >> 1 )const int MAXN = 200005 ;
const int MAXM = 500005 ;struct Node {int x1 , y1 , x2 , y2 ;int v ;int op ;
} L[MAXN] , S[MAXN << 1] ;int n , m ;
int ans[MAXN] ;
int T[MAXM] ;void scanf ( int& x , char c = 0 ) {while ( ( c = getchar () ) < '0' || c > '9' ) ;x = c - '0' ;while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}void modify ( int x , int v ) {while ( x <= m ) {T[x] += v ;x += x & -x ;}
}int sum ( int x , int ans = 0 ) {while ( x ) {ans += T[x] ;x -= x & -x ;}return ans ;
}int cmp ( const Node& a , const Node& b ) {return a.x1 != b.x1 ? a.x1 < b.x1 : a.op < b.op ;
}void cdq_solve ( int l , int r ) {if ( l == r ) return ;int m = mid , top = 0 ;cdq_solve ( l , m ) ;cdq_solve ( m + 1 , r ) ;FOR ( i , l , m ) if ( L[i].op == 1 ) S[top ++] = L[i] ;FOR ( i , m + 1 , r ) if ( L[i].op == 2 ) {S[top ++] = L[i] ;S[top - 1].x1 -- ;S[top ++] = L[i] ;S[top - 1].op = 3 ;S[top - 1].x1 = S[top - 1].x2 ;}sort ( S , S + top , cmp ) ;REP ( i , 0 , top ) {if ( S[i].op == 1 ) modify ( S[i].y1 , S[i].v ) ;else if ( S[i].op == 2 ) ans[S[i].v] -= sum ( S[i].y2 ) - sum ( S[i].y1 - 1 ) ;else ans[S[i].v] += sum ( S[i].y2 ) - sum ( S[i].y1 - 1 ) ;}REP ( i , l , m ) if ( L[i].op == 1 ) modify ( L[i].y1 , -L[i].v ) ;
}void solve () {int ans_cnt = 0 ;CLR ( T , 0 ) ;CLR ( ans , 0 ) ;scanf ( m ) ;scanf ( n ) ;FOR ( i , 1 , n ) {scanf ( L[i].op ) ;if ( L[i].op == 1 ) scanf ( L[i].x1 ) , scanf ( L[i].y1 ) , scanf ( L[i].v ) ;else {scanf ( L[i].x1 ) , scanf ( L[i].y1 ) , scanf ( L[i].x2 ) , scanf ( L[i].y2 ) ;L[i].v = ans_cnt ++ ;}}cdq_solve ( 1 , n ) ;REP ( i , 0 , ans_cnt ) printf ( "%d\n" , ans[i] ) ;
}int main () {freopen ( "locust.in" , "r" , stdin ) ;freopen ( "locust.out" , "w" , stdout ) ;solve () ;return 0 ;
}

这篇关于【COGS】577 蝗灾 cdq分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---