LightOJ 1135(线段树)
2024-08-25 13:36:58
题解引自:http://www.cnblogs.com/wuyiqi/archive/2012/05/27/2520642.html
题意:
有n个数,刚开始都为0
add i , j 给i,j区间内的数都加1
Q i j 询问i、j间能被三整除的数的个数
分析:
线段树记录三个域
对三取余为0的数的个数
。。。。。1.。。。。。
。。。。。2.。。。。。
可以保存在一个数组里面
考虑到每次给一个区间加1的时候,区间内对3取余为1的数的个数变成了对三取余为2,2的变成了0,0的变成了1
所以每次更新到区间或者把信息(懒惰标记)往下传的时候只需要把相应的域做一下调整即可
// File Name: 1135.cpp
// Author: Zlbing
// Created Time: 2013/7/18 21:47:54 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--) #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 const int MAXN=1e5+;
int col[MAXN<<];
int sum[MAXN<<][];
int n,q; void pushup(int rt)
{
for(int i=;i<;i++)
sum[rt][i]=sum[rt<<][i]+sum[rt<<|][i];
}
void build(int l,int r,int rt)
{
col[rt]=;
if(l==r)
{
sum[rt][]=;
sum[rt][]=sum[rt][]=;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
void make(int rt)
{
swap(sum[rt][],sum[rt][]);
swap(sum[rt][],sum[rt][]);
}
void pushdown(int rt)
{
if(col[rt])
{
col[rt<<]+=col[rt];
col[rt<<|]+=col[rt];
for(int i=;i<col[rt]%;i++)
{
make(rt<<);
make(rt<<|);
}
}
col[rt]=;
}
void update(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
col[rt]++;
make(rt);
return;
}
pushdown(rt);
int m=(l+r)>>;
if(L<=m)update(L,R,lson);
if(R>m)update(L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt][];
}
pushdown(rt);
int m=(l+r)>>;
int ret=;
if(L<=m)ret+=query(L,R,lson);
if(R>m)ret+=query(L,R,rson);
return ret;
}
int main()
{
int T;
int cas=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
int a,b,c;
build(,n,);
printf("Case %d:\n",cas++);
for(int i=;i<q;i++)
{
scanf("%d%d%d",&a,&b,&c);
b++,c++;
if(a==)update(b,c,,n,);
if(a==){
printf("%d\n",query(b,c,,n,));
}
}
}
return ;
}
最新文章
- css-使用line-height实现垂直居中的一些问题
- UIkit框架之uUInavigationController
- 编码-截取中文-去除HTML字符
- Content related to smartcards (and RFID/NFC)
- Baby Step Gaint Step
- java 容器、二叉树操作、107
- WC2001 高性能计算机
- jsp假分页
- EF Core新增迁移时无法加载程序集“System.ValueTuple”的错误
- PHP开发api接口安全验证方法一
- python3安装scrapy教程
- Hive学习之路 (二十一)Hive 优化策略
- Knockout与Require框架同时使用时的visible绑定的问题,造成的影响,以及解决的方法。
- python 进程队列
- Java 8 新日期时间 API
- 磁盘 blk_update_request: I/O error
- Hadoop案例(八)辅助排序和二次排序案例(GroupingComparator)
- 今夜我们一起学习 Apache Shiro
- 预编译头文件来自编译器的早期版本,或者预编译头为 C++ 而在 C 中使用它(或相反)转
- 【spring】 SpringMVC返回json数据的三种方式
热门文章
- CentOS 6.4 编译 Hadoop 2.5.1
- Git CMD - pull: Fetch from and integrate with another repository or a local branch
- Eclipse清除SVN密码
- Bash常用快捷键
- mysql - 编码
- 那些年,我们一起学WCF--(6)PerCall实例行为
- 解决Xcode7多个模拟器的方法
- 向RichTextBox控件不停的AppendText数据时,如何把光标的焦点始终显示到最后
- Fedora 21 安装Infinality
- VIM快捷键(转)