PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Segment trees (with lazy propagation), sweep line, Euler tour on trees
PROBLEM:
You are given N rectangles in the plane. Initially, all of them have white borders.
Two rectangles will not touch or intersect, though one may be contained within another.
Process Q updates of the following types:
- Given i and c, color the border of the i-th rectangle c (c= 0/1 denotes white/black).
Also do this for every rectangle contained within the i-th. - Given i and a new rectangle, replace the i-th rectangle with this one. The new rectangle has white borders.
No two rectangles ever created will touch or intersect.
After each update, output the number of rectangles with black borders.
EXPLANATION:
Let’s try to solve the problem if there were no type 2 queries first - that is, we have some N disjoint rectangles, and each update colors some of them black or white.
This seems like a geometry task, but it really isn’t! (for the most part, at least)
The key here is to use the fact that no two rectangles intersect; so for any two of them, either one is contained inside the other, or they’re entirely disjoint.
In particular, that means that for each rectangle, there’s a unique smallest (say, by area) rectangle other than itself that contains it (or there’s nothing containing it).
Let \text{cover}_i denote the index of the unique smallest rectangle covering rectangle i.
If nothing covers rectangle i, let \text{cover}_i = 0.
Consider a graph on the vertices 0, 1, 2, \ldots, N where for each i, we draw the edge \text{cover}_i \to i.
Observe that this graph is a tree! After all, \text{cover}_i is simply the parent of i in this tree.
Furthermore, for two rectangles i and j, i contains j if and only if j is present in the subtree of i.
So, updates of the form “color every rectangle contained inside i, with c” can be rephrased as “color every vertex inside the subtree of i, with c”.
After each update, we’d like to know the number of vertices in the tree that are colored 1.
Now that the geometry problem has been converted to a tree one, there are two things we need to do:
- First, we need to actually compute this tree from the given rectangles;
- Second, we need to solve the problem on the tree.
Building the tree
This can be done with a sweepline; once again (ab)using the fact that the rectangles are disjoint to keep things simple.
Consider sweeping the x-coordinate from -\infty to \infty.
Let A_y denote the index of the smallest rectangle that’s currently covering y-coordinate y.
Initially, A is filled with zeros.
Then, consider what happens when you encounter the border of a rectangle; say with index i and that spans y-coordinates [y_1, y_2].
- If this is the left border of the rectangle, set \text{cover}_i := A_{y_1} (this will be the index of the smallest rectangle covering i).
Then, for each y_1 \leq y \leq y_2, set A_y := i, since rectangle i is now the smallest rectangle covering those coordinates. - If this is the right border of the rectangle, for each y_1 \leq y \leq y_2, set A_y := \text{cover}_i.
Essentially, we’re “unsetting” the effect of rectangle i; and when doing so, the smallest one covering its range will be the smallest one covering it overall.
The operations we want to perform are a “range set” and “point query” on array A.
This is a classical problem that can be solved using a segment tree and lazy propagation.
The sweep itself can be done quickly by processing a sorted list of rectangle borders (those are the only x-coordinates we care about).
The time complexity here is \mathcal{O}(N\log N).
Note that if you don’t use coordinate compression on array A, it becomes \mathcal{O}(N\log{10^{18}}) instead, which is marginally slower.
Processing updates
Now that we have our tree, we want to perform “subtree set” operations, and find the number of ones in the whole tree after each operation.
Every value is 0 or 1, so we equivalently just want the sum of the tree.
This is a rather standard task, and can be solved by building the Euler tour of the tree.
Essentially, the tree is flattened out into an array, in such a way that every subtree of the tree corresponds to some subarray of this array (sounds fancy, but it’s really just writing out vertices in DFS order).
With this done, “subtree set” turns into “range set”, and range set updates along with range sum queries can also be processed quickly with a segment tree + lazy propagation.
With this easier version done, let’s move back to the original problem, where rectangles can change.
Luckily, it’s not much of a jump: most of the work is already done.
We don’t have to answer queries online, so we can first read all rectangles, and once again build the covering tree out of them.
Each vertex of this tree will now hold two integers though: its value, and whether it’s active or not.
Initially, the active vertices are those that represent the first N rectangles.
The answer after an update is the sum of values of only active vertices, rather than all vertices.
That can be maintained by simply extending the information stored in each segment tree node.
Specifically, you can maintain the answer for that nodes (i.e the sum of values of all active vertices in the range it represents), and the number of active vertices in its range.
When updating:
- A type 1 update doesn’t change which nodes are active or not.
So, it can be done as usual: for any segment fully covered within the updated range, its answer will now equal the number of active vertices contained within it (rather than the length of the range). - A type 2 update activates one vertex and deactivates another.
These are point updates and are easily handled in \mathcal{O}(\log N) time by just walking down the segment tree.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
#else
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
#endif
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
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) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
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 <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e> struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
#endif
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace atcoder;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
struct S{
int num,tot;
};
S op(S l,S r){
return {l.num+r.num,l.tot+r.tot};
}
S e1(){
return {0,0};
}
struct F{
int col;
};
F composition(F l,F r){
return (l.col == INF ? r : l);
}
S mapping(F l,S r){
if(l.col == INF)return r;
if(l.col == 1)return {r.tot,r.tot};
return {0,r.tot};
}
F id(){
return {INF};
}
int opp(int a, int b) { return max(a, b); }
int ee() { return -2*INF; }
int target;
bool f(int v) { return v <= target; }
const int N = 4e5+5;
vi adj[N];
vi par(N);
vi sr(N),en(N);
int timer;
void dfs(int cur){
sr[cur] = timer++;
for(auto x : adj[cur]){
if(x == par[cur])continue;
dfs(x);
}
en[cur] = timer;
}
void solve()
{
ll n,q;
cin>>n>>q;
assert(1<=n && n<=2e5);
assert(1<=q && q<=2e5);
ll cnt[n+1];
vector <pair<ll,ll>> u;
for(int i=0;i<n;i++){
cnt[i+1]=i;
}
ll a,b,c,d;
vector <pair<pair<ll,ll>,pair<ll,ll>>> v;
set <ll> s;
for(int i=1;i<=n;i++){
cin>>a>>b>>c>>d;
assert(max(abs(a),max(abs(b),max(abs(c),abs(d))))<=1e18);
par[v.size()]=-1;
u.push_back({a,v.size()});
u.push_back({c,v.size()});
s.insert(b);
v.push_back({{a,b},{c,d}});
}
vector <ll> order;
vector <pair<ll,ll>> color;
vector <pair<ll,ll>> change;
for(int i=1;i<=q;i++){
cin>>a;
assert(a==1 || a==2);
order.push_back(a);
if(a==1){
cin>>a>>b;
assert(1<=a && a<=n);
assert(b==0 || b==1);
color.push_back({a,b});
}else{
cin>>a;
assert(1<=a && a<=n);
change.push_back({a,v.size()});
cin>>a>>b>>c>>d;
assert(max(abs(a),max(abs(b),max(abs(c),abs(d))))<=1e18);
u.push_back({a,v.size()});
u.push_back({c,v.size()});
s.insert(b);
par[v.size()]=-1;
v.push_back({{a,b},{c,d}});
}
}
map <ll,ll> mcnt;
map <ll,ll> mpos;
ll mtt=0;
for(auto it:s){
mcnt[it]=mtt;
mtt++;
}
ll m=v.size();
ll done[m]={};
sort(u.begin(),u.end());
segtree<int,opp,ee> seg(m);
for(auto it:u){
if(done[it.second]==0){
done[it.second]=1;
seg.set(mcnt[v[it.second].first.second],v[it.second].second.second);
mpos[mcnt[v[it.second].first.second]]=it.second;
}else{
target=v[it.second].second.second;
done[it.second]=0;
mtt=seg.min_left<f>(mcnt[v[it.second].first.second])-1;
if(mtt==-1){
par[it.second]=mtt;
}else{
par[it.second]=mpos[mtt];
}
seg.set(mcnt[v[it.second].first.second],-2*INF);
}
}
for(int i=0;i<v.size();i++){
if(par[i] != -1){
adj[par[i]].pb(i);
adj[i].pb(par[i]);
}
}
for(int i=0;i<v.size();i++){
if(par[i]==-1){
dfs(i);
}
}
reverse(color.begin(),color.end());
reverse(change.begin(),change.end());
lazy_segtree<S, op, e1, F, mapping, composition, id> st(m);
for(int i=0;i<n;i++){
S nw = {0,1};
st.set(sr[i],nw);
}
for(auto op:order){
if(op == 1){//color c from l to r
int nd;nd=color.back().first;
nd=cnt[nd];
int c;c=color.back().second;
color.pop_back();
// int l,r;cin >> l;cin >> r;
st.apply(sr[nd],en[nd],{c});
}else{
int fff=change.back().first;
int ffs=change.back().second;
change.pop_back();
int nd=cnt[fff];
st.set(sr[nd],{0,0});
nd=ffs;
S nw = {0,1};
st.set(sr[nd],nw);
cnt[fff]=ffs;
}
cout << st.all_prod().num << "\n";//calculate total activate colored 1 number;
}
timer = 0;
for(int i=0;i<v.size();i++){
adj[i].clear();
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t; cin >> t; assert(1<=t && t<=1e5);while(t--)solve();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
namespace n0 {
struct segtree {
using T = pair<int, int>;
using F = int;
T e() {
return make_pair(-2, -2);
}
F id() {
return -2;
}
T op(T a, T b) {
if (a.first == -2) {
return b;
} else if (b.first == -2) {
return a;
}
return make_pair(min(a.first, b.first), max(a.second, b.second));
}
T mapping(F f, T x) {
if (f == -2) {
return x;
}
return make_pair(f, f);
}
F composition(F f, F g) {
if (f == -2) {
return g;
}
return f;
}
int n;
int size;
int log_size;
vector<T> node;
vector<F> lazy;
segtree() : segtree(0) {}
segtree(int _n) {
build(vector<T>(_n, e()));
}
segtree(const vector<T>& v) {
build(v);
}
void build(const vector<T>& v) {
n = (int) v.size();
if (n <= 1) {
log_size = 0;
} else {
log_size = 32 - __builtin_clz(n - 1);
}
size = 1 << log_size;
node.resize(2 * size, e());
lazy.resize(size, id());
for (int i = 0; i < n; i++) {
node[i + size] = v[i];
}
for (int i = size - 1; i > 0; i--) {
pull(i);
}
}
void push(int x) {
node[2 * x] = mapping(lazy[x], node[2 * x]);
node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
if (2 * x < size) {
lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
}
lazy[x] = id();
}
void pull(int x) {
node[x] = op(node[2 * x], node[2 * x + 1]);
}
void set(int p, T v) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = v;
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
T get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
return node[p];
}
T get(int l, int r) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
T vl = e();
T vr = e();
while (l < r) {
if (l & 1) {
vl = op(vl, node[l++]);
}
if (r & 1) {
vr = op(node[--r], vr);
}
l >>= 1;
r >>= 1;
}
return op(vl, vr);
}
void apply(int p, F f) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = mapping(f, node[p]);
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
int ll = l;
int rr = r;
while (l < r) {
if (l & 1) {
node[l] = mapping(f, node[l]);
if (l < size) {
lazy[l] = composition(f, lazy[l]);
}
l++;
}
if (r & 1) {
r--;
node[r] = mapping(f, node[r]);
if (l < size) {
lazy[r] = composition(f, lazy[r]);
}
}
l >>= 1;
r >>= 1;
}
l = ll;
r = rr;
for (int i = 1; i <= log_size; i++) {
if (((l >> i) << i) != l) {
pull(l >> i);
}
if (((r >> i) << i) != r) {
pull((r - 1) >> i);
}
}
}
};
vector<vector<int>> make_graph(const vector<vector<int>>& a) {
int m = (int) a.size();
vector<int> order(2 * m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
long long x = (i < m ? a[i][0] : a[i - m][2]);
long long y = (j < m ? a[j][0] : a[j - m][2]);
return x < y;
});
segtree seg(vector<pair<int, int>>(2 * m, make_pair(-1, -1)));
vector<int> last(m, -1);
for (int i : order) {
if (i < m) {
auto p = seg.get(a[i][1], a[i][3]);
assert(p.first == p.second);
last[i] = p.first;
seg.apply(a[i][1], a[i][3], i);
} else {
i -= m;
seg.apply(a[i][1], a[i][3], last[i]);
}
}
vector<vector<int>> g(m);
for (int i = 1; i < m; i++) {
g[last[i]].emplace_back(i);
}
return g;
}
} // namespace n0
namespace n1 {
struct segtree {
using T = vector<int>;
using F = int;
T e() {
return {0, 0};
}
F id() {
return -1;
}
T op(T a, T b) {
for (int i = 0; i < 2; i++) {
a[i] += b[i];
}
return a;
}
T mapping(F f, T x) {
if (f == -1) {
return x;
}
x[f] = x[0] + x[1];
x[f ^ 1] = 0;
return x;
}
F composition(F f, F g) {
if (f == -1) {
return g;
}
return f;
}
int n;
int size;
int log_size;
vector<T> node;
vector<F> lazy;
segtree() : segtree(0) {}
segtree(int _n) {
build(vector<T>(_n, e()));
}
segtree(const vector<T>& v) {
build(v);
}
void build(const vector<T>& v) {
n = (int) v.size();
if (n <= 1) {
log_size = 0;
} else {
log_size = 32 - __builtin_clz(n - 1);
}
size = 1 << log_size;
node.resize(2 * size, e());
lazy.resize(size, id());
for (int i = 0; i < n; i++) {
node[i + size] = v[i];
}
for (int i = size - 1; i > 0; i--) {
pull(i);
}
}
void push(int x) {
node[2 * x] = mapping(lazy[x], node[2 * x]);
node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]);
if (2 * x < size) {
lazy[2 * x] = composition(lazy[x], lazy[2 * x]);
lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]);
}
lazy[x] = id();
}
void pull(int x) {
node[x] = op(node[2 * x], node[2 * x + 1]);
}
void set(int p, T v) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = v;
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
T get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
return node[p];
}
T get(int l, int r) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
T vl = e();
T vr = e();
while (l < r) {
if (l & 1) {
vl = op(vl, node[l++]);
}
if (r & 1) {
vr = op(node[--r], vr);
}
l >>= 1;
r >>= 1;
}
return op(vl, vr);
}
void apply(int p, F f) {
assert(0 <= p && p < n);
p += size;
for (int i = log_size; i >= 1; i--) {
push(p >> i);
}
node[p] = mapping(f, node[p]);
for (int i = 1; i <= log_size; i++) {
pull(p >> i);
}
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= n);
l += size;
r += size;
for (int i = log_size; i >= 1; i--) {
if (((l >> i) << i) != l) {
push(l >> i);
}
if (((r >> i) << i) != r) {
push((r - 1) >> i);
}
}
int ll = l;
int rr = r;
while (l < r) {
if (l & 1) {
node[l] = mapping(f, node[l]);
if (l < size) {
lazy[l] = composition(f, lazy[l]);
}
l++;
}
if (r & 1) {
r--;
node[r] = mapping(f, node[r]);
if (l < size) {
lazy[r] = composition(f, lazy[r]);
}
}
l >>= 1;
r >>= 1;
}
l = ll;
r = rr;
for (int i = 1; i <= log_size; i++) {
if (((l >> i) << i) != l) {
pull(l >> i);
}
if (((r >> i) << i) != r) {
pull((r - 1) >> i);
}
}
}
};
void answer_queries(const vector<vector<int>>& g, const vector<vector<int>>& que, int n) {
int m = (int) g.size();
vector<int> beg(m), end(m), order;
function<void(int, int)> Dfs = [&](int v, int p) {
beg[v] = (int) order.size();
order.emplace_back(v);
for (int to : g[v]) {
if (to == p) {
continue;
}
Dfs(to, v);
}
end[v] = (int) order.size();
};
Dfs(0, -1);
int q = (int) que.size();
vector<int> where(n + 1);
iota(where.begin(), where.end(), 0);
vector<vector<int>> ss(m, vector<int>(2));
for (int i = 1; i <= n; i++) {
ss[beg[i]][0] = 1;
}
segtree seg(ss);
for (int i = 0; i < q; i++) {
int j = que[i][1];
if (que[i][0] == 1) {
seg.apply(beg[where[j]], end[where[j]], que[i][2]);
} else {
seg.set(beg[que[i][2]], vector<int>{1, 0});
seg.set(beg[where[j]], vector<int>(2, 0));
where[j] = que[i][2];
}
cout << seg.node[1][1] << '\n';
}
}
} // namespace n1
int main() {
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0, sq = 0;
while (tt--) {
int n = in.readInt(1, 2e5);
in.readSpace();
int q = in.readInt(1, 2e5);
in.readEoln();
sn += n;
sq += q;
vector<vector<long long>> a(n + 1, vector<long long>(4));
a[0][0] = a[0][1] = -2e18;
a[0][2] = a[0][3] = 2e18;
for (int i = 0; i < n; i++) {
a[i + 1] = in.readLongs(4, -1e18, 1e18);
in.readEoln();
assert(a[i + 1][0] < a[i + 1][2]);
assert(a[i + 1][1] < a[i + 1][3]);
}
int m = (int) a.size();
vector<vector<int>> que(q, vector<int>(3));
for (int i = 0; i < q; i++) {
que[i][0] = in.readInt(1, 2);
in.readSpace();
que[i][1] = in.readInt(1, n);
in.readSpace();
if (que[i][0] == 1) {
que[i][2] = in.readInt(0, 1);
} else {
que[i][2] = m;
a.emplace_back(in.readLongs(4, -1e18, 1e18));
assert(a[m][0] < a[m][2]);
assert(a[m][1] < a[m][3]);
m++;
}
in.readEoln();
}
vector<vector<int>> b(m, vector<int>(4));
{
vector<vector<long long>> c(2);
for (int i = 0; i < m; i++) {
for (int j = 0; j < 4; j++) {
c[j % 2].emplace_back(a[i][j]);
}
}
for (int i = 0; i < 2; i++) {
sort(c[i].begin(), c[i].end());
c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 4; j++) {
b[i][j] = (int) (lower_bound(c[j % 2].begin(), c[j % 2].end(), a[i][j]) - c[j % 2].begin());
}
}
}
debug(b);
auto g = n0::make_graph(b);
debug(g);
n1::answer_queries(g, que, n);
}
in.readEof();
assert(sn <= 2e5);
assert(sq <= 2e5);
return 0;
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Node {
using T = array<ll, 3>; // value, number of active, sum of active
T unit = {0, 0, 0};
T f(T a, T b) {
a[0] += b[0];
a[1] += b[1];
a[2] += b[2];
return a;
}
Node *l = 0, *r = 0;
int lo, hi;
int mset = -1;
T val = unit;
Node(int _lo,int _hi):lo(_lo),hi(_hi){}
T query(int L, int R) {
if (R <= lo || hi <= L) return unit;
if (L <= lo && hi <= R) return val;
push();
return f(l->query(L, R), r->query(L, R));
}
void set(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
mset = x;
val[0] = x;
val[2] = val[1]*x;
}
else {
push(), l->set(L, R, x), r->set(L, R, x);
val = f(l->val, r->val);
}
}
void upd(int pos, int x) {
if (lo > pos or hi <= pos) return;
if (lo == hi-1) {
val[0] = val[2] = 0;
val[1] = x;
}
else {
push();
l->upd(pos, x), r->upd(pos, x);
val = f(l->val, r->val);
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mset != -1)
l->set(lo,hi,mset), r->set(lo,hi,mset), mset = -1;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
map<ll, int> compress;
vector<array<ll, 4>> rect;
for (int i = 0; i < n; ++i) {
ll a, b, c, d; cin >> a >> b >> c >> d;
rect.push_back({a, b, c, d});
compress[b], compress[d+1];
}
struct Query {
int type, pos, id, col;
array<ll, 4> chng;
};
vector<Query> qry(q);
int sz = n;
for (auto &x : qry) {
cin >> x.type >> x.pos;
--x.pos;
if (x.type == 1) cin >> x.col;
else {
for (int i = 0; i < 4; ++i) cin >> x.chng[i];
compress[x.chng[1]], compress[x.chng[3]+1];
rect.push_back(x.chng);
x.id = sz++;
}
}
{
int k = 0;
for (auto &[x, y] : compress) y = k++;
}
++sz;
vector adj(sz, vector<int>());
vector<int> par(sz);
vector<array<ll, 4>> events;
for (int i = 0; i < sz-1; ++i) {
auto [a, b, c, d] = rect[i];
events.push_back({a, i+1, b, d});
events.push_back({c+1, -i-1, b, d});
}
sort(begin(events), end(events));
Node *sweepseg = new Node(0, compress.size());
for (auto [_, id, y1, y2] : events) {
y1 = compress[y1], y2 = compress[y2+1];
if (id < 0) {
int x = par[-id];
sweepseg -> set(y1, y2, x);
}
else {
par[id] = sweepseg->query(y1, y1+1)[0];
sweepseg -> set(y1, y2, id);
}
}
for (int i = 1; i < sz; ++i) adj[par[i]].push_back(i);
vector<int> in(sz), out(sz);
int timer = 0;
auto dfs = [&] (const auto &self, int u) -> void {
in[u] = timer++;
for (int v : adj[u]) self(self, v);
out[u] = timer;
};
dfs(dfs, 0);
Node *treeseg = new Node(0, sz);
for (int i = 1; i <= n; ++i) treeseg -> upd(in[i], 1);
vector<int> curid(n);
for (int i = 0; i < n; ++i) curid[i] = i+1;
for (auto x : qry) {
if (x.type == 1) {
int u = curid[x.pos];
treeseg -> set(in[u], out[u], x.col);
}
else {
treeseg -> upd(in[curid[x.pos]], 0);
curid[x.pos] = x.id+1;
treeseg -> upd(in[curid[x.pos]], 1);
}
cout << treeseg->query(0, sz)[2] << '\n';
}
}
}