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棵树，这样的话我们就可以对于一个区间进行修改了。
但是恶意卡快读快输就不对了啊……
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #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简直业界良心啊！
相信你看了上面的过程也一定理解了这道题了，刚刚传的时候顺序是乱的，结果我就当场来了一遍快速排序QAQ……
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
unsigned long long c1[60000],c2[60000],c3[60000],n;
unsigned long long c4[60000],c5[60000],maxx,a[60000];
inline unsigned long long In()
{
unsigned long long This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') F=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This*F;
}
inline unsigned long long Lowbit(long long x)
{ return x&(-x); }
void Plus(unsigned long long x,unsigned long long add,unsigned long long num)
{
if(num==1)
{
while(x<=maxx)
{
c1[x]+=add;
x+=Lowbit(x);
}
}
if(num==2)
{
while(x<=maxx)
{
c2[x]+=add;
x+=Lowbit(x);
}
}
if(num==3)
{
while(x<=maxx)
{
c3[x]+=add;
x+=Lowbit(x);
}
}
if(num==4)
{
while(x<=maxx)
{
c4[x]+=add;
x+=Lowbit(x);
}
}
if(num==5)
{
while(x<=maxx)
{
c5[x]+=add;
x+=Lowbit(x);
}
}
}
unsigned long long Sum(unsigned long long x,unsigned long long num)
{
if(num==1)
{
unsigned long long ans=0;
while(x>=1)
{
ans+=c1[x];
x-=Lowbit(x);
}
return ans;
}
if(num==2)
{
unsigned long long ans=0;
while(x>=1)
{
ans+=c2[x];
x-=Lowbit(x);
}
return ans;
}
if(num==3)
{
unsigned long long ans=0;
while(x>=1)
{
ans+=c3[x];
x-=Lowbit(x);
}
return ans;
}
if(num==4)
{
unsigned long long ans=0;
while(x>=1)
{
ans+=c4[x];
x-=Lowbit(x);
}
return ans;
}
if(num==5)
{
unsigned long long ans=0;
while(x>=1)
{
ans+=c5[x];
x-=Lowbit(x);
}
return ans;
}
}
int main()
{
n=In();
for(unsigned long long i=1;i<=n;i++)
{
a[i]=In()+1;
maxx=max(maxx,a[i]);
}
for(unsigned int i=1;i<=n;i++)
{
unsigned long long This=1;
Plus(a[i],This,1);
for(unsigned long long j=2;j<=5;j++)
{
unsigned long long This=Sum(a[i]-1,j-1);
Plus(a[i],This,j);
}
}
cout<<Sum(maxx,5)<<endl;
return 0;
}
|
