#ifdef LOCAL //#define _GLIBCXX_DEBUG #else #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") #endif #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair P; typedef pair Pi; typedef vector Vec; typedef vector Vi; typedef vector Vs; typedef vector Vc; typedef vector

VP; typedef vector VVP; typedef vector VV; typedef vector VVi; typedef vector VVc; typedef vector VVV; typedef vector VVVV; #define MAKEVV(variable, a, ...) VV variable(a, Vec(__VA_ARGS__)) #define MAKEVVc(variable, a, ...) VVc variable(a,Vc(__VA_ARGS__)) #define MAKEVVV(variable, a, b, ...) VVV variable(a, VV(b, Vec(__VA_ARGS__))) #define MAKEVVVV(variable, a, b, c, ...) VVVV variable(a, VVV(b, (VV(c, Vec(__VA_ARGS__))))) #define endl '\n' #define REP(i, a, b) for(ll i=(a); i<(b); i++) #define PER(i, a, b) for(ll i=(a); i>=(b); i--) #define rep(i, n) REP(i, 0, n) #define per(i, n) PER(i, n, 0) const ll INF = 4'000'000'000'000'000'010LL; const ll MOD=998244353; #define Yes(n) cout << ((n) ? "Yes" : "No") << endl; #define YES(n) cout << ((n) ? "YES" : "NO") << endl; #define ALL(v) v.begin(), v.end() #define rALL(v) v.rbegin(), v.rend() #define pb(x) push_back(x) #define mp(a, b) make_pair(a,b) #define Each(a,b) for(auto &a :b) #define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i) #define SUM(a) accumulate(ALL(a),0LL) #ifdef LOCAL #define dbg(x_) cerr << #x_ << ":" << x_ << endl; #define dbgmap(mp) cerr << #mp << ":"<first <<":"<second << endl;} #define dbgset(st) cerr << #st << ":"<bool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (bauto lb(T &X, ll x){return lower_bound(ALL(X),x) - X.begin();} templateauto ub(T &X, ll x){return upper_bound(ALL(X),x) - X.begin();} ll popcnt(ll x){return __builtin_popcount(x);} ll topbit(ll t){return t==0?-1:63-__builtin_clzll(t);} ll floor(ll y,ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return (y-x+1)/x;}return y/x;}; ll ceil(ll y, ll x){assert(x != 0);if(x < 0){y *= -1; x *= -1;}if(y < 0){return y/x;}return (y+x-1)/x;}; template ostream &operator<<(ostream &s, const pair &p) { return s<<"("< istream &operator>>(istream &i, pair &p) { return i>>p.first>>p.second; } templateistream& operator>>(istream&i,vector&v) {rep(j,v.size())i>>v[j];return i;} // vector template ostream &operator<<(ostream &s, const vector &v) { int len=v.size(); for(int i=0; i ostream &operator<<(ostream &s, const vector > &vv) { s< struct Zip { bool initialized; vector v; Zip() : initialized(false) {} void add(T x) { v.push_back(x); } void init() { sort(ALL(v)); Uniq(v); initialized = true; } ll id(T x) { if(!initialized) init(); return lb(v, x); } T operator[](ll i) { if(!initialized) init(); return v[i]; } ll size() { if(!initialized) init(); return v.size(); } }; struct AngelBeats { using i64 = long long; static constexpr i64 INF = numeric_limits::max() / 2.1; struct alignas(32) Node { i64 sum = 0, g1 = 0, l1 = 0; i64 g2 = -INF, gc = 1, l2 = INF, lc = 1, add = 0; }; vector v; i64 n, log; AngelBeats() {} AngelBeats(int _n) : AngelBeats(vector(_n)) {} AngelBeats(const vector& vc) { n = 1, log = 0; while (n < (int)vc.size()) n <<= 1, log++; v.resize(2 * n); for (i64 i = 0; i < (int)vc.size(); ++i) { v[i + n].sum = v[i + n].g1 = v[i + n].l1 = vc[i]; } for (i64 i = n - 1; i; --i) update(i); } void range_chmin(int l, int r, i64 x) { inner_apply<1>(l, r, x); } void range_chmax(int l, int r, i64 x) { inner_apply<2>(l, r, x); } void range_add(int l, int r, i64 x) { inner_apply<3>(l, r, x); } void range_update(int l, int r, i64 x) { inner_apply<4>(l, r, x); } i64 range_min(int l, int r) { return inner_fold<1>(l, r); } i64 range_max(int l, int r) { return inner_fold<2>(l, r); } i64 range_sum(int l, int r) { return inner_fold<3>(l, r); } void debug(ll n) { #ifdef LOCAL Vec res(n); rep(i, n)res[i] = range_sum(i, i+1); dbg(res); #endif } private: void update(int k) { Node& p = v[k]; Node& l = v[k * 2 + 0]; Node& r = v[k * 2 + 1]; p.sum = l.sum + r.sum; if (l.g1 == r.g1) { p.g1 = l.g1; p.g2 = max(l.g2, r.g2); p.gc = l.gc + r.gc; } else { bool f = l.g1 > r.g1; p.g1 = f ? l.g1 : r.g1; p.gc = f ? l.gc : r.gc; p.g2 = max(f ? r.g1 : l.g1, f ? l.g2 : r.g2); } if (l.l1 == r.l1) { p.l1 = l.l1; p.l2 = min(l.l2, r.l2); p.lc = l.lc + r.lc; } else { bool f = l.l1 < r.l1; p.l1 = f ? l.l1 : r.l1; p.lc = f ? l.lc : r.lc; p.l2 = min(f ? r.l1 : l.l1, f ? l.l2 : r.l2); } } void push_add(int k, i64 x) { Node& p = v[k]; p.sum += x << (log + __builtin_clz(k) - 31); p.g1 += x; p.l1 += x; if (p.g2 != -INF) p.g2 += x; if (p.l2 != INF) p.l2 += x; p.add += x; } void push_min(int k, i64 x) { Node& p = v[k]; p.sum += (x - p.g1) * p.gc; if (p.l1 == p.g1) p.l1 = x; if (p.l2 == p.g1) p.l2 = x; p.g1 = x; } void push_max(int k, i64 x) { Node& p = v[k]; p.sum += (x - p.l1) * p.lc; if (p.g1 == p.l1) p.g1 = x; if (p.g2 == p.l1) p.g2 = x; p.l1 = x; } void push(int k) { Node& p = v[k]; if (p.add != 0) { push_add(k * 2 + 0, p.add); push_add(k * 2 + 1, p.add); p.add = 0; } if (p.g1 < v[k * 2 + 0].g1) push_min(k * 2 + 0, p.g1); if (p.l1 > v[k * 2 + 0].l1) push_max(k * 2 + 0, p.l1); if (p.g1 < v[k * 2 + 1].g1) push_min(k * 2 + 1, p.g1); if (p.l1 > v[k * 2 + 1].l1) push_max(k * 2 + 1, p.l1); } void subtree_chmin(int k, i64 x) { if (v[k].g1 <= x) return; if (v[k].g2 < x) { push_min(k, x); return; } push(k); subtree_chmin(k * 2 + 0, x); subtree_chmin(k * 2 + 1, x); update(k); } void subtree_chmax(int k, i64 x) { if (x <= v[k].l1) return; if (x < v[k].l2) { push_max(k, x); return; } push(k); subtree_chmax(k * 2 + 0, x); subtree_chmax(k * 2 + 1, x); update(k); } template inline void _apply(int k, i64 x) { if constexpr (cmd == 1) subtree_chmin(k, x); if constexpr (cmd == 2) subtree_chmax(k, x); if constexpr (cmd == 3) push_add(k, x); if constexpr (cmd == 4) subtree_chmin(k, x), subtree_chmax(k, x); } template void inner_apply(int l, int r, i64 x) { if (l == r) return; l += n, r += n; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) _apply(l++, x); if (r & 1) _apply(--r, x); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template inline i64 e() { if constexpr (cmd == 1) return INF; if constexpr (cmd == 2) return -INF; return 0; } template inline void op(i64& a, const Node& b) { if constexpr (cmd == 1) a = min(a, b.l1); if constexpr (cmd == 2) a = max(a, b.g1); if constexpr (cmd == 3) a += b.sum; } template i64 inner_fold(int l, int r) { if (l == r) return e(); l += n, r += n; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } i64 lx = e(), rx = e(); while (l < r) { if (l & 1) op(lx, v[l++]); if (r & 1) op(rx, v[--r]); l >>= 1; r >>= 1; } if constexpr (cmd == 1) lx = min(lx, rx); if constexpr (cmd == 2) lx = max(lx, rx); if constexpr (cmd == 3) lx += rx; return lx; } }; // [L,R)の範囲を管理 template struct RangeSet{ set> st; T TINF; RangeSet(){ TINF=numeric_limits::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } // [l,r) covered? bool covered(T l,T r){ r--; assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l and r<=ite->second; } bool covered(T x){ return covered(x,x); } // [l, r)がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair covered_by(T l,T r){ r--; assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return *ite; return make_pair(-TINF,-TINF); } pair covered_by(T x){ return covered_by(x,x); } // insert[l,r), 増加量を返す T insert(T l,T r){ r--; assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(0); T sum_erased=T(0); if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } // T insert(T x){ // return insert(x,x); // } // erase [l,r), 減少量を返す T erase(T l,T r){ r--; assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second){ // 完全に1つの区間に包含されている if(ite->firstfirst,l-1); if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l and l<=ite->second){ ret+=ite->second-l+1;// 消えた if(ite->firstfirst,l-1); ite=st.erase(ite);// 次へ }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } // 右端が区間の間にあるか if(ite->first<=r and r<=ite->second){ ret+=r-ite->first+1; if(rsecond) st.emplace(r+1,ite->second); st.erase(ite); } return ret; } // T erase(T x){ // return erase(x,x); // } // number of range int size(){ return (int)st.size()-2; } // mex [x,~) T mex(T x=0){ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x and x<=ite->second) return ite->second+1; else return x; } void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["< get(){ set

res; Each(s, st){ if(s.first==-TINF or s.second==TINF) continue; res.insert(mp(s.fi, s.se+1)); } return res; } }; int solve(){ ll n; cin>>n; //vector> query(n+1); map query; Zip zip; rep(i, n){ ll l,r,a; cin>>l>>r>>a; l--; zip.add(l); zip.add(r); //query[i] = mp(a,mp(l,r)); query[a].emplace_back(l,r); } //sort(ALL(query)); //dbg(query) ll Q; cin>>Q; Vec ques(Q); cin>>ques; rep(i,Q)ques[i]--; rep(i,Q)zip.add(ques[i]); zip.init(); dbgmap(query); ll m = zip.size(); dbg(m); dbg(zip.v); Vec init(m+2,INF/400); AngelBeats seg(init); ll mx = 1e5+10; //debug REP(x,0,mx){ RangeSet rs; rs.insert(0,m); Each(p, query[x]){ auto [l, r] = p; ll li = zip.id(l); ll ri = zip.id(r); dbg(-x) dbg(mp(li,ri)) rs.erase(li,ri); } //dbg(x); Each(p, rs.get()){ auto [l, r] = p; seg.range_chmin(l,r,x); } //seg.debug(m); } rep(i,Q){ ll id = zip.id(ques[i]); ll ans = seg.range_sum(id,id+1); out(ans); } return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout<>T; // while(T--) solve(); }