题目大意 ：本题为POJ2777的改编题 ：poj2777 数据比poj弱了点，可以不用状压 ！ 给你n个花盆（n<=100000 ），这里有30种花， 初始时没盆花都种的种类为1的花，现在给你 q 个操作 1， P a,b,c （把区间[a,b]的花改为种类为c的花） 2，Q a b （查询区间[a,b]中有多少种花并输出）
题目思路：首先看到题目第一想到的是线段树，然后就想线段树的节点维护的是什么，容易想到的是区间的花的种类数，但是一般的方法不好实现满足区间的减法，这里就有一个相对暴力的方法，用一个标记数组和种类计数的数组，当然我不推荐这种做法，因为我当时也不是这样想的。因为种类只有30，所以就不难想到用状态压缩，用30位的二进制位表示花的种类，0表示没有该种花，1表示有，这里有一个二进制的或运算的技巧，0|1=1 ,1|1=1; 所以就可以实现花的种类的加法，因此就不难想到用线段树的节点来维护这个值！
定义：
sto[] 数组为线段树节点数组 cover[]数组为懒惰标记数组
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=2e5+100;
int sto[maxn<<2];
int cover[maxn<<2];建树：
cover[]数组初始化为1 二进制 为 1（前面的0省略了） 第一位为1表示种类为1的花 ，向上更新函数为 两个子节点的或运算结果---实现种类的加法！
void Push(int rt)
{
sto[rt]=sto[rt<<1]|sto[rt<<1|1];
}
void BuildTree(int l,int r,int rt)
{
cover[rt]=0;
if(l==r)
{
sto[rt]=1;
return ;
}
int mid=(l+r)>>1;
BuildTree(lson);
BuildTree(rson);
Push(rt);
}更新函数：
向下更新函数：因为更新的是整个区间都改为同一种种类，所以直接把父节点的caver值赋值给子节点，子节点的值就是父节点的cover值（这里用十进制表示）
区间更新：和普通的线段树的区间更新函数一样，只要改向上向下更新函数即可！
void PushDown(int rt,int cnt)
{
if(cover[rt])
{
cover[rt<<1]=cover[rt];
cover[rt<<1|1]=cover[rt];
sto[rt<<1]=cover[rt];
sto[rt<<1|1]=cover[rt];
cover[rt]=0;
}
}
void Update(int L,int R,int v,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
cover[rt]=v;
sto[rt]=v;
return ;
}
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid) Update(L,R,v,lson);
if(mid<R)Update(L,R,v,rson);
Push(rt);
}查询函数：
和普通的区间查询函数相似，只是把区间加法运算改为或运算来实现区间的加法！
int query(int L,int R,int l,int r,int rt)
{
if(L <=l && r<=R) return sto[rt];
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
int res=0;
if(L<=mid)res=query(L,R,lson)|res;
if(mid<R) res=query(L,R,rson)|res;
return res;
}主函数：
前面是题目的输入要求，输入 P a,b,c 时 因为c为种类十进制数，所以要把转换成二进制的种类数 比如种类2为 10 种类3为 100 种类4 为1000 ...... 然后在把二进制的种类数转换成十进制的数，10为2^1=2 ,100为2^2=4， 1000为2^3 = 8 ......这个只要用个循环就可以算出，，！ 输入 Q a b 时 此时调用查询函数，返回的是一个十进制数，然后转换成二进制数（本身就可以当成二进制数进行计数，这里只是一种说法），这里用到了与运算来计数，因为0&1 = 0 1&1 = 1 ,所以就可以拿返回的值与1进行与运算，如果为1就表示当前位置上有该种类的花否则没有，也就是下面的代码的那个while循环，最后统计出来的就是要的答案！
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
BuildTree(1,n,1);
while(q--)
{
char str[5];
scanf("%s",str);
if(str[0]=='Q')
{
int l,r;
scanf("%d%d",&l,&r);
int x=query(l,r,1,n,1);
int ans=0;
while(x){
if(x&1==1)ans++;
x=x/2;
}
printf("%d\n",ans);
}
else
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int ans=0;
int ss=1;
for(int i=1;i<z;i++){
ss*=2;
}
ans+=ss;
Update(x,y,ans,1,n,1);
}
}
}
return 0;
}#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=2e5+100;
int sto[maxn<<2];
int cover[maxn<<2];
void PushDown(int rt,int cnt)
{
if(cover[rt])
{
cover[rt<<1]=cover[rt];
cover[rt<<1|1]=cover[rt];
sto[rt<<1]=cover[rt];
sto[rt<<1|1]=cover[rt];
cover[rt]=0;
}
}
void Push(int rt)
{
sto[rt]=sto[rt<<1]|sto[rt<<1|1];
}
void BuildTree(int l,int r,int rt)
{
cover[rt]=0;
if(l==r)
{
sto[rt]=1;
return ;
}
int mid=(l+r)>>1;
BuildTree(lson);
BuildTree(rson);
Push(rt);
}
void Update(int L,int R,int v,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
cover[rt]=v;
sto[rt]=v;
return ;
}
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid) Update(L,R,v,lson);
if(mid<R)Update(L,R,v,rson);
Push(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L <=l && r<=R) return sto[rt];
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
int res=0;
if(L<=mid)res=query(L,R,lson)|res;
if(mid<R) res=query(L,R,rson)|res;
return res;
}
int main()
{
int n,q;
while(~scanf("%d%d",&n,&q))
{
BuildTree(1,n,1);
while(q--)
{
char str[5];
scanf("%s",str);
if(str[0]=='Q')
{
int l,r;
scanf("%d%d",&l,&r);
int x=query(l,r,1,n,1);
int ans=0;
while(x){
if(x&1==1)ans++;
x=x/2;
}
printf("%d\n",ans);
}
else
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int ans=0;
int ss=1;
for(int i=1;i<z;i++){
ss*=2;
}
ans+=ss;
Update(x,y,ans,1,n,1);
}
}
}
return 0;
}
POJ上的AC代码：
只要在输入时多加个种类变量T 其实没有啥用 ，只需考虑最多为30种 还有就是它的区间输入不一定是从左往右的，所以还要做个判断！！！
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=2e5+100;
int sto[maxn<<2];
int cover[maxn<<2];
void PushDown(int rt,int cnt)
{
if(cover[rt])
{
cover[rt<<1]=cover[rt];
cover[rt<<1|1]=cover[rt];
sto[rt<<1]=cover[rt];
sto[rt<<1|1]=cover[rt];
cover[rt]=0;
}
}
void Push(int rt)
{
sto[rt]=sto[rt<<1]|sto[rt<<1|1];
}
void BuildTree(int l,int r,int rt)
{
cover[rt]=0;
if(l==r)
{
sto[rt]=1;
return ;
}
int mid=(l+r)>>1;
BuildTree(lson);
BuildTree(rson);
Push(rt);
}
void Update(int L,int R,int v,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
cover[rt]=v;
sto[rt]=v;
return ;
}
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid) Update(L,R,v,lson);
if(mid<R)Update(L,R,v,rson);
Push(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L <=l && r<=R) return sto[rt];
PushDown(rt,r-l+1);
int mid=(l+r)>>1;
int res=0;
if(L<=mid)res=query(L,R,lson)|res;
if(mid<R) res=query(L,R,rson)|res;
return res;
}
int main()
{
int n,q,t;
while(~scanf("%d%d%d",&n,&t,&q))
{
BuildTree(1,n,1);
while(q--)
{
char str[5];
scanf("%s",str);
if(str[0]=='P')
{
int l,r;
scanf("%d%d",&l,&r);
if(l>r)swap(l,r);
int x=query(l,r,1,n,1);
int ans=0;
while(x){
if(x&1==1)ans++;
x=x/2;
}
printf("%d\n",ans);
}
else
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(x>y)swap(x,y);
int ans=0;
int ss=1;
for(int i=1;i<z;i++){
ss*=2;
}
ans+=ss;
Update(x,y,ans,1,n,1);
}
}
}
return 0;
}
京公网安备 11010502036488号