LOJ刷题 / 2019寒假刷题计划
1 分钟 读完 (大约 188 个字)

10113. 「一本通 4.1 例 1」数列操作

题意

这是一道模板题。

给定Q个操作：

  • 1 i x：给定 $i,x​$，将 $a[i]​$ 加上 $x​$；
  • 2 l r：给定 $l,r$，求 $\sum_{i=l}^ra[i]$ 的值（换言之，求 $a[l]+a[l+1]+\dots+a[r]$ 的值）。

思路

模板题呀。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[5000010];
void add(ll x,ll y){
	for(ll i=x;i<=n;i+=i&(-i)){
		a[i]+=y;
	}
}
ll getsum(ll x){
	ll sum=0;
	for(ll i=x;i;i-=i&(-i)){
		sum+=a[i];
	}
	return sum;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++){
		ll x;scanf("%lld",&x);
		add(i,x);
	}
	for(ll i=1;i<=m;i++){
		ll type;
		scanf("%lld",&type);
		if(type==1){
			ll x,k;
			scanf("%lld%lld",&x,&k);
			add(x,k);
		}
		if(type==2){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",getsum(y)-getsum(x-1));
		}
	}
}
LOJ刷题 / 2019寒假刷题计划
1 分钟 读完 (大约 209 个字)

10114. 「一本通 4.1 例 2」数星星 Stars

题意

给定 $n​$ 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

思路

这不就是裸的树状数组吗？

题目都按顺序（y的增序）。。。

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
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();int res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
int n,x,y,ans[1500010];
int a[1500010];
void add(int x,int y){
	for(int i=x;i<=1500000;i+=i&(-i)){
		a[i]+=y;
	}
}
int getsum(int x){
	int sum=0;
	for(int i=x;i;i-=i&(-i)){
		sum+=a[i];
	}
	return sum;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		x=read();y=read();
		int t=getsum(x+1);
		ans[t]++;
		add(x+1,1);
	}
	for(int i=0;i<n;i++){
		write(ans[i]);putchar('\n');
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
3 分钟 读完 (大约 512 个字)

10117. 「一本通 4.1 练习 2」简单题

题意

有一个 $n$ 个元素的数组，每个元素初始均为 $0$。有 $m$ 条指令，要么让其中一段连续序列数字反转——$0$ 变 $1$，$1$ 变 $0$（操作 $1$），要么询问某个元素的值（操作 $2$）。

思路

当然是树状数组啦。。。

这里介绍C++的一大利器——位运算。

&在C++里叫做与运算。应该差不多吧。。大概就是这样的：（按一个个位运算）

1
2
3
4
1&1=1
0&1=0
1&0=0
0&0=0

|在C++里叫或运算

1
2
3
4
0|1=1
1|0=1
1|1=1
0|0=0

^在C++里叫异或(xor)

1
2
3
4
0^0=0
1^0=1
0^1=1
1^1=0

~在C++里叫取反

顾名思义。。。

1
2
~1=0
~0=1

然后你就会发现这道题可以用C++的异或+树状数组解决。

利用树状数组，做一个异或前缀和。然后在输出时异或一遍就好了。

（这道题的1操作就相当于异或1）

（然而我们知道x xor 1 xor 1还是等于x）

（所以对于每个1操作只需要先把l之前的xor 1，然后r+1之前的xor 1）

（对于每个2操作只需要把前面统统xor一遍）

你就完美的解决了这道题

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
#include<bits/stdc++.h>
using namespace std;//丑陋无比的头文件终于结束
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}//读入
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}//输出
int n,k;
int c[500010];//不解释
void add(int x,int y){//修改
	for(int i=x;i<=n;i+=i&(-i)){
		c[i]^=y;//异或前缀和
	}
}
int getsum(int x){//询问
	int sum=0;
	for(int i=x;i;i-=i&(-i)){
		sum^=c[i];//询问异或
	}
	return sum;//返回啊
}
int main(){
	n=read();k=read();//读入
	for(int i=1;i<=k;i++){
		char A;cin>>A;
		int m,p;
		if(A=='1'){//操作1
			m=read();p=read();
			add(m,1);//先将l之前的xor 1
			add(p+1,1);//然后把r+1之前的xor 1
            //那么l之前的数统统 xor 1 xor 1，抵消
		}else if(A=='2'){
			m=read();
			write(getsum(m));putchar('\n');//询问输出
		}
	}
	return 0;//结束了。。。
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 246 个字)

10118. 「一本通 4.1 练习 3」打鼹鼠

题意

这是一道模板题。

给出一个 $n\times m$ 的零矩阵 $A$，你需要完成如下操作：

  • 1 x y k：表示元素 $A_{x,y}$ 自增 $k$；
  • 2 a b c d：表示询问左上角为 $(a,b)$，右下角为 $(c,d)$ 的子矩阵内所有数的和。

思路

当然是树状数组啦。。。

模板题。不介绍。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[5010][5010];
ll lowbit(ll x){
	return (x&-x);
}
void add(ll x,ll y,ll k){
	for(ll i=x;i<=n;i+=lowbit(i)){
		for(ll j=y;j<=m;j+=lowbit(j)){
			a[i][j]+=k;
		}
	}
}
ll getsum(ll x,ll y){
	ll sum=0;
	for(ll i=x;i>0;i-=lowbit(i)){
		for(ll j=y;j>0;j-=lowbit(j)){
			sum+=a[i][j];
		}
	}
	return sum;
}
int main(){
	scanf("%lld%lld",&n,&m);
	ll type;
	while(scanf("%lld",&type)!=EOF){
		if(type==1){
			ll x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			add(x,y,k);
		}
		if(type==2){
			ll x1,y1,x2,y2;
			scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
			printf("%lld\n",getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1));
		}
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 231 个字)

10115. 「一本通 4.1 例 3」校门外的树

题意

  • $K=1$，读入 $l,r$表示在 $l$ 到 $r$ 之间种上一种树，每次操作种的树的种类都不同；
  • $K=2$，读入 $l,r$ 表示询问 $l$ 到 $r$ 之间有多少种树。

思路

当然是树状数组啦。。。

食用二维树状数组。

假想括号。。。统计一下就好啦。

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
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();int res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
int n,m,x,y;
int a[3][1500000];
void add(int y,int x){
	for(int i=x;i<=1500000;i+=i&(-i)){
		a[y][i]+=1;
	}
}
int getsum(int k,int x){
	if(x==0) return 0;
	int sum=0;
	for(int i=x;i;i-=i&(-i)){
		sum+=a[k][i];
	}
	return sum;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int type=read();
		x=read();y=read();
		if(type==1) add(0,x),add(1,y);
		else if(type==2) printf("%d\n",getsum(0,y)-getsum(1,x-1));
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 368 个字)

10116. 「一本通 4.1 练习 1」清点人数

题意

  • 如果字母为 A，接下来是一个数 $m$，表示年级主任现在在第 $m$ 节车厢；
  • 如果字母为 B，接下来是两个数 $m,p$，表示在第 $m$ 节车厢有 $p$ 名学生上车；
  • 如果字母为 C，接下来是两个数 $m,p$，表示在第 $m$ 节车厢有 $p$ 名学生下车。

思路

当然是树状数组啦。。。

如果字母为 A ,那么$getsum(m)$

如果字母为 B ,那么$add(m,p)$

如果字母为 C ，那么$add(m,-p)$

好了呀。。。

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else{
		write(x/10);
		putchar(x%10+'0');
	}
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n,k;
int c[500010];
void add(int x,int y){
	for(int i=x;i<=n;i+=i&(-i)){
		c[i]+=y;
	}
}
int getsum(int x){
	int sum=0;
	for(int i=x;i;i-=i&(-i)){
		sum+=c[i];
	}
	return sum;
}
int main(){
//	freopen("code.in","r",stdin);freopen("code.out","w",stdout);
	n=read();k=read();
	for(int i=1;i<=k;i++){
		char A;cin>>A;
		int m,p;
		if(A=='A'){
			m=read();
			write(getsum(m));putchar('\n');
		}else if(A=='B'){
			m=read();p=read();
			add(m,p);
		}else if(A=='C'){
			m=read();p=read();
			add(m,-p);
		}
	}
	return 0;
}
关注我

链接

分类

标签云

Link Cut Tree RMQ Splay bfs dp fhq treap spfa 二分 博弈论 堆 差分 异或 数论 斜率优化 暴力 最长链 枚举 树状数组 树链剖分 模拟 线性筛 线段树 背包 贪心 通知

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×