线段树+扫描线 HDU-3642 Get The Treasury 题目链接：[ HDU - 3642 ] 题目大意：给你n个立方体的左下角坐标和右上角坐标，求立方体相交至少相交的面积。 题解 将Z轴离散化，把面积当作二维的底和高 代码如下 #include<bits/stdc++.h> using namespace std; const int MAXN=2010; struct Node { int l,r; int lf,rf;//实际的左右端点 int c; int once,twice,more; }segTree[MAXN*3]; int y[MAXN]; int z[MAXN]; struct Line { int x; int y1,y2; int z1,z2;//这两个是枚举的时候判断使用的 int f; }line[MAXN]; bool cmp(Line a,Line b) { return a.x<b.x; } void Build(int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; segTree[i].lf=y[l]; segTree[i].rf=y[r]; segTree[i].c=0; segTree[i].once=segTree[i].twice=segTree[i].more=0; if(r==l+1)return; int mid=(l+r)>>1; Build(i<<1,l,mid); Build((i<<1)|1,mid,r); } void push_up(int i) { if(segTree[i].c>2) { segTree[i].more=segTree[i].rf-segTree[i].lf; segTree[i].once=segTree[i].twice=0; } else if(segTree[i].c==2) { if(segTree[i].l+1==segTree[i].r)//叶子结点 { segTree[i].more=0; segTree[i].twice=segTree[i].rf-segTree[i].lf; segTree[i].once=0; return; } segTree[i].more=segTree[i<<1].once+segTree[i<<1].twice+segTree[i<<1].more +segTree[(i<<1)|1].once+segTree[(i<<1)|1].twice+segTree[(i<<1)|1].more; segTree[i].twice=segTree[i].rf-segTree[i].lf-segTree[i].more; segTree[i].once=0; } else if(segTree[i].c==1) { if(segTree[i].l+1==segTree[i].r) { segTree[i].more=0; segTree[i].twice=0; segTree[i].once=segTree[i].rf-segTree[i].lf; return; } segTree[i].more=segTree[i<<1].more+segTree[i<<1].twice +segTree[(i<<1)|1].more+segTree[(i<<1)|1].twice; segTree[i].twice=segTree[i<<1].once+segTree[(i<<1)|1].once; segTree[i].once=segTree[i].rf-segTree[i].lf-segTree[i].more-segTree[i].twice; } else { if(segTree[i].l+1==segTree[i].r) { segTree[i].more=segTree[i].once=segTree[i].twice=0; return; } segTree[i].more=segTree[i<<1].more+segTree[(i<<1)|1].more; segTree[i].twice=segTree[i<<1].twice+segTree[(i<<1)|1].twice; segTree[i].once=segTree[i<<1].once+segTree[(i<<1)|1].once; } } void update(int i,Line e) { if(segTree[i].lf>=e.y1 && segTree[i].rf<=e.y2) { segTree[i].c+=e.f; push_up(i); return; } if(e.y2<=segTree[i<<1].rf) update(i<<1,e); else if(e.y1>=segTree[(i<<1)|1].lf) update((i<<1)|1,e); else { Line temp=e; temp.y2=segTree[i<<1].rf; update(i<<1,temp); temp=e; temp.y1=segTree[(i<<1)|1].lf; update((i<<1)|1,temp); } push_up(i); } Line temp[MAXN]; int main(void) { int T; int n; int x1,y1,z1,x2,y2,z2; scanf("%d",&T); int iCase=0; while(T--) { iCase++; scanf("%d",&n); int t=0; for(int i=0;i<n;i++) { scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2); line[t].x=x1; line[t].y1=y1; line[t].y2=y2; line[t].z1=z1; line[t].z2=z2; line[t].f=1; y[t]=y1; z[t++]=z1; line[t].x=x2; line[t].y1=y1; line[t].y2=y2; line[t].z1=z1; line[t].z2=z2; line[t].f=-1; y[t]=y2; z[t++]=z2; } sort(line,line+t,cmp); sort(y,y+t); int t1=unique(y,y+t)-y; Build(1,0,t1-1); sort(z,z+t); int t2=unique(z,z+t)-z; long long ans=0; long long area=0; for(int i=0;i<t2-1;i++) { int m=0; for(int j=0;j<t;j++) if(line[j].z1<=z[i]&&line[j].z2>z[i]) temp[m++]=line[j]; area=0; update(1,temp[0]); for(int j=1;j<m;j++) { area+=(long long)segTree[1].more*(temp[j].x-temp[j-1].x); update(1,temp[j]); } ans+=area*(z[i+1]-z[i]); } printf("Case %d: %I64d\n",iCase,ans); } return 0; }

线段树+扫描线 HDU-1542 Picture 题目链接：[ HDU - 1828 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求外周长。 题解 扫描线 + 离散化板子 将横竖两次扫描简化 代码如下 #include<bits/stdc++.h> using namespace std; const int maxn = 10010; const int maxN = 80010; const int INF = 0x3f3f3f3f; inline int read(void) { int w = 1, d = 0; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { d = d * 10 + ch - '0'; ch = getchar(); } return w * d; } struct Node { int l, r, cnt; int lc, rc; int len, num; } tree[maxN]; struct node { int x1, x2, y, flag; void init(int l, int r, int h, int f) { x1 = l, x2 = r, y = h, flag = f; } bool operator < (const node& a) { return y < a.y; } } line[maxn]; int n, x1, y11, x2, y2; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; tree[id].lc = 0; tree[id].rc = 0; tree[id].num = 0; if (l == r) return; int mid = (l + r) >> 1; build_tree(id << 1, l, mid); build_tree(id << 1 | 1, mid + 1, r); } void getlen(int i) { if (tree[i].cnt) { tree[i].len = tree[i].r - tree[i].l + 1; tree[i].lc = tree[i].rc = 1; tree[i].num = 1; }else if (tree[i].l == tree[i].r) { tree[i].len = 0; tree[i].lc = tree[i].rc = 0; tree[i].num = 0; } else { tree[i].len = tree[i << 1].len + tree[i << 1 | 1].len; tree[i].lc = tree[i << 1].lc; tree[i].rc = tree[i << 1 | 1].rc; tree[i].num = tree[i << 1].num + tree[i << 1 | 1].num - (tree[i << 1].rc & tree[i << 1 | 1].lc); } } void update(int id, int l, int r, int v) { if (tree[id].l == l && tree[id].r == r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) update(id << 1, l, r, v); else if (l > mid) update(id << 1 | 1, l, r, v); else { update(id << 1, l, mid, v); update(id << 1 | 1, mid + 1, r, v); } getlen(id); } int main(void) { ios::sync_with_stdio(false); while (~scanf("%d", &n)) { int minn = INF, maxx = -INF; for (int i = 0; i < n; i++) { x1 = read(), y11 = read(), x2 = read(), y2 = read(); maxx = max(maxx, max(x1, x2)); minn = min(minn, min(x1, x2)); line[i].init(x1, x2, y11, 1); line[i + n].init(x1, x2, y2, -1); } sort(line, line + 2 * n); build_tree(1, minn, maxx - 1); long long ans = 0, last = 0; for (int i = 0; i < 2 * n; i++) { update(1, line[i].x1, line[i].x2 - 1, line[i].flag); ans += abs(tree[1].len - last); ans += (line[i + 1].y - line[i].y) * tree[1].num * 2; last = tree[1].len; } cout << ans << endl; } return 0; }

线段树+扫描线 HDU-1542 Atlantis 题目链接：[ HDU - 1542 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求矩形相交的面积。 题解 扫描线 + 离散化板子 代码如下 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; double dif_x[500]; struct node { double x1,x2,y; int flag; void init(double l, double r, double h, int key) { x1 = l; x2 = r; y = h; flag = key; } }line[500]; bool cmp(node a, node b) { return a.y < b.y; } struct node2 { int l, r, cnt; double len; }tree[1000]; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; if(l == r) return; int mid = (r + l) >> 1; build_tree(id << 1, l, mid); build_tree((id << 1) + 1, mid + 1, r); } void getlen(int id) { if(tree[id].cnt >= 1) tree[id].len = dif_x[tree[id].r+1] - dif_x[tree[id].l]; else tree[id].len = tree[id<<1].len + tree[(id<<1)|1].len; } void update(int id,int l,int r,int v) { if(tree[id].l==l && tree[id].r==r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if(r <= mid) update(id << 1,l,r,v); else if(l > mid) update((id << 1) + 1, l, r, v); else { update(id << 1, l, mid, v); update((id << 1) + 1, mid + 1, r, v); } getlen(id); } int mySearch(double p, int l, int r) { while(l <= r) { int mid = (l + r) >> 1; if(dif_x[mid] == p) return mid; if(dif_x[mid] < p) l = mid + 1; else r = mid - 1; } } int main(void) { int n, noc = 0; while (~scanf("%d", &n)) { if (n == 0) break; noc++; double x1, y1, x2, y2; int line_num = 0; for(int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[line_num].init(x1, x2, y1, 1); dif_x[line_num++] = x1; line[line_num].init(x1, x2, y2, -1); dif_x[line_num++] = x2; } sort(line, line + line_num, cmp); sort(dif_x, dif_x + line_num); int dif_x_num = unique(dif_x, dif_x + line_num) - dif_x; build_tree(1, 0, dif_x_num - 1); double ans = 0; for(int i = 0; i < line_num - 1; i++) { int line_l = mySearch(line[i].x1, 0, dif_x_num - 1); int line_r = mySearch(line[i].x2, 0, dif_x_num-1) - 1; update(1, line_l, line_r, line[i].flag); ans += tree[1].len * (line[i+1].y - line[i].y); } printf("Test case #%d\n", noc); printf("Total explored area: %.2lf\n\n", ans); } return 0; }

线段树+扫描线 HDU-1542 覆盖的面积 题目链接：[ HDU - 1255 ] 题目大意：给你n个矩形的左下角坐标和右上角坐标，求矩形相交至少覆盖两次以上的面积。 题解 代码如下 #include<bits/stdc++.h> using namespace std; const int maxn = 2010; double dif_x[maxn]; //记录不同的x坐标 int n, t = 0; struct node { double x1, x2, y; int flag; void init(double l, double r, double h, int key) { x1 = l, x2 = r, y = h, flag = key; } bool operator < (const node& a) const { return y < a.y; } }line[maxn]; struct Node { int l, r, cnt; double len; double len2; }tree[maxn * 4]; void build_tree(int id, int l, int r) { tree[id].l = l; tree[id].r = r; tree[id].cnt = 0; tree[id].len = 0; tree[id].len2 = 0; if (l == r) return; int mid = (r + l) >> 1; build_tree(id << 1, l, mid); build_tree(id << 1 | 1, mid + 1, r); } void getlen(int id) { if (tree[id].cnt) //如果该段被覆盖那么就直接由dif_x数组获得长度 tree[id].len = dif_x[tree[id].r + 1] - dif_x[tree[id].l]; else if (tree[id].l == tree[id].r) tree[id].len = 0; else //如果没有被覆盖，那么应该是由左右孩子的和 tree[id].len = tree[id << 1].len + tree[id << 1 | 1].len; if (tree[id].cnt >= 2) tree[id].len2 = dif_x[tree[id].r + 1] - dif_x[tree[id].l]; else if (tree[id].l == tree[id].r) tree[id].len2 = 0; else if (tree[id].cnt == 1) tree[id].len2 = tree[id << 1].len + tree[id << 1 | 1].len; else tree[id].len2 = tree[id << 1].len2 + tree[id << 1 | 1].len2; } void update(int id, int l, int r, int v) { if (tree[id].l == l && tree[id].r == r) { tree[id].cnt += v; getlen(id); return; } int mid = (tree[id].l + tree[id].r) >> 1; if (r <= mid) update(id << 1, l, r, v); else if (l > mid) update(id << 1 | 1, l, r, v); else { update(id << 1, l, mid, v); update(id << 1 | 1, mid + 1, r, v); } getlen(id); } int main(void) { ios::sync_with_stdio(false); scanf("%d", &t); while (t--) { scanf("%d", &n); int line_num = 0; //一共有多少条横线 double x1, y11, x2, y2; for (int i = 0; i < n; i++) { scanf("%lf%lf%lf%lf", &x1, &y11, &x2, &y2); line[line_num].init(x1, x2, y11, 1); dif_x[line_num++] = x1; line[line_num].init(x1, x2, y2, -1); dif_x[line_num++] = x2; } sort(line, line + line_num); sort(dif_x, dif_x + line_num); //对dif_x去重，要先排个序，这样更方便 int dif_x_num = unique(dif_x, dif_x + line_num) - dif_x; //dif_x_num表示去重后不同的x坐标的数量 build_tree(1, 0, dif_x_num - 1); double ans = 0.00; for (int i = 0; i < line_num - 1; i++) { int ll = lower_bound(dif_x, dif_x + dif_x_num, line[i].x1) - dif_x; int rr = lower_bound(dif_x, dif_x + dif_x_num, line[i].x2) - dif_x - 1; update(1, ll, rr, line[i].flag); ans += tree[1].len2 * (line[i + 1].y - line[i].y); } printf("%.2lf\n", ans + 0.000001); } return 0; }

线段树 HDU-1754 I Hate It 题目链接：[HDU - 1754] 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 Input 本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。 当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 Output 对于每一次询问操作，在一行里面输出最高成绩。 Sample Input 5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5 Sample Output 5 6 5 9 Hint Huge input,the C function scanf() will work better than cin 题解 #include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; struct node{ int l,r,max; }t[810000]; int A[210000],max; int MAX(int a, int b) { return a>b ? a:b; } void build(int l,int r,int k) { t[k].l=l; t[k].r=r; if(l==r) t[k].max=A[r]; else{ build(l,(l+r)/2,k<<1); build((l+r)/2+1,r,k<<1|1); t[k].max=MAX(t[k<<1].max, t[k<<1|1].max); } } int query(int l,int r,int k) { if(t[k].l>=l && t[k].r<=r) return t[k].max; else{ int ans=0; int m=(t[k].l+t[k].r)/2; if(l<=m) ans=query(l,r,k<<1); if(r>m) ans=MAX(ans,query(l,r,k<<1|1)); return ans; } } void change(int a,int b,int k) { if(t[k].l==a && t[k].r==a){ t[k].max=b; return; } if(a>(t[k].l+t[k].r)/2) change(a,b,2*k+1); else change(a,b,2*k); t[k].max=MAX(t[k*2].max, t[k*2+1].max); } int main(void) { int l,r,k,n,m; char command; while(scanf("%d%d",&n,&m)!=EOF){ memset(t,0,sizeof(t)); memset(A,0,sizeof(A)); for(int i=1;i<=n;i++) scanf("%d",&A[i]); build(1,n,1); getchar(); while(m-->0){ int a, b; scanf("%c%d%d",&command,&a,&b); getchar(); if(command=='Q') cout << query(a,b,1) << endl; else if(command=='U') change(a,b,1); } } return 0; } ​```cpp

线段树 HDU-1166 敌兵布阵 题目链接：[HDU - 1166] C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。 中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的. Input 第一行一个整数T，表示有T组数据。 每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。 接下来每行有一条命令，命令有4种形式： (1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30） (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）; (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数; (4)End 表示结束，这条命令在每组数据最后出现; 每组数据最多有40000条命令 Output 对第i组数据,首先输出“Case i:”和回车, 对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。 Sample Input 1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End Sample Output Case 1: 6 33 59 题解 #include<iostream> #include<cstring> #include<string> using namespace std; struct Node{ int l, r, sum; }t[210000]; int a[210000]; void build(int l, int r, int k) { t[k].l=l; t[k].r=r; if(l==r){ t[k].sum=a[r]; }else{ build(l, (l+r)/2, k*2); build((l+r)/2+1, r, k*2+1); t[k].sum=t[k*2].sum+t[k*2+1].sum; } } int query(int l, int r, int k) { if(t[k].l>=l && t[k].r<=r) return t[k].sum; else{ int m=(t[k].l+t[k].r)/2; int ans=0; if(l<=m) ans+=query(l, r, 2*k); if(r>m) ans+=query(l, r, 2*k+1); return ans; } } void add(int a,int b,int k) { t[k].sum+=b; if(t[k].l==a && t[k].r==a) return; if(a>(t[k].l+t[k].r)/2) add(a, b, 2*k+1); else add(a, b, 2*k); } void sub(int a,int b,int k) { t[k].sum-=b; if(t[k].l==a && t[k].r==a) return; if(a>(t[k].l+t[k].r)/2) sub(a, b, 2*k+1); else sub(a, b, 2*k); } int main(void) { int n,T; char command[6]; scanf("%d", &T); for (int i=1; i<=T; i++) { scanf("%d", &n); for (int j=1; j<=n; j++) scanf("%d", &a[j]); build(1, n, 1); cout << "Case " << i << ":" << endl; int a,b; while (scanf("%s", command)) { if (strcmp(command,"End")==0) break; scanf("%d%d", &a, &b); if(strcmp(command,"Query")==0) cout << query(a, b, 1) << endl; else if(strcmp(command,"Add")==0) add(a, b, 1); else if(strcmp(command,"Sub")==0) sub(a, b, 1); } } return 0; }