acm数据结构题解(2)

int main() {

int n,x,y,color;

while( ~scanf(\ { init();

Build(1,0,8000); while( n-- ) {

scanf(\ Updata(1,x,y,color); }

Compute(1,0,8000); memset(len,0,sizeof(len)); for(int i=0; i

if( col[i+1] != col[i] && col[i] != -1 ) len[col[i]]++; for(int j=0; j

printf(\ printf(\ }

return 0; } ZOJ1610

求N个矩形覆盖的面积

#include #include #include #include using namespace std;

#define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1

const int maxn = 2222;

int cnt[maxn << 2]; //对于rt，若cnt[rt]>0，则对应子树的线段区间被完全覆盖；若cnt[rt]==0，则被部分覆盖/完全没有覆盖 double sum[maxn << 2]; //对于rt,sum[rt]为对应子树覆盖的到线段区间的长度

double X[maxn]; //所有矩形的左右边界“直线”（每个矩形有两条这种直线，分别占用本数组的两个元素）

//（矩形）上/下边界“线段” struct Seg {

double h , l , r; //h高度, l左端点, r右端点 int s; //s==1为下边界线段； s==-1为上边界线段

Seg(){}

Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}

//需要按照上/下边界线段的高度来排序

bool operator < (const Seg &cmp) const {//看运算符重载??? return h < cmp.h; } }ss[maxn];

void PushUp(int rt,int l,int r) {

if (cnt[rt]) sum[rt] = X[r+1] - X[l]; //子树rt的线段区间完全覆盖

else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //子树rt的线段区间没有完全覆盖（没有覆盖/部分覆盖） }

//需要插入/移出线段树的“上/下边界线段”： 左端点X[L], 右端点X[R+1], c==1下边界/c==-1上边界 //待插入/移除的线段树子树范围

void update(int L,int R,int c,int l,int r,int rt) { if (L <= l && r <= R) { cnt[rt] += c; PushUp(rt , l , r); return ;

}

int m = (l + r) >> 1;

if (L <= m) update(L , R , c , lson); if (m < R) update(L , R , c , rson);

PushUp(rt , l , r); }

int Bin(double key,int n,double X[]) { int l = 0 , r = n - 1; while (l <= r) {

int m = (l + r) >> 1;

//1. 第1个分支是“递归终止条件” if (X[m] == key) return m;

//2. 第2、3个分支是“二分后的两个子问题” if (X[m] < key) l = m + 1; else r = m - 1; }

return -1; }

int main() { int n , cas = 1;

while (~scanf(\

int m = 0; while (n --) {

double a , b , c , d;

scanf(\ X[m] = a;

ss[m++] = Seg(a , c , b , 1); X[m] = c;

ss[m++] = Seg(a , c , d , -1); }

sort(X , X + m); sort(ss , ss + m);

//X[]已经递增排序后，如下操作使得X[]中不等的数字依次放在靠前

//例如X[]={1,2,2,5,5,7} --> X[]={1,2,5,7,5,7} //处理后，其中X[0, ... ,k-1]为不等的数字 int k = 1;

for (int i = 1 ; i < m ; i ++) { if (X[i] != X[i-1]) X[k++] = X[i]; }

memset(cnt , 0 , sizeof(cnt)); memset(sum , 0 , sizeof(sum));

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库acm数据结构题解(2)在线全文阅读。