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

10128. 「一本通 4.3 练习 2」花神游历各国

题意

每一次旅行中，花神会选择一条旅游路线，它在那一串国家中是连续的一段，这次旅行带来的开心值是这些国家的喜欢度的总和，当然花神对这些国家的喜欢程序并不是恒定的，有时会突然对某些国家产生反感，使他对这些国家的喜欢度 $\delta$ 变为 $\sqrt \delta$（可能是花神虐爆了那些国家的 OI，从而感到乏味）。

现在给出花神每次的旅行路线，以及开心度的变化，请求出花神每次旅行的开心值。

思路

为了使时间复杂度降低，我们可以发现：$\sqrt 1=1$所以，最大数字$10^9$操作较少次数便能到$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
#include<bits/stdc++.h>
#define ll long long
#define MAXNUM 1000000*4+10
using namespace std;
struct node{
	ll l,r,lef,rig;
	ll val,Max;
}tree[210000];
ll a[110000],len,n,m;
void build(ll l,ll r){
	ll root=++len;
	tree[root].l=l;tree[root].r=r;tree[root].lef=tree[root].rig=-1;
	if(l==r)tree[root].val=tree[root].Max=a[l];
	else{
		ll mid=(l+r)/2;
		ll lef=tree[root].lef=len+1;build(l,mid);
		ll rig=tree[root].rig=len+1;build(mid+1,r);
		tree[root].val=tree[lef].val+tree[rig].val;
		tree[root].Max=max(tree[lef].Max,tree[rig].Max);
	}
}
void update(ll root,ll l,ll r){
	if(tree[root].Max<2) return ;
	if(tree[root].l==tree[root].r){tree[root].val=sqrt(tree[root].val);tree[root].Max=tree[root].val;return ;}
	ll lef=tree[root].lef,rig=tree[root].rig,mid=(tree[root].l+tree[root].r)/2;
	if(r<=mid) update(lef,l,r);
	else if(mid<l) update(rig,l,r);
	else update(lef,l,mid),update(rig,mid+1,r);
	tree[root].val=tree[lef].val+tree[rig].val;
	tree[root].Max=max(tree[lef].Max,tree[rig].Max);
}
ll query(ll root,ll l,ll r){
	if(tree[root].l>=l&&tree[root].r<=r) return tree[root].val;
	ll lef=tree[root].lef,rig=tree[root].rig,mid=(tree[root].l+tree[root].r)/2;
	if(r<=mid) return query(lef,l,r);
	else if(mid<l) return query(rig,l,r);
	else return query(lef,l,mid)+query(rig,mid+1,r);
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,n);
	scanf("%lld",&m);
	while(m--){
		char s;cin>>s;
		if(s=='2'){
			ll x,y;scanf("%lld%lld",&x,&y);
			update(1,x,y);
		}else{
			ll x,y;scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
4 分钟 读完 (大约 582 个字)

10129. 「一本通 4.3 练习 3」维护序列

题意

有长为 $n$ 的数列，不妨设为 $a_1,a_2,\cdots ,a_n$。有如下三种操作形式：

  • 把数列中的一段数全部乘一个值；
  • 把数列中的一段数全部加一个值；
  • 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $P$ 的值。

思路

线段树瞎搞。乘法的优先级要高一些。

注意MOD

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
#include<bits/stdc++.h>
#define N 10000000+10
#define ll long long
using namespace std;
ll n,m,a[N],add[N*4+10],mod,p,mul[N*4+10];
ll tree[N*4+10];
void pushup(ll id){
	tree[id]=tree[id<<1]+tree[(id<<1)|1];
	tree[id]%=mod;
}
void push_down(ll cur,ll l,ll r,ll mid){
    if(mul[cur]==1&&add[cur]==0) return;
    mul[cur<<1]=mul[cur<<1]*mul[cur]%mod;
    add[cur<<1]=(add[cur<<1]*mul[cur]%mod+add[cur])%mod;
    tree[cur<<1]=(tree[cur<<1]*mul[cur]%mod+add[cur]*(ll)(mid-l+1)%mod)%mod;
    mul[cur<<1|1]=mul[cur<<1|1]*mul[cur]%mod;
    add[cur<<1|1]=(add[cur<<1|1]*mul[cur]%mod+add[cur])%mod;
    tree[cur<<1|1]=(tree[cur<<1|1]*mul[cur]%mod+add[cur]*(ll)(r-mid)%mod)%mod;
    mul[cur]=1;
    add[cur]=0;
    return;
}
void update(ll id,ll l,ll r,ll ql,ll qr,ll val){
	if(ql<=l&&qr>=r){
		add[id]+=val;add[id]%=mod;
		tree[id]=(tree[id]+(ll)(r-l+1)*val%mod)%mod;
		return ;
	}
	push_down(id,l,r,l+r>>1);
	ll mid=l+((r-l)>>1);
	if(ql<=mid) update(id<<1,l,mid,ql,qr,val);
	if(qr>=mid+1) update((id<<1)|1,mid+1,r,ql,qr,val);
	pushup(id);
}
void updatemul(ll cur,ll L,ll R,ll l,ll r,ll x){
    if(L>=l&&R<=r){
        mul[cur]=mul[cur]*(ll)x%mod;
        add[cur]=add[cur]*(ll)x%mod;
        tree[cur]=tree[cur]*(ll)x%mod;
        return;
    }
    ll mid=L+R>>1;
    push_down(cur,L,R,mid);
    if(l<=mid) updatemul(cur<<1,L,mid,l,r,x);
    if(r>mid) updatemul(cur<<1|1,mid+1,R,l,r,x);
    pushup(cur);
}
ll query(ll id,ll L,ll R,ll l,ll r){
    if(L>=l&&R<=r) return tree[id]%mod;
    ll mid=L+R>>1;
    ll ans=0;
    push_down(id,L,R,mid);
    if(l<=mid) ans=(ans+query(id<<1,L,mid,l,r))%mod;
    if(r>mid) ans=(ans+query(id<<1|1,mid+1,R,l,r))%mod;
    pushup(id);
    return ans;
}
void build(ll L,ll R,ll x,ll y,ll cur){
    mul[cur]=1;add[cur]=0;tree[cur]+=y;
    if(L==R) return;
    ll mid=L+R>>1;
    if(x>mid) build(mid+1,R,x,y,cur<<1|1);
    else build(L,mid,x,y,cur<<1);
    pushup(cur);
}
int main(){
	scanf("%lld%lld",&n,&mod);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),build(1,n,i,a[i]%mod,1);
	scanf("%lld",&m);
	for(ll i=1;i<=m;i++){
		ll type;
		scanf("%lld",&type);
		if(type==1){
			ll x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			updatemul(1,1,n,x,y,k);
		}
		if(type==2){
			ll x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			update(1,1,n,x,y,k);
		}
		if(type==3){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			ll temp=query(1,1,n,x,y);
			printf("%lld\n",temp%mod);
		}
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 259 个字)

10127. 「一本通 4.3 练习 1」最大数

题意

给定一个正整数数列 $a_1, a_2, a_3, \cdots , a_n$，每一个数都在 $0\sim p – 1$ 之间。可以对这列数进行两种操作：

  • 添加操作：向序列后添加一个数，序列长度变成 $n + 1$；

  • 询问操作：询问这个序列中最后 $L$ 个数中最大的数是多少。

程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。

思路

模板题呀。

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
#include<bits/stdc++.h>
#define ll long long
#define MAXNUM 200000*4+10
using namespace std;
struct node{
	ll l,r,lef,rig,c;
}tree[MAXNUM];
ll n,m,q,len,las;
void build(ll l,ll r){
	ll root=++len;
	tree[root].l=l;tree[root].r=r;tree[root].lef=tree[root].rig=-1;
	if(l<r){
		ll mid=(l+r)/2;
		tree[root].lef=len+1;build(l,mid);
		tree[root].rig=len+1;build(mid+1,r);
	}
}
void update(ll root,ll x,ll k){
	if(tree[root].l==tree[root].r){tree[root].c=k;return ;}
	ll lef=tree[root].lef,rig=tree[root].rig;
	ll mid=(tree[root].l+tree[root].r)/2;
	if(x<=mid) update(lef,x,k);
	else update(rig,x,k);
	tree[root].c=max(tree[lef].c,tree[rig].c);
}
ll query(ll root,ll l,ll r){
	if(tree[root].l>=l&&tree[root].r<=r) return tree[root].c;
	ll lef=tree[root].lef,rig=tree[root].rig;
	ll mid=(tree[root].l+tree[root].r)/2;
	if(r<=mid) return query(lef,l,r);
	else if(mid<l) return query(rig,l,r);
	else return max(query(lef,l,mid),query(rig,mid+1,r));
}
int main(){
	scanf("%lld%lld",&m,&q);
	build(1,m);
	while(m--){
		char s;cin>>s;
		if(s=='A'){
			ll x;scanf("%lld",&x);n++;
			update(1,n,(x+las)%q);
		}else{
			ll x;scanf("%lld",&x);
			las=query(1,n-x+1,n);
			printf("%lld\n",las);
		}
	}
}
LOJ刷题 / 2019寒假刷题计划
3 分钟 读完 (大约 419 个字)

10126. 「一本通 4.3 例 2」A Simple Problem with Integers

题意

这是一道模板题。\r\n\r\n给定数列 $a[1], a[2], \dots, a[n]$，你需要依次进行 $q$ 个操作，操作有两类：

  • 1 l r x：给定 $l,r,x$，对于所有 $i\in[l,r]$，将 $a[i]$ 加上 $x$（换言之，将 $a[l], a[l+1], \dots, a[r]$ 分别加上 $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
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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[1000010],add[1000000*4+10];
ll tree[1000000*4+10];
void pushup(ll id){
	tree[id]=tree[id<<1]+tree[(id<<1)|1];
}
void build(ll id,ll l,ll r){
	if(l==r) tree[id]=a[l];
	else{
		ll mid=l+((r-l)>>1);
		build(id<<1,l,mid);
		build((id<<1)|1,mid+1,r);
		pushup(id);
	}
}
void pushdown(ll id,ll l,ll r){
	if(add[id]!=0){
		add[id<<1]+=add[id];
		add[(id<<1)|1]+=add[id];
		ll mid=l+((r-l)>>1);
		tree[id<<1]+=add[id]*(mid-l+1);
		tree[(id<<1)|1]+=add[id]*(r-mid);
		add[id]=0;
	}
}
void update(ll id,ll l,ll r,ll ql,ll qr,ll val){
	if(ql<=l&&qr>=r){
		add[id]+=val;
		tree[id]+=val*(r-l+1);
		return ;
	}
	pushdown(id,l,r);
	ll mid=l+((r-l)>>1);
	if(ql<=mid) update(id<<1,l,mid,ql,qr,val);
	if(qr>=mid+1) update((id<<1)|1,mid+1,r,ql,qr,val);
	pushup(id);
}
ll query(ll id,ll l,ll r,ll ql,ll qr){
	if(ql<=l&&qr>=r) return tree[id];
	pushdown(id,l,r);
	ll mid=l+((r-l)>>1);
	ll ans=0;
	if(ql<=mid) ans+=query(id<<1,l,mid,ql,qr);
	if(qr>=mid+1) ans+=query((id<<1)|1,mid+1,r,ql,qr);
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll type;
		scanf("%lld",&type);
		if(type==1){
			ll x,y,k;
			scanf("%lld%lld%lld",&x,&y,&k);
			update(1,1,n,x,y,k);
		}
		if(type==2){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			ll temp=query(1,1,n,x,y);
			printf("%lld\n",temp);
		}
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 367 个字)

10125. 「一本通 4.3 例 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
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
#include<bits/stdc++.h>
#define N 10000000+10
#define ll long long
using namespace std;
ll n,m,a[N],add[N*4+10];
ll tree[N*4+10];
void pushup(ll id){
	tree[id]=tree[id<<1]+tree[(id<<1)|1];
}
void build(ll id,ll l,ll r){
	if(l==r) tree[id]=a[l];
	else{
		ll mid=l+((r-l)>>1);
		build(id<<1,l,mid);
		build((id<<1)|1,mid+1,r);
		pushup(id);
	}
}
void pushdown(ll id,ll l,ll r){
	if(add[id]!=0){
		add[id<<1]+=add[id];
		add[(id<<1)|1]+=add[id];
		ll mid=l+((r-l)>>1);
		tree[id<<1]+=add[id]*(mid-l+1);
		tree[(id<<1)|1]+=add[id]*(r-mid);
		add[id]=0;
	}
}
void update(ll id,ll l,ll r,ll ql,ll qr,ll val){
	if(ql<=l&&qr>=r){
		add[id]+=val;
		tree[id]+=val*(r-l+1);
		return ;
	}
	pushdown(id,l,r);
	ll mid=l+((r-l)>>1);
	if(ql<=mid) update(id<<1,l,mid,ql,qr,val);
	if(qr>=mid+1) update((id<<1)|1,mid+1,r,ql,qr,val);
	pushup(id);
}
ll query(ll id,ll l,ll r,ll ql,ll qr){
	if(ql<=l&&qr>=r) return tree[id];
	pushdown(id,l,r);
	ll mid=l+((r-l)>>1);
	ll ans=0;
	if(ql<=mid) ans+=query(id<<1,l,mid,ql,qr);
	if(qr>=mid+1) ans+=query((id<<1)|1,mid+1,r,ql,qr);
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll type;
		scanf("%lld",&type);
		if(type==1){
			ll x,y,k;
			scanf("%lld%lld",&y,&k);
			
			update(1,1,n,y,y,k);
		}
		if(type==2){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			ll temp=query(1,1,n,x,y);
			printf("%lld\n",temp);
		}
	}
	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

×