Description
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.Input
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.Output
Ouput results of the output operation in order, each line contains a number.Sample Input
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
Sample Output
2 1
Source
POJ Monthly--2006.03.26,dodo
題意:
有一個board,初始都為顏色1,有兩個操作,C將區間[l,r]都塗成顏色val,P詢問區間[l,r]的顏色種數。
思路:
線段樹區間更新,維護一個區間的顏色種類數就行了,由於只有30種顏色,可以考慮位操作,用一個int來表示。
代碼:
#include#include #include #include #define maxn 100005 #define lson (rt<<1) #define rson (rt<<1|1) #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int n,m,tot; char s[10]; int vis[maxn<<2],sum[maxn<<2]; void pushdown(int le,int ri,int rt) { if(vis[rt]!=-1) { vis[lson]=vis[rson]=vis[rt]; sum[lson]=sum[rson]=(1< >1; if(v<=mid) { update(le,mid,lson,u,v,val); } else if(u>=mid+1) { update(mid+1,ri,rson,u,v,val); } else { update(le,mid,lson,u,mid,val); update(mid+1,ri,rson,mid+1,v,val); } pushup(le,ri,rt); } int query(int le,int ri,int rt,int u,int v) { if(vis[rt]!=-1) return (1< >1; if(v<=mid) { res=query(le,mid,lson,u,v); } else if(u>=mid+1) { res=query(mid+1,ri,rson,u,v); } else { res=query(le,mid,lson,u,mid); res|=query(mid+1,ri,rson,mid+1,v); } return res; } int main() { while(~scanf("%d%d%d",&n,&tot,&m)) { memset(vis,-1,sizeof(vis)); memset(sum,0,sizeof(sum)); update(1,n,1,1,n,0); while(m--) { scanf("%s",s); int u,v,val; if(s[0]=='C') { scanf("%d%d%d",&u,&v,&val); if(u>v) swap(u,v); update(1,n,1,u,v,val-1); } else { if(u>v) swap(u,v); scanf("%d%d",&u,&v); int x=query(1,n,1,u,v),ans=0; while(x) { if(x&1) ans++; x>>=1; } printf("%d\n",ans); } } } return 0; } /* 2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2 */