#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include // #include // #include // #include // using namespace __gnu_pbds; // #include // namespace multiprecisioninteger = boost::multiprecision; // using cint=multiprecisioninteger::cpp_int; using namespace std; using ll=long long; using datas=pair; using ddatas=pair; using tdata=pair; using vec=vector; using mat=vector; using pvec=vector; using pmat=vector; // using llset=tree,rb_tree_tag,tree_order_statistics_node_update>; #define For(i,a,b) for(i=a;i<(ll)b;++i) #define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i) #define rep(i,N) For(i,0,N) #define rep1(i,N) For(i,1,N) #define brep(i,N) bFor(i,N,0) #define brep1(i,N) bFor(i,N,1) #define all(v) (v).begin(),(v).end() #define allr(v) (v).rbegin(),(v).rend() #define vsort(v) sort(all(v)) #define vrsort(v) sort(allr(v)) #define uniq(v) vsort(v);(v).erase(unique(all(v)),(v).end()) #define endl "\n" #define popcount __builtin_popcountll #define eb emplace_back #define print(x) cout< ostream& operator<<(ostream& os,const pair& p){return os<<"("< ostream& operator<<(ostream& os,const vector& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const set& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const multiset& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< ostream& operator<<(ostream& os,const map& v){ os<<"{";bool f=false; for(auto& x:v){if(f)os<<",";os< inline bool chmax(T& a,const T b){bool x=a inline bool chmin(T& a,const T b){bool x=a>b;if(x)a=b;return x;} #ifdef DEBUG void debugg(){cout<void debugg(const T& x,const Args&... args){cout<<" "< struct SegmentTree2DCompressed { using merge_f = function< get_t(get_t, get_t) >; using range_get_f = function< get_t(structure_t &, int, int) >; using update_f = function< void(structure_t &, int, update_t) >; int sz; vector< structure_t > seg; const merge_f f; const range_get_f g; const update_f h; const get_t identity; vector< vector< int > > LL, RR; vector< vector< int > > beet; SegmentTree2DCompressed(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity) : f(f), g(g), h(h), identity(identity) { sz = 1; while(sz < n) sz <<= 1; beet.resize(2 * sz); LL.resize(2 * sz); RR.resize(2 * sz); } void update(int a, int x, update_t z, int k, int l, int r) { if(r <= a || a + 1 <= l) return; if(a <= l && r <= a + 1) return h(seg[k], x, z); update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1); update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r); return h(seg[k], x, z); } void update(int x, int y, update_t z) { y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]); return update(x, y, z, 1, 0, sz); } get_t query(int a, int b, int x, int y, int k, int l, int r) { if(a >= r || b <= l) return identity; if(a <= l && r <= b) return g(seg[k], x, y); return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1), query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r)); } get_t query(int a, int b, int x, int y) { x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]); y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]); return query(a, b, x, y, 1, 0, sz); } void build() { for(int k = (int) beet.size() - 1; k >= sz; k--) { sort(begin(beet[k]), end(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); } for(int k = sz - 1; k > 0; k--) { beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size()); merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]), begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k])); beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k])); LL[k].resize(beet[k].size() + 1); RR[k].resize(beet[k].size() + 1); int tail1 = 0, tail2 = 0; for(int i = 0; i < beet[k].size(); i++) { while(tail1 < beet[2 * k + 0].size() && beet[2 * k + 0][tail1] < beet[k][i]) ++tail1; while(tail2 < beet[2 * k + 1].size() && beet[2 * k + 1][tail2] < beet[k][i]) ++tail2; LL[k][i] = tail1, RR[k][i] = tail2; } LL[k][beet[k].size()] = (int) beet[2 * k + 0].size(); RR[k][beet[k].size()] = (int) beet[2 * k + 1].size(); } for(int k = 0; k < beet.size(); k++) { seg.emplace_back(structure_t(beet[k].size())); } } void preupdate(int x, int y) { beet[x + sz].push_back(y); } }; ll calcS(ll a,ll b,ll c,ll d,ll e,ll f){ c-=a;d-=b; e-=a;f-=b; return abs(c*f-d*e); } ll max(ll a,ll b){return std::max(a,b);} ll maxe(){return -1;} #include using segtree=atcoder::segtree; using dtree=SegmentTree2DCompressed; int main(){ startupcpp(); ll i,N,Q; cin>>N>>Q; vec t(Q),l(Q),r(Q),s(Q),fl(N),fr(N),fs(N); rep(i,N){ int a,b,c,d,e,f; cin>>a>>b>>c>>d>>e>>f; fl[i]=min({a,c,e}); fr[i]=max({a,c,e}); fs[i]=calcS(a,b,c,d,e,f); } rep(i,Q){ cin>>t[i]; if(t[i]==1){ int a,b,c,d,e,f; cin>>a>>b>>c>>d>>e>>f; l[i]=min({a,c,e}); r[i]=max({a,c,e}); s[i]=calcS(a,b,c,d,e,f); }else cin>>l[i]>>r[i]; } vec za; for(auto& x:l)za.emplace_back(x); for(auto& x:r)za.emplace_back(x); for(auto& x:fl)za.emplace_back(x); for(auto& x:fr)za.emplace_back(x); uniq(za); dtree tree(za.size(),[](ll a,ll b){return max(a,b);},[](segtree& x,int a,int b){return x.prod(a,b);},[](segtree& x,int a,ll b){x.set(a,b);},-1); for(auto& x:l)x=lower_bound(all(za),x)-za.begin(); for(auto& x:r)x=lower_bound(all(za),x)-za.begin(); for(auto& x:fl)x=lower_bound(all(za),x)-za.begin(); for(auto& x:fr)x=lower_bound(all(za),x)-za.begin(); rep(i,N)tree.preupdate(fl[i],fr[i]); rep(i,Q)tree.preupdate(l[i],r[i]); tree.build(); rep(i,N)tree.update(fl[i],fr[i],fs[i]); rep(i,Q){ if(t[i]==1)tree.update(l[i],r[i],s[i]); else print(tree.query(l[i],r[i]+1,l[i],r[i]+1)); } }