开源网站有哪些,百度推广长春分公司,网站二级菜单是什么,wxr wordpress校门外的树 【题目分析】题目描述的是一种区间修改#xff0c;看起来好像要用线段树。但是对于这种区间内部没有差别并且查询的是区间内的类别的问题#xff0c;是可以转化为树状数组进行的。毕竟树状数组更加简单。 我们的关注点应该放在区间的端点处#xff0c;然后通过统…校门外的树 【题目分析】题目描述的是一种区间修改看起来好像要用线段树。但是对于这种区间内部没有差别并且查询的是区间内的类别的问题是可以转化为树状数组进行的。毕竟树状数组更加简单。 我们的关注点应该放在区间的端点处然后通过统计端点得到答案。 我们不妨用数组a1保存左端点的个数用数组a2保存右端点的个数从开始到x假如查询的是区间[l,r]那么a1[r]是区间[1,r]的种类数a2[l-1]是区间[1,r]中不包含在[l,r]的种类数答案就是a1[r]-a1[l-1] 代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;int n,m,k,l,r;
const int MAXN50005;
int a1[MAXN],a2[MAXN];int lowbit(int x)
{return x(-x);
}void update1(int x,int y)
{while(xn){a1[x]y;xlowbit(x);}
}
void update2(int x,int y)
{while(xn){a2[x]y;xlowbit(x);}
}int ask1(int x)
{int ret0;while(x){reta1[x];x-lowbit(x);}return ret;
}
int ask2(int x)
{int ret0;while(x){reta2[x];x-lowbit(x);}return ret;
}int main()
{scanf(%d%d,n,m);memset(a1,0,sizeof(a1));memset(a2,0,sizeof(a2));for(int i0;im;i){scanf(%d%d%d,k,l,r);if(k1){update1(l,1);update2(r,1);}else if(k2){printf(%d\n,ask1(r)-ask2(l-1));}}return 0;
}
