一个并不是很基础的数据结构题

题目

  1. 基础数据结构练习题

时间限制:\(1s\) 空间限制:\(256MB\)

题目描述

sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧。 在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。 给出一个长度为\(n\)的数列\(A\),接下来有\(m\)次操作,操作有三种: 对于所有的\(i∈[l,r]\),将\(A_i\)变成\(A_i+x\)。 对于所有的\(i∈[l,r]\),将\(A_i\)变成\(\lfloor \sqrt {A~i~} \rfloor\)。 对于所有的\(i∈[l,r]\),询问\(A_i\)的和。 作为一个不怎么熟练的初学者,sylvia想了好久都没做出来。而可怜酱又外出旅游去了,一时间联系不上。于是她决定向你寻求帮助:你能帮她解决这个问题吗。 ## 输入格式 第一行两个数:\(n,m\)。 接下来一行\(n\)个数\(A_i\)。 接下来\(m\)行中,第\(i\)行第一个数\(t_i\) 表示操作类型: 若\(t_i=1\),则接下来三个整数\(l_i,r_i,x_i\),表示操作一。 若\(t_i=2\),则接下来三个整数\(l_i,r_i\),表示操作二。 若\(t_i=3\),则接下来三个整数\(l_i,r_i\),表示操作三。 ## 输出格式 对于每个询问操作,输出一行表示答案。 ## 数据规模 对于所有数据,保证有 \(1<=n,m<=100000,1≤l_i≤r_i≤n,1≤A_i,x_i≤10^5\)

解题报告

\(ISA\)大爷瞬间秒掉了,我却纠结了好久.

因为存在操作一:\(A_i+x\),所以不能像某道只带开方的题目那般暴力了;

但是可以发现,每次添加操作\([l,r]\),不会改变\(A[i]-A[i-1] \ (l<i \leqslant r)\) 只会改变 \(A[l]-A[l-1]\)\(A[r+1]-A[r]\),而如果\(A[i]=A[i+1]\)(或者\(|A[i]-A[i+1]|=1 \And \space |\sqrt {A[i]} - \sqrt {A[i+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
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100001;
typedef long long ll;
int n,m,a[N];
ll sm[N<<2],mx[N<<2],mn[N<<2],mark[N<<2];
char *cp=(char *)malloc(10000000);
char *os=(char *)malloc(1000000),*ot=os;
inline void in(int &x) {
for (;*cp<'0'||*cp>'9';cp++);
for (x=0;*cp>='0'&&*cp<='9';cp++)
x=x*10+*cp-48;
}
void out(ll x) {
if (x) out(x/10) ,*ot++=x%10+'0';
}
inline void print(ll x) {
if (x) out(x); else *ot++='0'; *ot++='\n';
}
inline void up(int x) {
sm[x]=sm[x<<1]+sm[x<<1|1];
mx[x]=max(mx[x<<1],mx[x<<1|1]);
mn[x]=min(mn[x<<1],mn[x<<1|1]);
}
inline void down(int x,int l,int r) {
int mid=(l+r)>>1;
if (mark[x]) {
sm[x<<1]+=mark[x]*(ll)(mid-l+1);
sm[x<<1|1]+=mark[x]*(ll)(r-mid);
mx[x<<1]+=mark[x],mx[x<<1|1]+=mark[x];
mn[x<<1]+=mark[x],mn[x<<1|1]+=mark[x];
mark[x<<1]+=mark[x],mark[x<<1|1]+=mark[x];
mark[x]=0;
}
}
void build(int x,int l,int r) {
mark[x]=0;
if (l==r)
sm[x]=mx[x]=mn[x]=a[l];
else {
int mid=(l+r)>>1;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
up(x);
}
}
void add(int x,int l,int r,int L,int R,int v) {
if (L<=l&&r<=R) {
sm[x]+=(ll) v*(r-l+1),mx[x]+=v,mn[x]+=v;
mark[x]+=v;
} else {
int mid=(l+r)>>1; down(x,l,r);
if (L<=mid) add(x<<1,l,mid,L,R,v);
if (R>mid) add(x<<1|1,mid+1,r,L,R,v);
up(x);
}
}
ll query(int x,int l,int r,int L,int R) {
if (L<=l&&r<=R)
return sm[x];
else {
down(x,l,r);int mid=(l+r)>>1;ll tmp=0;
if (L<=mid) tmp+=query(x<<1,l,mid,L,R);
if (R>mid) tmp+=query(x<<1|1,mid+1,r,L,R);
return tmp;
}
}
void gen(int x,int l,int r,int L,int R) {
if (l^r) down(x,l,r); int mid=(l+r)>>1;
if (L<=l&&r<=R) {
if ((mx[x]-mn[x]==1&&(int)sqrt(mx[x])!=(int)sqrt(mn[x]))||(mx[x]==mn[x])){
ll tmp=(ll)sqrt(mx[x])-mx[x];
sm[x]+=tmp*(ll)(r-l+1),mx[x]+=tmp,mn[x]+=tmp,mark[x]+=tmp;
return;
}
if (l^r) gen(x<<1,l,mid,L,R),gen(x<<1|1,mid+1,r,L,R);
up(x); return ;
}
if (L<=mid) gen(x<<1,l,mid,L,R);
if (R>mid) gen(x<<1|1,mid+1,r,L,R);
up(x);
}
int main() {
freopen("uoj228.in","r",stdin);
freopen("uoj228.out","w",stdout);
fread(cp,1,10000000,stdin);
in(n),in(m); int i;
for (i=1;i<=n;++i) in(a[i]);
build(1,1,n); int x,y,type,z;
for (i=1;i<=m;++i) {
in(type),in(x),in(y);
switch (type) {
case 1: in(z),add(1,1,n,x,y,z);break;
case 2: gen(1,1,n,x,y); break;
case 3: print(query(1,1,n,x,y));
}
}
fwrite(os,1,ot-os,stdout);
return 0;
}

留言