【题解】Color it 动态开点线段树 hdu6183 ——quhengyi11

题目

可爱的传送门酱 (≧▽≦)

题解

动态开点线段树不太熟所以写一写，然而这道题我感觉难的是转化技巧= =

看到这个题目，你可能会产生和 qhy 一样的疑惑: 你要询问直接询问一个矩形就行了为什么规定了矩形的一条边一定在直线 $x=1$上面。然而这是一个对简化问题十分重要的条件，因为所有点的坐标是正整数，这样的条件相当于只规定了横坐标的上界 x。

然而这有什么用呢？

我们可以将横坐标 x 看成点的一个值 v，我们把纵坐标丢进线段树里面维护，每次询问就相当于询问 $[y1,y2]$的区间里面有没有值小于等于 x 的值。（突然感觉转化好简单 QAQ）

那开 51 棵线段树（颜色种数）不就行了。

然而你不确定每棵线段树要开多大空间呀，所以我们需要动态开点。

总结：看似二维猛如虎，实际降维难点无。

代码：

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 150005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define mod 19260817
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
int n, m, opt, x, y, ya, yb, tot, rt[51], c, ans;
bool fl;
struct tree{
    int ls, rs, v;
}t[N << 2];
inline void update (int &k, int l, int r, int val, int pos)
{
    if (!k)
    {
        k = ++tot;
        t[k].v = val;
    }
    t[k].v = std::min(t[k].v, val);
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid) update(t[k].ls, l, mid, val, pos);
        else update(t[k].rs, mid + 1, r, val, pos);
}
inline void query (int k, int l, int r, int val, int L, int R)
{
    if (fl || !k) return;
    if (L <= l && r <= R)
    {
        if (t[k].v <= val)
            fl = 1;
        return;
    }
    int mid = l + r >> 1;
    if (L <= mid) query(t[k].ls, l, mid, val, L, R);
    if (mid < R) query(t[k].rs, mid + 1, r, val, L, R);
}
int main ()
{
    while (scanf("%d", &opt))
    {
        if (opt == 0)
        {
            fo (i, 0, 50) rt[i] = 0;
            fo (i, 1, tot) t[i].ls = t[i].rs = t[i].v = 0;
            tot = 0;
        }
        else
        if (opt == 1)
        {
            scanf("%d %d %d", &x, &y, &c);
            update(rt[c], 1, 1e6, x, y);
        }
        else
        if (opt == 2)
        {
            scanf("%d %d %d", &x, &ya, &yb);
            ans = 0;
            fo (i, 0, 50)
            {
                fl = 0;
                query(rt[i], 1, 1e6, x, ya, yb);
                ans += fl;
            }
            printf("%d\n", ans);
        }
        else
            break;
    }
    return 0;
}