儿童影楼网站设计,简单建设网站,关注公众号领红包,上海网站建设哪家强折叠 区间修改#xff0c;区间查询#xff0c;这一类题通常都可以使用线段树解决#xff0c;但对于此题#xff0c;树状数组同样可以#xff0c;而且常数较小#xff0c;代码简单。 思路#xff1a; 考虑使用树状数组去维护差分数组#xff0c;即对于 a i a_i ai,我们…折叠 区间修改区间查询这一类题通常都可以使用线段树解决但对于此题树状数组同样可以而且常数较小代码简单。 思路 考虑使用树状数组去维护差分数组即对于 a i a_i ai,我们使用树状数组去维护 ∣ a i − a i − 1 ∣ |a_i-a_{i-1}| ∣ai−ai−1∣的值。 对于修改我们对一段区间进行修改的时候能对结果产生影响的只有左右端点因为绝对值之差相互抵消了。 所以我们考虑修改时端点的影响即可。 对于 a l a_l al,若 a l − 1 ≤ a l a_{l-1}\leq a_l al−1≤al那么我们在对 a l a_l al进行加一后我们会发现 ∣ a l − a l − 1 ∣ |a_l-a_{l-1}| ∣al−al−1∣的值同样会加一所以我们正常给 a l a_l al加一即可。 反之 a l − 1 a l a_{l-1}a_{l} al−1al,那么在给 a l a_l al加一的时候 ∣ a l − a l − 1 ∣ |a_l-a_{l-1}| ∣al−al−1∣的值会减小所以此时我们需要给该值减一。 对于 r , r 1 r,r1 r,r1位置的分析同理。 同时又因为查询需要输出 a l a_l al的值所以我们再开一个树状数组去单独维护每个值的大小即可。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nstruct MIT
{
ll tr[N];
int lowbit(int x) {return x (-x);
}void add(int u, int v) {for (int i u; i N; i lowbit(i)) {tr[i] v;}
}ll query(int x) {ll res 0;for (int i x; i 0; i - lowbit(i)) {res tr[i];}return res;
}
};MIT t1,t2;void solve()
{int n,q;cinnq;vectorint a(n5);for(int i1;in;i){cina[i];t1.add(i,a[i]-a[i-1]);t2.add(i,abs(a[i]-a[i-1]));}while(q--){int op,l,r;cinoplr;if(op1){coutt1.query(l)t2.query(r)-t2.query(l)endl;}else{ll c1t1.query(l-1),c2t1.query(l);if(c2-c10) t2.add(l,1);else t2.add(l,-1);c1t1.query(r),c2t1.query(r1);if(c2-c10) t2.add(r1,-1);else t2.add(r1,1);t1.add(l,1),t1.add(r1,-1);}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
Mex and Update
问题陈述
给你一个长度为 N N N 的序列 A ( A 1 , A 2 , … , A N ) A(A_1,A_2,\dots,A_N) A(A1,A2,…,AN)。 请按给出的顺序回答下列 Q Q Q 个问题。 k k k个查询按以下格式给出
首先将 A i k A_{i_k} Aik改为 x k x_k xk。这一改动将带入后续查询。然后打印 A A A的 m e x \rm{mex} mex。 A A A的 m e x \rm{mex} mex是不包含在 A A A中的最小非负整数。
可以说一道典题收获不小。有两种思路第一种就是set第二种就是树状数组两种方法接下来都会介绍。
set做法 我们使用set去记录序列中没有出现过的数那么这样对于每次查询而言我们输出set的第一个元素即可。同时我们使用 c n t cnt cnt数组去维护每个数在序列中的出现次数然后每次修改时去 c n t cnt cnt数组中对应删除或是添加。 对于删除操作若该元素删去一次后变为 0 即代表这个数不存在于序列中了所以需要放入 set 对于添加操作若该元素添加后次数变为1即代表该数第一次出现在序列中即之前不存在于序列中存在于set中所以此时需要把这个数从set中删除即可。 时间复杂度 q l o g n qlogn qlogn
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nvoid solve()
{int n,q;cinnq;setint s;mapint,int mp;//不使用map使用正常数组即可。vectorint a(n5);for(int i1;in;i){cina[i];mp[a[i]];}for(int i0;in;i){if(!mp.count(i)) s.insert(i);}while(q--){int id,x;cinidx;if(mp[a[id]]){mp[a[id]]--;mp[x];if(mp[x]1) s.erase(x);if(mp[a[id]]0){s.insert(a[id]);}a[id]x;}cout*s.begin()endl;}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
树状数组 思路我们考虑将每个元素放入树状数组中即将值域映射到下标通过0/1去判断这个数是否存在。经过上述操作后我们对于mex的判断为因为树状数组返回的是 1 − i 1-i 1−i的前缀和即对于第 i 个数我们可以知道前面有多少个比 i 小的数那么我们可以在树状数组上进行二分前缀和保证了单调性找到第一个下标大于其对应值的地方即为mex。 时间复杂度 q × ( l o g n ) 2 q\times(logn)^2 q×(logn)2 细节有点多具体看代码注释。
#include bits/stdc.husing namespace std;
const int N 4e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nint n,q;vectorint a(N),b(N);struct MIT
{
ll tr[N];
int lowbit(int x) {return x (-x);
}void add(int u, int v) {for (int i u; i N; i lowbit(i)) {tr[i] v;}
}ll query(int x) {ll res 0;for (int i x; i 0; i - lowbit(i)) {res tr[i];}return res;
}
};
MIT c;int cal()//树状数组二分过程
{int l1,rn1,ans0;while(lr){int mid(lr)/2;if(c.query(mid)mid){ansmid;lmid1;}else rmid-1;}return ans;
}void solve()
{cinnq;for(int i1;in;i) cina[i],a[i];//把每个元素加1因为树状数组不能为0for(int i1;in;i){if(a[i]n1){//如果当前数大于n,那么放入树状数组就没有意义了因为mex只能为0-n之间if(b[a[i]]0){//如果这个数没有出现过我们就进行添加c.add(a[i],1);}b[a[i]];//记录该数的出现次数}}while(q--){ll id,x;cinidx;x;if(a[id]n1){//同理if(b[a[id]]1) c.add(a[id],-1);//如果当前数的次数为1即删一次为0即我们修改后这个数不存在了所以就需要把这个数从树状数组中删除b[a[id]]--;}if(xn1){//同理if(b[x]0) c.add(x,1);b[x];}a[id]x;//把当前数的值修改为xcoutcal()endl;}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
由于set的做法写的不是很好导致set的运行时间比树状数组还长…
大风起兮 简化一下题意给定一个数组有 q q q次操作每次操作选择一个编号为 x x x的元素删除要求输出每次操作的中位数。
思路 考虑树状数组在这题中如何进行应用我们同样把值域映射到下标去统计对于第 i 个数其前面有多少个比他小的数。然后运用二分去找值为 n / 2 n/2 n/2的下标即为所求。
因为值域很大所以需要进行离散化。
#include bits/stdc.husing namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nstruct MIT
{
ll tr[N];
int lowbit(int x) {return x (-x);
}void add(int u, int v) {for (int i u; i N; i lowbit(i)) {tr[i] v;}
}ll query(int x) {ll res 0;for (int i x; i 0; i - lowbit(i)) {res tr[i];}return res;
}
};int n,q;
int a[N];
MIT tr;int cal(int x)
{int l1,rN,ans0;while(lr){int mid(lr)/2;if(tr.query(mid)x){rmid-1;ansmid;}else lmid1;}return ans;
}void solve()
{cinn;vectorint b;for(int i1;in;i){scanf(%d,a[i]);b.push_back(a[i]);}b.push_back(0);sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());//离散化不多说了for(int i1;in;i){int tlower_bound(b.begin(),b.end(),a[i])-b.begin();a[i]t;tr.add(t,1);}int q;cinq;while(q--){int x;cinx;xa[x];tr.add(x,-1);n--;if(n%20){double ans(b[cal(n/2)]b[cal(n/21)])*1.0/2;printf(%.1lf ,ans);}else{double ansb[cal((n1)/2)]*1.0;printf(%.1lf ,ans);}}//coutendl;
}int main()
{int t;t1;while(t--){solve();}//system(pause);return 0;
}
