HDU - 6183 暴力，线段树动态开点，cdq分治

B - Color it HDU - 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用2^C来表示,然后线段树维护个区间或和。需要注意的就是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个实现方法中，暴力最快。。。数据太坑了

巴特西

HDU - 6183 暴力，线段树动态开点，cdq分治

B - Color it HDU - 6183

最新文章

热门文章

巴特西

HDU - 6183 暴力，线段树动态开点，cdq分治

B - Color itHDU - 6183

最新文章

热门文章

B - Color it HDU - 6183