【HDU6183】Color it(线段树)

admin管理员组

文章数量:1531452

记录一个菜逼的成长。。

题目链接

题目大意:

有四种操作。
0 $0$:清除所有点
1 x y c$1\ x\ y\ c$:给点 (x,y) $(x,y)$添加一种颜色 c $c$
2 x y1 y2$2\ x\ y1\ y2$:在 (0,y1) $(0,y1)$与 (x,y2) $(x,y2)$所围成的矩形里有多少种颜色
3 $3$:程序结束

笔记

注意这里一个点可以有很多种颜色，是不会被覆盖的。
颜色最多51种。我们就建51棵线段树。
每个线段树按y$y$轴建树，每个结点的值是在范围内的最小的 x $x$值
ps:看了cls(claris)的cpp感觉学到了姿势啊。orz.
时间复杂度O(50nlogn)$O(50nlogn)$

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for( int i = l; i <= r; i++ )
#define rep0(i,l,r) for( int i = l; i < r; i++ )
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int maxn = 1000000 + 10;
int T[100],l[maxn],r[maxn],v[maxn];
int tot,X,y1,y2,flag;
void ins(int &t,int L,int R,int y,int x) {
  if(!t){
    t = ++tot;
    v[t] = x;
  }
  if(v[t] > x)v[t] = x;//保存最小的x值
  if(L == R)return ;
  int mid = (L + R) >> 1;
  if(y <= mid)ins(l[t],L,mid,y,x);
  else ins(r[t],mid+1,R,y,x);
}
void ask(int t,int L,int R) {
  if(flag || !t)return ;
  if(y1 <= L && y2 >= R){
    if(v[t] <= X)flag = 1;
    return ;
  }
  int mid = (L + R) >> 1;
  if(y1 <= mid)ask(l[t],L,mid);
  if(y2 >  mid)ask(r[t],mid+1,R);
}
int main()
{
  for (int i = 0; i <= 50; i++)T[i] = 0;
  int ope;
  while (~scanf("%d",&ope)) {
    if (ope == 3)return 0;
    if (ope == 0) {
      for (int i = 0; i <= 50; i++)T[i] = 0;
      for (int i = 1; i <= tot; i++) l[i] = r[i] = 0;
      tot = 0;
    }
    else if (ope == 1) {
      int x,y,c;
      scanf("%d%d%d",&x,&y,&c);
      ins(T[c],1,1000000,y,x);
    }
    else if(ope == 2){
      scanf("%d%d%d",&X,&y1,&y2);
      int ans = 0;
      for (int i = 0; i <= 50; i++) {
        flag = 0;
        ask(T[i],1,1000000);
        if(flag)ans++;
      }
      printf("%d\n",ans);
    }
  }
  return 0;
}

本文标签： 线段Color