Color it

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)

Total Submission(s): 0    Accepted Submission(s): 0

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

 

题解：这道题目AC的人比较少    在这提供俩种想法

第一：题目规定了颜色的数目最多是51种    

我们可以使用51个线段树   来保存每一种颜色的那些坐标

然后使用线段树查询     时间可能会少点    

第二：我是使用的第二种方法，题目说了最多有

150000个1和2的操作

所以穷举也不是不可以的考虑的    我就是使用穷举AC的

不过时间复杂度不能和线段树的比

//但是   我的代码简单    #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;struct Node{ int x; int y;} node;vector
             
              v[65];int main(){ int k,c; int x2,y1,y2; while(1) { scanf("%d",&k); if(k==3)break; if(k==0) { for(int i=0; i<65; ++i) v[i].clear(); } else if(k==1) { scanf("%d%d%d",&node.x,&node.y,&c); v[c].push_back(node); } else { int ans=0; scanf("%d%d%d",&x2,&y1,&y2); for(int i=0; i<=50; ++i) { for(int j=0; j
              
               =y1) { ans++; break; } } } printf("%d\n",ans); } } return 0;} //欢迎喜欢算法 IT的dalao加1345411028 带我飞