线段树入门题
#include<iostream>
#define N 1000000
using namespace std;
struct line
{ int left,right;
int col;
}a[N];
int n,t,o;
bool c[31]={0};
char s;
int aa,bb,cc;
void build(int i,int j,int v)
{
a[v].left=i;
a[v].right=j;
a[v].col=1;
if(a[v].left<a[v].right)
{ int mid=(i+j)>>1;
build(i,mid,2*v);
build(mid+1,j,2*v+1);
}
}
void insert(int i,int j,int v,int q)
{ if(a[v].left==i&&a[v].right==j)
{ a[v].col=q;
return ;
}
else if(a[v].left<a[v].right)
{ int mid=(a[v].left+a[v].right)>>1;
if(a[v].col>=1)
{ a[2*v].col=a[v].col;
a[2*v+1].col=a[v].col;
a[v].col=-1;
}
if(j<=mid)
{ insert(i,j,2*v,q);
}
else if(i>mid)
{ insert(i,j,2*v+1,q);
}
else
{ insert(i,mid,2*v,q);
insert(mid+1,j,2*v+1,q);
}
}
}
void check(int s,int t,int v)
{ if(a[v].col>0)
{ c[a[v].col]=1;
return ;
}
else if(a[v].col==-1&&a[v].left<a[v].right)
{ int mid=(a[v].left+a[v].right)>>1;
if(t<=mid)
{ check(s,t,2*v);
}
else if(s>mid)
{ check(s,t,2*v+1);
}
else
{ check(s,mid,2*v);
check(mid+1,t,2*v+1);
}
}
}
int cnt()
{ int i;
int s=0;
for(i=1;i<=30;i++)
{ if(c[i])
s++;
}
return s;
}
int main()
{
scanf("%d%d%d",&n,&t,&o);
getchar();
build(1,n,1);
while(o--)
{ scanf("%c",&s);
getchar();
if(s=='C')
{ scanf("%d%d%d",&aa,&bb,&cc);
getchar();
if(aa<=bb)
insert(aa,bb,1,cc);
else insert(bb,aa,1,cc);
}
else
{
scanf("%d%d",&aa,&bb);
getchar();
memset(c,0,sizeof(c));
if(aa<=bb)
check(aa,bb,1);
else check(bb,aa,1);
printf("%d\n",cnt());
}
}
system("pause");
return 0;
}