poj2777
区间修改，区间查询
mark=-1表示这个区间有多种颜色，否则就1种
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cmath> #include<ctime> #include<set> #include<map> #include<stack> #include<cstring> #define inf 2147483647 #define For(i,a,b) for(register long long i=a;i<=b;i++) #define p(a) putchar(a) #define g() getchar() #define N 100010 using namespace std; long long a[N],n,m,k,x,y,t,cnt; bool vis[50]; char flag; struct seg{long long mark; }s[N<<3];void in(long long &x){long long y=1;char c=getchar();x=0;while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();}x*=y; } void o(long long x){if(x<0){p('-');x=-x;}if(x>9)o(x/10);p(x%10+'0'); }inline void build(long long rt,long long l,long long r){s[rt].mark=1;if(l==r) return;long long mid=(l+r)>>1;build(rt<<1, l, mid);build(rt<<1|1, mid+1, r); }inline void pushdown(long long rt,long long l,long long r){if(s[rt].mark!=-1){s[rt<<1].mark=s[rt<<1|1].mark=s[rt].mark;s[rt].mark=-1;} }inline void update(long long rt,long long nl,long long nr,long long l,long long r,long long k){if(nr<l||nl>r)return;if(nl>=l&&nr<=r){s[rt].mark=k;return;}pushdown(rt,nl,nr);long long mid=(nl+nr)>>1;update(rt<<1, nl, mid, l, r, k);update(rt<<1|1, mid+1, nr, l, r, k); }inline void query(long long rt,long long nl,long long nr,long long l,long long r){if(nl>r||nr<l) return;if(s[rt].mark!=-1){vis[s[rt].mark]=1;return;} long long mid=(nl+nr)>>1;query(rt<<1, nl, mid, l, r);query(rt<<1|1, mid+1, nr, l, r); }int main(){in(n);in(t);in(m);build(1,1,n);For(i,1,m){cin>>flag;if(flag=='C'){in(x);in(y);in(k);update(1,1,n,x,y,k);}else{memset(vis,0,sizeof(vis));in(x);in(y);query(1,1,n,x,y);cnt=0;For(j,1,t) if(vis[j]) cnt++;o(cnt);p('\n');}}return 0; }
