2013
11-12

# Count Color

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board – one segment with only one color. We can do following two operations on the board:

1. “C A B C” Color the board from segment A to segment B with color C.

2. “P A B” Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Ouput results of the output operation in order, each line contains a number.

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2


2
1


/* @author: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> *//
import java.io.*;
import java.util.*;
public class Main
{
static  tree[] mytree=new tree[300003];
static boolean[] flag=new boolean[35];
public static void main(String args[]) throws Exception
{
int l=Integer.parseInt(ss[0]);
int t=Integer.parseInt(ss[1]);
int o=Integer.parseInt(ss[2]);
buildtree(1,l,1);
while(o--!=0)
{
if(ss[0].equals("C"))
{
int A=Integer.parseInt(ss[1]);
int B=Integer.parseInt(ss[2]);
if(A>B)
{
int temp=A;
A=B;
B=temp;
}
int p=Integer.parseInt(ss[3]);
insert(A,B,p,1);

}
if(ss[0].equals("P"))
{
int A=Integer.parseInt(ss[1]);
int B=Integer.parseInt(ss[2]);
if(A>B)
{
int temp=A;
A=B;
B=temp;
}
Arrays.fill(flag, false);
query(A,B,1);
int count=0;
for(int i=0;i< 35;i++)
if(flag[i])
count++;
System.out.println(count);

}
}
}

public static void buildtree(int a,int b,int i)
{
mytree[i]=new tree();
mytree[i].left=a;
mytree[i].right=b;
mytree[i].color=1;
if(a!=b)
{
int mid=(a+b)/2;
buildtree(a,mid,i*2);
buildtree(mid+1,b,i*2+1);
}
}

public static void insert(int a,int b,int c,int i)
{
if(mytree[i].left==a&&mytree[i].right==b)
mytree[i].color=c;
else
{
if( mytree[i].color !=-1)
{
mytree[i*2].color =mytree[i].color ;
mytree[i*2+1].color =mytree[i].color ;
mytree[i].color =-1;
}
int mid=(mytree[i].left+mytree[i].right)/2;
if(b<=mid)
insert(a,b,c,2*i);
else if(a>=mid+1)
insert(a,b,c,2*i+1);
else
{
insert(a,mid,c,2*i);
insert(mid+1,b,c,2*i+1);
}
}

}

public static void query(int a,int b,int i)
{
if(mytree[i].color==-1)
{
if(mytree[2*i]==mytree[2*i+1]&&mytree[2*i].color!=-1)
mytree[i].color=mytree[2*i+1].color;
}
if(mytree[i].color!=-1)
{
flag[mytree[i].color]=true;
}
else
{
int mid=(mytree[i].left+mytree[i].right)/2;
if(b<=mid&&mytree[2*i]!=null)
query(a,b,2*i);
else if(a>=mid+1&&mytree[2*i+1]!=null)
query(a,b,2*i+1);
else
{
if(mytree[2*i]!=null)
query(a,mid,2*i);
if(mytree[2*i+1]!=null)
query(mid+1,b,2*i+1);
}
}
}
}

class tree
{
int left;
int right;
int color;
}

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}