在久别线段树之后,我终于又A了一道线段树。
题意为:
一个母龙不停地生小孩。问对于每个龙来说,他存在过的最小子孙和他的代数差值是多少。
这题就是区间修改,区间求最值。调了几调,还在课上写了一写。终于过了。push_up 和 push_dn写错了。
其他全是图方便的写法, 比如unique 和 lowerbound。
#define maxn 141001 #define lson l, m , rt << 1 #define rson m + 1, r, rt << 1 |1 #define ls rt << 1 #define rs rt << 1 | 1 int X[maxn],n, mmax[maxn << 2], T, num[maxn], all,xsub, cover[maxn << 2]; struct Node{ int s; int e; }p[maxn]; #include <cstdio> #include <vector> #include <cmath> #include <algorithm> using namespace std; vector <int> vec[maxn]; void build(int l, int r, int rt){ mmax[rt] = 0; cover[rt] = -1; if(l == r) return ; int m = (l + r) >> 1; build(lson); build(rson); } void push_up(int rt){ mmax[rt] = max(mmax[ls],mmax[rs]); if(cover[ls] == cover[rs]){ cover[rt] = cover[ls]; }else{ cover[rt] = -1; } } void push_dn(int rt){ if(cover[rt] != -1){ mmax[ls] = mmax[rs] = mmax[rt]; cover[ls] = cover[rs] = cover[rt]; cover[rt] = -1; } } void update(int L, int R, int val, int l ,int r, int rt){ if(L <= l && r <= R && cover[rt] >= 0){ cover[rt] = max(val, cover[rt]); mmax[rt] = cover[rt]; return ; } if(l == r) { mmax[rt] = cover[rt] = val; return ; } int m = (l + r) >> 1; push_dn(rt); if(L <= m) update(L,R,val,lson); if(R > m) update(L, R, val, rson); push_up(rt); } int query(int L, int R, int l ,int r, int rt){ if(L <= l && r <= R){ return mmax[rt]; }int m = (l + r) >> 1; push_dn(rt); int ans = 0; if(L <= m) ans = query(L,R,lson); if(R > m) ans = max(ans, query(L,R,rson)); return ans; } void solve(int pa, int level){ for(int i = 0; i < vec[pa].size(); i ++){ solve(vec[pa][i], level + 1); } int aa = lower_bound(X, X + xsub,p[pa].s) - X; int bb = lower_bound(X, X + xsub,p[pa].e) - X; update(aa, bb, level, 0, all, 1); num[pa] = query(aa, bb, 0, all, 1) - level; } #include <cstring> int main(){ scanf("%d",&T); while(T --){ scanf("%d",&n); int a, b,pp; xsub = 0; for(int i = 0; i < n; i++) vec[i].clear(); for(int i = 0; i < n; i++) { scanf("%d%d%d",&pp, & a, & b); if(pp != -1) vec[pp].push_back(i); p[i].s = a, p[i].e = b; X[xsub ++] = a, X[xsub ++] = b; } sort(X, X + xsub); all = xsub; build(0, all, 1); solve(0, 0); for(int i = 0; i < n - 1; i ++){ printf("%d ", num[i]); }printf("%d\n",num[n - 1]); } return 0; }