龙岗网站-建设深圳信科,桂林网站建设制作,域名解析器,公司黄页网题目链接 题目要求实现区间覆盖修改以及区间数量查询#xff0c;不难想到为线段树#xff0c;而需要维护什么值来得到不同数的数量很难想#xff0c;但是我们注意到颜色的数量最多只有30种#xff0c;所以对于每一种颜色在一个区间中是否存在#xff0c;我们可以使用线段树…题目链接 题目要求实现区间覆盖修改以及区间数量查询不难想到为线段树而需要维护什么值来得到不同数的数量很难想但是我们注意到颜色的数量最多只有30种所以对于每一种颜色在一个区间中是否存在我们可以使用线段树状态压缩来解决这个问题 首先考虑pushup这点很简单只要将两个儿子节点的颜色状态或一下就可以 然后考虑pushdown此处为颜色覆盖所以对于每次修改只需要将原先的颜色状态直接覆盖为新的状态即可包括lazy也是这样这里注意lazy存的是要覆盖的颜色种类而改变的时候是要先将1左移lazy个位置然后覆盖 ac代码
#includebits/stdc.h
#define endl \n
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pairint,int pii;
const int N1e510;
struct Tree
{int l,r;int sum,lazy;
}tr[N2];
int n,m,q;
string op;
int l,r,d;
int lowbit(int x){return x-x;}
void change(int u,int lazy)
{tr[u].sum1lazy;tr[u].lazylazy;
}
void pushup(int u)
{tr[u].sumtr[u1].sum|tr[u1|1].sum;
}
void pushdown(int u)
{if(tr[u].lazy){change(u1,tr[u].lazy);change(u1|1,tr[u].lazy);tr[u].lazy0;}
}
void build(int u,int l,int r)
{if(lr)tr[u]{l,r,11,0};else {tr[u]{l,r};int midlr1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);}
}
void modify(int u,int l,int r,int d)
{if(tr[u].lltr[u].rr){change(u,d);return ;}pushdown(u);int midtr[u].ltr[u].r1;if(lmid)modify(u1,l,r,d);if(rmid)modify(u1|1,l,r,d);pushup(u);
}
int query(int u,int l,int r)
{if(tr[u].lltr[u].rr)return tr[u].sum;pushdown(u);int midtr[u].ltr[u].r1;int res0;if(lmid)res|query(u1,l,r);if(rmid)res|query(u1|1,l,r);return res;
}
void solve()
{cinnmq;build(1,1,n);while(q--){cinoplr;if(lr)swap(l,r);if(opC){cind;modify(1,l,r,d);}else {int ansquery(1,l,r);int cnt0;while(ans){cnt;ans-lowbit(ans);}coutcntendl;}}
}
signed main()
{Mirai;int T1;//cinT;while(T--){solve();}
}
