Segment Tree 2
-
K-th Number
- 不用离散化,给定区间大小就可以建树。离散化本身也是O(n)的!
- 手动归并排序(pushup)。
- [4], upper_bound(4) -> 1, lower_bound(4) -> 0.
- Binary Search !!!
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #define lc 2*rt+1 #define rc 2*rt+2 using namespace std; const int maxn = 100005; int N, M, a, b, c; int arr[maxn]; struct node { int l, r; vector<int> v; } t[maxn << 2]; void merge(vector<int>&a, vector<int>&b, vector<int>&c) { int la = a.size(); int lb = b.size(); int i = 0, j = 0; while (i < la && j < lb) { if (a[i] <= b[j]) c.push_back(a[i++]); else c.push_back(b[j++]); } while (i < la) c.push_back(a[i++]); while (j < lb) c.push_back(b[j++]); } void build(int rt, int l, int r) { t[rt].l = l; t[rt].r = r; if (l == r) { t[rt].v.push_back(arr[l]); return; } build(lc, l, (l + r) / 2); build(rc, (l + r) / 2 + 1, r); merge(t[lc].v, t[rc].v, t[rt].v); } int lt(int rt, int l, int r, int v) { if (t[rt].l == l && t[rt].r == r) { int num = upper_bound(t[rt].v.begin(), t[rt].v.end(), v) - t[rt].v.begin(); return num; } int mid = (t[rt].l + t[rt].r) / 2; if (r <= mid) return lt(lc, l, r, v); else if (l > mid) return lt(rc, l, r, v); else return lt(lc, l, mid, v) + lt(rc, mid + 1, r, v); } int query(int l, int r, int K) { //binary search int L = -1e9 - 1, R = 1e9 + 1; // max+1, min-1 while (L + 1 < R) { int M = (L + R) / 2; int n = lt(0, l, r, M); if (n < K) L = M; else R = M; } return R; } int main() { scanf("%d%d", &N, &M); for (int i = 0; i < N; i++) scanf("%d", arr + i); build(0, 0, N - 1); for (int i = 0; i < M; i++) { scanf("%d%d%d", &a, &b, &c); int res = query(a - 1, b - 1, c); cout << res << endl; } }
-
Atlantis
- 暴力离散标记法
#include <cstdio> #include <cstring> #include <algorithm> #define maxn 510 using namespace std; int n; double x2,y2,x1,y1; bool flag[maxn][maxn]; double X[maxn],Y[maxn]; struct node { double x1,y1,x2,y2; } p[maxn]; int bsearch(double *a,int l,int r,double target) { int low=l,high=r; while(low<=high) { int mid=(low+high)>>1; if(a[mid]==target) { return mid; } if(a[mid]>target) high=mid-1; else low=mid+1; } } int main() { int case1=0; while(scanf("%d",&n)!=EOF) { memset(flag,false,sizeof(flag)); memset(X,0,sizeof(X)); memset(Y,0,sizeof(Y)); case1++; if(n==0) break; int t1=0,t2=0; for(int i=0; i<n; i++) { scanf("%lf%lf%lf%lf",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2); X[t1++]=p[i].x1;X[t1++]=p[i].x2; Y[t2++]=p[i].y1;Y[t2++]=p[i].y2; } sort(X,X+2*n); sort(Y,Y+2*n); for(int i=0; i<n; i++) { int xpos=bsearch(X,0,t1-1,p[i].x1); int ypos=bsearch(Y,0,t2-1,p[i].y1); int xpos1=bsearch(X,0,t1-1,p[i].x2); int ypos1=bsearch(Y,0,t2-1,p[i].y2); for(int i=xpos; i<xpos1; i++) { for(int j=ypos; j<ypos1; j++) { flag[i][j]=true; } } } double sum=0; for(int i=0; i<t1; i++) { for(int j=0; j<t2; j++) { if(flag[i][j]) sum+=((X[i+1]-X[i])*(Y[j+1]-Y[j])); } } printf("Test case #%d\n",case1); printf("Total explored area: %.2lf\n",sum); printf("\n"); } return 0; }
-
线段树扫描线
十分烦人的做法。。。
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <stack> #include <vector> #include <queue> #include <set> #include <map> #define ll long long #define lc 2*rt+1 #define rc 2*rt+2 using namespace std; const int maxn = 105; int N; double ans; double X1, Y1, X2, Y2; struct node { int l, r; double len; int cover; } T[maxn << 3]; struct line { double x, y1, y2; int flag; // is_left bool operator< (const line& b) const { return x < b.x; } } L[maxn << 1]; int ycnt = 0; double ys[maxn << 1]; void build(int rt, int l, int r) { T[rt].l = l; T[rt].r = r; if (l + 1 == r) return; build(lc, l, (l + r) / 2); build(rc, (l + r) / 2, r); } int cnt = 0; void add_line() { L[cnt].x = X1; L[cnt].y1 = Y1; L[cnt].y2 = Y2; L[cnt++].flag = 1; L[cnt].x = X2; L[cnt].y1 = Y1; L[cnt].y2 = Y2; L[cnt++].flag = -1; } void getlen(int rt) { if (T[rt].cover) T[rt].len = ys[T[rt].r] - ys[T[rt].l]; else if (T[rt].l + 1 == T[rt].r) T[rt].len = 0; // required! else T[rt].len = T[lc].len + T[rc].len; } void update(int rt, line& ln) { if (ys[T[rt].l] >= ln.y1 && ys[T[rt].r] <= ln.y2) { // node's region is covered by line T[rt].cover += ln.flag; // left right getlen(rt); return; } if (T[rt].l + 1 == T[rt].r) return; int mid = (T[rt].r + T[rt].l) / 2; if (ln.y1 <= ys[mid]) update(lc, ln); if (ln.y2 > ys[mid]) update(rc, ln); getlen(rt); } int main() { int cas = 0; while (cin >> N) { if (cas) puts(""); if (N == 0) break; cnt = 0, ycnt = 0; for (int i = 0; i < N; i++) { scanf("%lf%lf%lf%lf", &X1, &Y1, &X2, &Y2); add_line(); ys[ycnt++] = Y1; ys[ycnt++] = Y2; } sort(L, L + cnt); sort(ys, ys + ycnt); ycnt = unique(ys, ys + ycnt) - ys; build(0, 0, cnt - 1); // tree for x ans = 0; update(0, L[0]); for (int i = 1; i < 2 * N; i++) { double tmp = (L[i].x - L[i - 1].x) * T[0].len; //cout << "add "<<L[i].x - L[i-1].x<<"*"<<T[0].len<<"=" << tmp << endl;; ans += tmp; update(0, L[i]); } printf("Test case #%d\n", ++cas); printf("Total explored area: %.2f\n", ans); } }
-
Picture
边排序,相同x时入边在前。
保证边重合的情况,两边不都算。
#include <iostream> #include <algorithm> #include <cstring> #include <vector> #define lc 2*rt+1 #define rc 2*rt+2 using namespace std; const int maxn = 10005; int N; int ans; int X1, Y1, X2, Y2; struct LINE { int x, y1, y2, flag; LINE(int x, int y1, int y2, int f) :x(x), y1(y1), y2(y2), flag(f) {} bool operator< (const LINE& b) const { // this line wasted me 4 hours. if (x == b.x) return flag>b.flag; return x < b.x; } }; vector<LINE> xline; vector<int> ys; void addline() { xline.push_back(LINE(X1, Y1, Y2, 1)); xline.push_back(LINE(X2, Y1, Y2, -1)); ys.push_back(Y1); ys.push_back(Y2); } struct node { int l, r; int cover; int count; int len; bool ll, rr; } t[maxn * 10]; void build(int rt, int l, int r) { t[rt].l = l; t[rt].r = r; t[rt].count = 0; t[rt].cover = 0; t[rt].len = 0; t[rt].ll = false; t[rt].rr = false; if (l + 1 == r) return; build(lc, l, (l + r) / 2); build(rc, (l + r) / 2, r); } void getlen(int rt) { if (t[rt].cover > 0) { t[rt].len = ys[t[rt].r] - ys[t[rt].l]; t[rt].count = 1; t[rt].ll = t[rt].rr = true; } else if (t[rt].l + 1 == t[rt].r) { // leaves, and not covered. t[rt].len = 0; t[rt].count = 0; t[rt].ll = t[rt].rr = false; } else { t[rt].len = t[lc].len + t[rc].len; t[rt].count = t[lc].count + t[rc].count + ((t[lc].rr && t[rc].ll) ? -1 : 0); t[rt].ll = t[lc].ll; t[rt].rr = t[rc].rr; } } void update(int rt, LINE& ln) { if (ys[t[rt].l] >= ln.y1 && ys[t[rt].r] <= ln.y2) { t[rt].cover += ln.flag; getlen(rt); return; } int mid = (t[rt].l + t[rt].r) / 2; if (ln.y2 > ys[mid]) update(rc, ln); if (ln.y1 < ys[mid]) update(lc, ln); getlen(rt); } int main() { while (cin >> N) { if (N == 0) { cout << 0 << endl; continue; } xline.clear(); ys.clear(); for (int i = 0; i < N; i++) { cin >> X1 >> Y1 >> X2 >> Y2; addline(); } sort(xline.begin(), xline.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); build(0, 0, ys.size() - 1); int len = xline.size(); ans = 0; int last = 0; int segs = 0; for (int i = 0; i < len; i++) { update(0, xline[i]); if (i) { ans += (xline[i].x - xline[i - 1].x) * 2 * segs; } ans += abs(t[0].len - last); last = t[0].len; segs = t[0].count; } cout << ans << endl; } }
二维线段树
-
Matrix
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include<cstdio> #include<string.h> #define maxn 1010 #define m ((l+r)>>1) #define ls (now<<1) #define rs (ls|1) using namespace std; int N; int tree[maxn << 2][maxn << 2]; char op[10]; int xl, yl, xr, yr, x, y; int ans; void UpDateY(int xnow, int l, int r, int now){ cout << "UpdateY: " <<xnow <<" "<< l << "-" << r << " " << now << endl; if (yl <= l && r <= yr) { cout << "change " << xnow << "," << now << endl; tree[xnow][now] ^= 1; return; } if (yl <= m) UpDateY(xnow, l, m, ls); if (yr > m) UpDateY(xnow, m + 1, r, rs); } void UpDateX(int l, int r, int now){ cout << "UpdateX: " << l << "-" << r << " " << now << endl; if (xl <= l && r <= xr) { UpDateY(now, 1, N, 1); return; } if (xl <= m) UpDateX(l, m, ls); if (xr > m) UpDateX(m + 1, r, rs); } void QueryY(int xnow, int l, int r, int now) { ans ^= tree[xnow][now]; if (l == r) return; if (y <= m) QueryY(xnow, l, m, ls); if (y > m) QueryY(xnow, m + 1, r, rs); } void QueryX(int l, int r, int now) { QueryY(now, 1, N, 1); if (l == r) return; if (x <= m) QueryX(l, m, ls); if (x > m) QueryX(m + 1, r, rs); } int main() { int cas; scanf("%d", &cas); while (cas--) { memset(tree, 0, sizeof(tree)); int T; scanf("%d %d", &N, &T); while (T--) { scanf("%s", op); if (op[0] == 'C') { scanf("%d %d %d %d", &xl, &yl, &xr, &yr); UpDateX(1, N, 1); } else { scanf("%d %d", &x, &y); ans = 0; QueryX(1, N, 1); printf("%d\n", ans); } } if (cas) puts(""); } return 0; }