登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Xorex's blog

纵然希望渺茫,也要做一条有梦想的咸鱼!

 
 
 
 
 

日志

 
 
关于我

本人倒是一直被吊着打啊……

文章分类

二叉索引树(树状数组)—题解  

2017-05-12 22:01:44|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
开个坑,这两天补完。
QAQ硬是拖了三天……

P1993[树状数组]种树
Jzyz的机房的新规定明确说明,机房高一最强的人要接受惩罚,于是杨树辰就被罚去植树了。我们把jzyz对面的一条路看成一条长度为n的线,晗神给杨树神指定了一些区间让他种树,美其名曰让他减肥,但是晗神在中间会来检查杨树神的工作,询问杨树神一个点上有几棵树,但是杨树神不仅代码敲得贼好,而且眼神非常好,但是作为大佬的杨树神想考考你,并让你设计一个程序来帮他完成晗神的检查。
输入:
第一行:n和m。 
第2到m+1行:每行开头一个z Z=1,后跟两个整数L和R表示种树的区间L,R,0<=L<=R<=n. Z=2,后跟一个整数x,表示询问的地点的树的个数,0<=x<=n.
输出:
对于每个z==2的答案。
1<=n,m<=1000000;

这里是运用到了树状数组的区间操作,我们对于修改一个区间的元素已经很清楚了,只需要将所有的数组都加上就好了,那么检查的时候我们就需要将左端点到1种上-1棵树,然后右端点到1种上1棵树,这样的话我们就可以对于一个区间进行修改了。
但是恶意卡快读快输就不对了啊……
code:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,z,x,y,k,c[1000002];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int In()
{
int This=0,F=1; char ch=getc();
while(ch<'0'||ch>'9')
{
if(ch=='-') F=-1;
ch=getc();
}
while(ch>='0'&&ch<='9')
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getc();
}
return This*F;
}
void put(int x)
{
if(x==0)
{
putchar('0');
putchar('\n');
return;
}
if(x<0)
{
putchar('-');
x=-x;
}
int num=0;char ch[16];
while(x) ch[++num]=x%10+'0',x/=10;
while(num) putchar(ch[num--]);
putchar('\n');
}
inline int Lowbit(int x)
{ return x&(-x); }
int Sum(int x)
{
int ans=0;
while(x>=1)
{
ans+=c[x];
x-=Lowbit(x);
}
return ans;
}
void Plus(int x,int add)
{
while(x<=n)
{
c[x]+=add;
x+=Lowbit(x);
}
}
int main()
{
n=In()+1; m=In();
for(int i=1;i<=m;i++)
{
if(z=In()==1)
{
x=In()+1; y=In()+1;
Plus(x,1);
Plus(y+1,-1);
}
else put(Sum(k=In()+1));
}
return 0;
}



P1994 [树状数组]尧神追MM(树神出的题就是不一样)
Jzyz的机房中都是dalao,其中最会追MM的就是尧神。
有一天尧神发现了n个MM,尧神非常开心,想让他们都成为自己的GF,但是他又怕有太多的GF会得不偿失(其实就是怕原配生气),于是他决定只从这n个MM中找5个作为自己的GF。每个MM都有自己的魅力值(1<=魅力值<=50000),尧神希望自己找的这5个MM的魅力值严格递增,他的原配想要请你设计个程序计算尧神找GF的方案数(因为这是他晚上回去要跪键盘的时间)。
输入:
第一行:一个整数n(1<=n<=50000)
第二行:n个整数,表示n个MM的魅力值。
输出:
输入仅包含一行,表示方案数。
这道题啊,超级厉害啊,各种坑挖的,什么无符号longlong,什么坐标为0。
首先,你需要声明一个 unsigned long long 才不会被爆掉,然后记得每个坐标都加上一个1,因为数据里面是有位0的,而树状数组里面是不能为零的,不然会无线循环,Lowbit(0)=0然后就不停地加或者减无法退出。
因为题目上让尧神留下来5个MM,所以我们就可以开五个树状数组来记录下来元素能严格递增并且长度达到第i个树状数组的方案数,更新的步骤是这样的,将第i个数加入第一个树状数组里面,统计小于第i个数的个数,如果然后加到下一个树状数组里面这样每次循环4次。
最后输出第五个树状数组所有元素之和就好了。
树神的PPT简直业界良心啊!

二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
  
二叉索引树(树状数组)—题解 - Xorex - Xorexs blog 二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
 二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
二叉索引树(树状数组)—题解 - Xorex - Xorexs blog 二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
二叉索引树(树状数组)—题解 - Xorex - Xorexs blog 
二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
 
 
 
  
 
 
二叉索引树(树状数组)—题解 - Xorex - Xorexs blog二叉索引树(树状数组)—题解 - Xorex - Xorexs blog
  

相信你看了上面的过程也一定理解了这道题了,刚刚传的时候顺序是乱的,结果我就当场来了一遍快速排序QAQ……



  评论这张
 
阅读(80)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018