hdu 6183 Color it

hdu 6183 Color it

​​ Problem Description Do you like painting? Little D doesn’t like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format of these operations is as follows.

0 : clear all the points.

1 x y c : add a point which color is c at point (x,y) .

2 x y1 y2 : count how many different colors in the square (1,y1) and (x,y2) . That is to say, if there is a point (a,b) colored c , that 1≤a≤x and y1≤b≤y2 , then the color c should be counted.

3 : exit.

Input The input contains many lines.

Each line contains a operation. It may be ‘0’, ‘1 x y c’ ( 1≤x,y≤106,0≤c≤50 ), ‘2 x y1 y2’ (1≤x,y1,y2≤106 ) or ‘3’.

x,y,c,y1,y2 are all integers.

Assume the last operation is 3 and it appears only once.

There are at most 150000 continuous operations of operation 1 and operation 2.

There are at most 10 operation 0.

Output For each operation 2, output an integer means the answer .

Sample Input 0 1 1000000 1000000 50 1 1000000 999999 0 1 1000000 999999 0 1 1000000 1000000 49 2 1000000 1000000 1000000 2 1000000 1 1000000 0 1 1 1 1 2 1 1 2 1 1 2 2 2 1 1 2 1 2 2 2 2 1 1 2 1 2 1 3 2 2 1 2 2 10 1 2 2 10 2 2 0 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 1 2 2 1 2 2 10 1 2 2 10 2 2 3

Sample Output 2 3 1 2 2 3 3 1 1 1 1 1 1 1 动态加点线段树 由于我们观察到 这个区间的询问 每次都是从第一行开始的 并且 一共只有50种颜色 所以我们针对这50种颜色去建线段树 每个线段树的节点以y来建立 节点内存的信息表示当前这个纵坐标这个颜色 最早出现在第几行 那么查询的时候我只需要查询y1 y2这个区间内 每种颜色最早出现在第几行即可 然后只要这个最早出现的地方小于等于x那么这个区间统计的时候就一定会被统计到

#include #include#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int left,right,v;}tree[2200000];int root[55],num;void insert1(int &x,int l,int r,int pos,int v){ if (!x){ x=++num;tree[x].left=tree[x].right=0;tree[x].v=inf;} int mid=l+r>>1;tree[x].v=min(tree[x].v,v);if (l==r) return ; if (pos<=mid) insert1(tree[x].left,l,mid,pos,v);else insert1(tree[x].right,mid+1,r,pos,v);}int query(int x,int l1,int r1,int l,int r){ if (!x) return inf; if (l<=l1&&r>=r1) return tree[x].v; int mid=l1+r1>>1;int tmp=inf; if (l<=mid) tmp=min(tmp,query(tree[x].left,l1,mid,l,r)); if (r>mid) tmp=min(tmp,query(tree[x].right,mid+1,r1,l,r)); return tmp;}int main(){ freopen("hdu6183.in","r",stdin); while (1){ int op=read();if (op==3) return 0; if (op==0) for (int i=0;i<=50;++i) root[i]=0,num=1; if (op==1){ int x=read(),y=read(),c=read();insert1(root[c],1,1000000,y,x); }int ans=0; if (op==2){ int x=read(),y1=read(),y2=read(); for (int i=0;i<=50;++i) if(query(root[i],1,1000000,y1,y2)<=x) ans++; printf("%d\n",ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。