Primero construyamos un grafo en el que a cada nodo representa a una sábana, y hay una arista dirigida del nodo ~x~ al nodo ~y~ si la sábana que representa el nodo ~x~ es la menor entre todas las que poseen área en común con la sábana representada por el nodo ~y~. Es fácil ver que el grafo formado es un bosque y que si un nodo se mancha de un color todos sus ancestros hasta la raíz también lo hacen (o lo hicieron, pues comparten un área en común).

Para simplicidad en el código y entendimiento, podemos añadir una sábana enorme con ~id = 0~ que tenga área de intersección con todas y no esté contenida en ninguna y así tendríamos sólo un árbol.

Para construir dicho árbol usamos un Sweep Line por las ~x~s de la siguiente forma:

1. Hay tres tipos de eventos, (1) un rectángulo (sábana) se abre, (2) aparece una bola y (3) un rectángulo se cierra.
2. Si hay varios eventos con la misma ~x~ serán procesados en el orden anterior (no queremos perdernos una bola :)).
3. Para cada evento tenemos un intervalo ~[y0, y1]~ sobre el eje ~Y~, que representa (1) para los rectángulos el inicio y el fin verticalmente y (2) para las bolas la ~y~ de su coordenada (en este caso ~y0 = y1~).
4. Tenemos además para cada evento un ~id~, que representa (1) para los rectángulos el ~id~ del mismo y (2) para las bolas su color.
5. Y por supuesto se tiene la ~x~ del evento que se usará para ordenar los mismos.

Antes de comenzar el barrido añadimos un evento de tipo 1 (rectángulo se abre) con ~x=-inf~, ~id=0~, ~y0=-inf~, ~y1=inf~; esta será nuestra súper sábana. Ahora estamos listos para comenzar el barrido:

1. Si el elemento acutal es un inicio de rectángulo, preguntamos al ST por la posición ~y0~ (o cualquiera entre ~[y0, y1]~), este será nuestro padre en el árbol llamemosle ~p[id]~, actualizamos el segment tree en el rango ~[y0, y1]~ con el ~id~ actual.
2. Si el elemento acutal es una bola, preguntamos al ST por la posición ~y0~ (o ~y1~, da igual), este es el nodo que representa a la sábana más pequeña que debemos agregarle el color de la bola actual (~id~).
3. Si el elemento acutal es un fin de rectángulo, pintamos con el ST el intervalo ~[y0, y1]~ de color ~p[id]~.

Seguidamente creamos el grafo usando el arreglo de padres ~p~.

Ahora que tenemos el árbol podemos usar Small-to-Large technique (o DSU on trees) para contar para cada nodo cuántos colores distintos hay en su subárbol.

La complejidad de la primera parte es ~O(NlogN)~ y de la segunda ~O(Nlog^2N)~, por lo tanto en general será ~O(Nlog^2N)~.

Código:

    #pragma GCC optimize("Ofast")

    #include <bits/stdc++.h>
    using namespace std;

    typedef double d;
    typedef long long int ll;
    typedef long double ld;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    #define INIT ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
    #define endl '\n'
    #define fr first
    #define sc second
    #define pb push_back
    #define eb emplace_back
    #define mp make_pair
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define ers erase
    #define sz(c) ((int)(c).size())
    #define all(x) (x).begin(),(x).end()
    #define unique(x) (x).resize(unique(all(x))-(x).begin())
    #define debug(_fmt,...) fprintf(stderr,"("#__VA_ARGS__ ") = (" _fmt")\n",__VA_ARGS__)

    const d eps = 1e-12;

    inline int sign(d x) { return x < -eps ? -1 : x > eps; }
    inline int realcmp(d x, d y) { return sign(x-y); }
    template<typename T> void na(vector<T>& a, int n) {a = vector<T>(n);for(T& i: a) cin >> i;}
    template<typename T> void pv(vector<T>& a) { for(T& i: a) cout << i << ' '; cout << endl; }
    template<typename T> vector<T> shrink(vector<T>& x) { vector<T> vals = x; sort(all(vals)); unique(vals); for(T& i: x) i = ub(all(vals), i) - vals.begin(); return vals; }

    const int MX = 3e5+7;

    struct Event
    {
      int x, y0, y1, id;
      int t; // 0 - start, 1 - ball, 2 - end
      Event(){}
      Event(int x, int y0, int y1, int id, int t)
        : x(x), y0(y0), y1(y1), id(id), t(t) {}
      bool operator< (const Event& e)const
      {
        if(x != e.x) return x < e.x;
        return t < e.t;
      }
    };

    // segment tree
    int tree[MX << 2], lazy[MX << 2];

    void push(int i, int lo, int hi)
    {
      if(~lazy[i])
      {
        tree[i] = lazy[i];
        if(lo != hi)
        {
          int l = i << 1, r = l | 1;
          lazy[l] = lazy[i];
          lazy[r] = lazy[i];
        }
      }

      lazy[i] = -1;
    }

    void upd(int x, int y, int p, int i = 1, int lo = 1, int hi = MX)
    {
      push(i, lo, hi);
      if(lo > y || hi < x) return;
      if(x <= lo && hi <= y)
      {
        lazy[i] = p;
        tree[i] = p;
        push(i, lo, hi);
        return;
      }
      int m = (lo + hi) >> 1, l = i << 1, r = l | 1;
      upd(x, y, p, l, lo, m);
      upd(x, y, p, r, m+1, hi);
    }

    int qry(int x, int i = 1, int lo = 1, int hi = MX)
    {
      push(i, lo, hi);
      if(x > hi || x < lo) return -1;
      if(lo == hi) return tree[i];
      int m = (lo + hi) >> 1, l = i << 1, r = l | 1;
      int s1 = qry(x, l, lo, m);
      int s2 = qry(x, r, m+1, hi);
      if(~s1) return s1;
      return s2;
    }

    int p[MX];
    vector<int> color[MX];

    // small-to-large
    int ans[MX];
    vector<int> g[MX];
    void eadd(int u, int v)
    {
      g[u].pb(v);
      g[v].pb(u);
    }
    vector<set<int>> ss;
    int js(int x, int y)
    {
      if(x == y) return x;
      if(sz(ss[x]) < sz(ss[y])) swap(x, y);
      for(int i: ss[y]) ss[x].ins(i);
      return x;
    }

    int dfs(int u=0, int p=-1)
    {
      int my = sz(ss);
      ss.eb();
      for(int c: color[u]) ss.back().ins(c);
      for(int v: g[u]) if(v != p)
        my = js(my, dfs(v, u));
      ans[u] = sz(ss[my]);
      return my;
    }

    int main()
    {
      #ifdef OJUDGE
        //freopen("in","r",stdin);
      #endif
      INIT;

      int n, m;
      cin >> n >> m;

      vector<int> ys;
      vector<Event> E;

      for(int i=1;i<=n;++i)
      {
        int x0, y0, x1, y1;
        cin >> x0 >> y0 >> x1 >> y1;
        E.eb(x0, y0, y1, i, 0);
        E.eb(x1, y0, y1, i, 2);
        ys.eb(y0); ys.eb(y1);
      }

      for(int i=1;i<=m;++i)
      {
        int x, y, c;
        cin >> x >> y >> c;
        E.eb(x, y, y, c, 1);
        ys.eb(y);
      }

      // shrink ys
      auto vals = ys;
      sort(all(vals));
      unique(vals);
      for(auto& e: E)
      {
        e.y0 = ub(all(vals), e.y0) - vals.begin();
        e.y1 = ub(all(vals), e.y1) - vals.begin();
      }

      // sweep to initialize graph
      memset(lazy, -1, sizeof lazy);
      memset(tree, 0, sizeof tree);
      sort(all(E));
      for(auto& e: E)
      {
        if(e.t == 0)
        { // start
          p[e.id] = qry(e.y0);
          upd(e.y0, e.y1, e.id);
        }else if(e.t == 2)
        { // end
          upd(e.y0, e.y1, p[e.id]);
        }else // if(e.t == 1)
        { // ball
          color[qry(e.y0)].eb(e.id);
        }
      }

      for(int i=1;i<=n;++i) eadd(p[i], i);
      dfs();
      for(int i=1;i<=n;++i) cout << ans[i] << '\n';

      return 0;
    }

    #warning you will remember this, overflow is there, though you might not see it ...