admin管理员组文章数量:1567526
记录一个菜逼的成长。。
题目链接
题目大意:
有四种操作。
0
:清除所有点
3
:程序结束
笔记
注意这里一个点可以有很多种颜色,是不会被覆盖的。
颜色最多51种。我们就建51棵线段树。
每个线段树按
ps:看了cls(claris)的cpp感觉学到了姿势啊。orz.
时间复杂度
#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;
}
版权声明:本文标题:【HDU6183】Color it(线段树) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1726363884a1067208.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论