B - Color itHDU - 6183
题目大意：有三种操作，0是清空所有点，1是给点(x,y)涂上颜色c，2是查询满足1<=a<=x,y1<=b<=y2的(a,b)点一共有几种不同的颜色
一开始做的时候直接就是开51个vector保存每个颜色相应的点，然后就是询问就是，暴力循环判断这个颜色存不存在一个满足条件的点，感觉最差情况下应该会超时，不过却过了
#include<cstdio>
#include<vector>
using namespace std;
struct Node{
int x,y;
Node(){}
Node(int x,int y):x(x),y(y){}
};
vector<Node> c[];
int main()
{
int op,x,y,y1,cc;
while(scanf("%d",&op)&&op!=)
{
if(op==)
{
for(int i=;i<=;i++)
c[i].clear();
}
else if(op==)
{
scanf("%d%d%d",&x,&y,&cc);
c[cc].push_back(Node(x,y));
}
else
{
scanf("%d%d%d",&x,&y,&y1);
int ans=;
for(int i=;i<=;i++)
{
for(int j=;j<c[i].size();j++)
if(c[i][j].x<=x&&c[i][j].y>=y&&c[i][j].y<=y1)
{
ans++;
break;
}
}
printf("%d\n",ans);
}
}
return ;
}
暴力过一切
然后看网上有是线段树动态开点的做法，但实际上并不比上面暴力的写法快，反而慢上几十ms，不过可以当做一个算法扩展来联系。
首先1操作肯定就是单点更新了，而2操作上已经限定了x的左边为1，所以我们以y轴来建线段树维护个区间内x的最小值，那么2操作就是区间查询了。但我们知道正常静态的线段树需要4*SIZE的节点空间来保存信息的，在这里又需要51颗线段树，也就是51*4*1000000的空间来保存节点信息，不知道你们电脑能不能开那么大的数组，反正我的电脑和OJ的虚拟机是不行的。但其实最多150000个1操作和2操作，并不需要那么大的空间。所以这时候需要用到线段树的动态开点了。
静态的线段树，每个编号为x的节点，它的左孩子编号就为2*x，右孩子编号就为2*x+1，然后这个节点x，我们是保存它的区间L,R和其他一系列信息。而动态开点的话，对于编号为x的节点，它的左右孩子的编号就不一定是2*x和2*x+1的关系了，所以我们要保存下的是它的左右孩子的编号已经一系列相关的信息，然后对于每个节点就是当需要到它时再开辟它。其他操作就和静态的线段树差不多。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
struct Tree{
int lson,rson,minx;
}T[N];
int tn,flag,root[];
//root就保存这个颜色对于的那棵线段树的根节点编号
void init()
{
tn=;
for(int i=;i<=;i++)
root[i]=;
}
void updata(int &id,int L,int R,int y,int x)//在这里用L,R来表示节点id的区间
{
if(!id)
{//需要到这个节点了，开辟这个节点
id=tn++;
T[id].minx=N;
T[id].lson=T[id].rson=;//它的子节点还未用得上
}
T[id].minx=min(T[id].minx,x);//更新最小的x值
//下面就是线段树的单点修改
if(L==R)
return ;
int mid=(L+R)>>;
if(y<=mid)
updata(T[id].lson,L,mid,y,x);
else
updata(T[id].rson,mid+,R,y,x);
}
void query(int id,int L,int R,int l,int r,int x)
{
if(flag||!id)//如果已经有点满足条件，或者这个节点没开辟就返回
return ;
if(l<=L&&r>=R)
{
if(T[id].minx<=x)
flag=;//在y1和y2范围内有个x满足条件
return ;
}
int mid=(L+R)>>;
if(l<=mid)
query(T[id].lson,L,mid,l,r,x);
if(r>mid)
query(T[id].rson,mid+,R,l,r,x);
}
int main()
{
int op,x,y,y2,c;
init();
while(~scanf("%d",&op)&&op!=)
{
if(op==)
init();
else if(op==)
{
scanf("%d%d%d",&x,&y,&c);
updata(root[c],,,y,x);
}
else
{
scanf("%d%d%d",&x,&y,&y2);
int ans=;
for(int i=;i<=;i++)
{
flag=;
query(root[i],,,y,y2,x);
ans+=flag;
}
printf("%d\n",ans);
}
}
return ;
}
线段树下线段果
正解是cdq分治，待我学成归来，再更新。。。我回来了
cdq分治处理的话，就是三维偏序的一个处理，（操作时间，x轴，y轴），然后第一维已经有序，那么我们cdq分治处理第二维，然后线段树处理第三维。因为最多是50种颜色，那么我们采用状压的策略，把每个颜色C用2C来表示,然后线段树维护个区间或和。需要注意的就是y轴离散化下，不然容易超时。
#include<cstdio>
#include<algorithm>
#include<vector>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define M(x) ((T[x].l+T[x].r)>>1)
using namespace std;
typedef long long ll;
const int N=,Y=;
struct Tree{
int l,r;
ll val;
}T[Y];
struct Nop{
int op,x,y,y1;
ll val;//op1更新操作的val记录2^C，op2查询操作记录答案编号
friend bool operator <(const Nop &n1,const Nop &n2){
return n1.x==n2.x ? n1.op<n2.op : n1.x<n2.x;
}
}P[N<<],temp[N<<];
int pn=,qn=,newy[Y];
bool num[Y]={};
vector<int> vy;
ll ans[N]={},cf2[]={};
inline void addp(int op,int x,int y,int y1,ll val){
P[pn++]=(Nop){op,x,y,y1,val};
}
inline void addy(int y)
{
if(!num[y])
{
num[y]=;
vy.push_back(y);
}
}
void built(int id,int l,int r)
{
T[id].val=;
T[id].l=l,T[id].r=r;
if(l==r)
return ;
built(L(id),l,M(id));
built(R(id),M(id)+,r);
}
//线段树单点修改
void updata(int id,int pos,ll val)
{
if(T[id].l==T[id].r&&T[id].l==pos)
{
if(val)
T[id].val|=val;
else
T[id].val=;
return ;
}
if(pos<=M(id))
updata(L(id),pos,val);
else
updata(R(id),pos,val);
T[id].val=T[L(id)].val|T[R(id)].val;
}
//区间或和查询
ll query(int id,int l,int r)
{
ll ans=;
if(l<=T[id].l&&T[id].r<=r)
return T[id].val;
if(l<=M(id))
ans|=query(L(id),l,r);
if(r>M(id))
ans|=query(R(id),l,r);
return ans;
}
void cdq(int l,int r)
{
if(l==r)
return ;
int m=(l+r)>>;
cdq(l,m);
cdq(m+,r);
int i=l,j=m+,k=l;
while(i<=m&&j<=r)
{
if(P[i]<P[j])
{
if(P[i].op==)
updata(,P[i].y,P[i].val);
temp[k++]=P[i++];
}
else
{
if(P[j].op==)
ans[P[j].val]|=query(,P[j].y,P[j].y1);
temp[k++]=P[j++];
}
}
while(i<=m)
temp[k++]=P[i++];
while(j<=r)
{
if(P[j].op==)
ans[P[j].val]|=query(,P[j].y,P[j].y1);
temp[k++]=P[j++];
}
for(i=l;i<=r;i++)
{
if(P[i].op==)
updata(,P[i].y,);
P[i]=temp[i];
}
}
void solve()
{
if(pn)
{
//离散化部分
sort(vy.begin(),vy.end());
for(int i=;i<vy.size();i++)
{
newy[vy[i]]=i+;
num[vy[i]]=;
}
for(int i=;i<pn;i++)
{
if(P[i].op==)
P[i].y=newy[P[i].y];
else
P[i].y=newy[P[i].y],P[i].y1=newy[P[i].y1];
}
//进行分治
cdq(,pn-);
}
for(int i=;i<qn;i++)
{
int sum=;
//判断2^0+2^1+2^2+...+2^50含有哪些
for(int j=;j<=;j++)
if(ans[i]&cf2[j])
sum++;
printf("%d\n",sum);
ans[i]=;
}
pn=qn=;
vy.clear();
}
int main()
{
int op,x,y,c,y1;
built(,,N);
for(int i=;i<=;i++)
cf2[i]=cf2[i-]<<;
while(~scanf("%d",&op)&&op!=)
{
if(op==)
solve();
else if(op==)
{
scanf("%d%d%d",&x,&y,&c);
addp(,x,y,,cf2[c]);
addy(y);
}
else
{
scanf("%d%d%d",&x,&y,&y1);
addp(,x,y,y1,qn++);
addy(y);
addy(y1);
}
}
solve();
return ;
}
一分二二分四
但实际上，3个实现方法中，暴力最快。。。数据太坑了