2022.11.6
洛谷 P2357 守墓人
为什么选这个？
练习树状数组，线段树（主要是树状数组），这个在之后的阶段会经常用到，是一种常见的数据结构。
题目解释
数据结构裸题。
有一个长度为$n$的数组，有几个操作，需要对某个区间加减操作，对某个区间求和。
由于算法思想就是模板，可以多看看树状数组 / 线段树的题解。
树状数组
Code：
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&-x
using namespace std;
const int N=5e5+10;
int n,m,last,opt,x,y,z,mian;
int sum1[N],sum2[N];
void add(int pos,int x)
{
for(int i=pos;i<=n;i+=lowbit(i))
sum1[i]+=x,sum2[i]+=pos*x;
}
long long query(int pos)
{
long long res=0;
for(int i=pos;i;i-=lowbit(i))
res+=(pos+1)*sum1[i]-sum2[i];
return res;
}
signed main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
cin >> x,add(i,x-last),last=x;
for(int i=1,opt;i<=m;i++)
{
cin >> opt;
switch(opt)
{
case 1:cin>>x>>y>>z,add(x,z),add(y+1,-z);break;
case 2:cin>>z,mian+=z;break;
case 3:cin>>z,mian-=z;break;
case 4:cin>>x,cin>>y;printf("%lld\n",query(y)-query(x-1)+(x==1)*mian);break;
case 5:printf("%lld\n",query(1)+mian);
}
}
}
树状数组
线段树
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
struct node
{
ll sum,lazy;
}tre[808666];
ll a[200001],n,f,l,r,k;
void build(ll l,ll r,ll now)
{
if(l==r)
{
tre[now].sum=a[l];
tre[now].lazy=0;
return;
}
ll mid=(l+r)>>1;
ll lson=now<<1;
ll rson=lson|1;
build(l,mid,lson);
mid++;
build(mid,r,rson);
tre[now].lazy=0;
tre[now].sum=tre[lson].sum+tre[rson].sum;
}
void down(ll l,ll r,ll now)
{
if(tre[now].lazy)
{
ll k=tre[now].lazy;tre[now].lazy=0;
ll mid=(l+r)>>1,lson=now<<1,rson=lson|1;
tre[lson].lazy+=k;tre[rson].lazy+=k;
tre[lson].sum+=(mid-l+1)*k;
mid++;
tre[rson].sum+=(r-mid+1)*k;
}
}
void add(ll u,ll v,ll l,ll r,ll now,ll it)
{
if(u<=l&&v>=r)
{
tre[now].lazy+=it;
tre[now].sum+=(r-l+1)*it;
return;
}
if(u>r||v<l) return;
ll mid=(l+r)>>1,lson=now<<1,rson=lson|1;
down(l,r,now);
add(u,min(v,mid),l,mid,lson,it);
mid++;
add(max(u,mid),v,mid,r,rson,it);
tre[now].sum=tre[lson].sum+tre[rson].sum;
}
ll ask(ll u,ll v,ll l,ll r,ll now)
{
if(u<=l&&v>=r)
{
return tre[now].sum;
}
if(u>r||v<l) return 0;
ll mid=(l+r)>>1,lson=now<<1,rson=lson|1;
down(l,r,now);
ll re=0;
re+=ask(u,min(v,mid),l,mid,lson);
mid++;
re+=ask(max(u,mid),v,mid,r,rson);
tre[now].sum=tre[lson].sum+tre[rson].sum;
return re;
}
int main()
{
scanf("%lld%lld",&n,&f);
for(ll i=1;i<=n;++i) scanf("%lld",&a[i]);
build(1,n,1);
for(ll i=1;i<=f;++i)
{
ll opt;
scanf("%lld",&opt);
if(opt == 1)
{
scanf("%lld%lld%lld",&l,&r,&k);
add(l,r,1,n,1,k);
}
if(opt == 2)
{
scanf("%lld",&k);
add(1,1,1,n,1,k);
}
if(opt == 3)
{
scanf("%d",&k);
add(1,1,1,n,1,-k);
}
if(opt == 4)
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",ask(l,r,1,n,1));
}
if(opt == 5)
{
printf("%lld\n",ask(1,1,1,n,1));
}
}
return 0;
}
线段树
Codeforces #829 Make Nonzero Sum (version easy / hard)
为什么选这个？
是一个练习思维的一道题，涉及算法的知识很少，相比更考验对于题目的理解，以及“贪心”的策略选择；
此外应该还涉及到构造了吧（（（
题目解释
给定了一个只有$[-1,0,1]$的数构成的数组，选取其不重不漏的子区间集合$s_i=[l_i,r_i]$使得这些子区间集$s_i$的总和为0。不要求子区间集的数量最小化。
- $s_i = a[l_i] - a[l_{i+1}]+…(+ / -)a[r_i]$
- $r[i] +1 == l[i+1], 1\leq i < n$
- $l[1]=1, r[k]=n$
即每个数组的值均对应在某个子区间上，而每个子区间内的计算顺序是加减交替的。
如果不存在，输出$-1$，存在则输出一种可能的集合组成方案
浅析
1. 可以把（非零的）数目个数总数分为奇数偶数来看，显然地有奇数个时，该式子无法求解，直接返回-1；
2. 对于一个数量大于等于3的集合，我们均可以有$a-b+c...=(a+b)+c$，所以对于大于3之上的部分我们是可以去改变组合的，我们只需要考虑的是数目小于等于2的一种情况；
3. 我们允许$[x,x]$形式的存在；
4. 每一组都凑成0，那么最后的结果就为0；
5. 对于$easy version$，只用考虑$[-1,1]$的情况，对于$hard version$，则需要考虑$[-1,0,1]$的情况，对于$easy version$我们只需要连续两个数凑成$0$即可，对于$hard version$，我们可以看每一个区域$[x_1,x_2]$的第二个数$x_2$其前面是否为$0$：如果为0，则令该$0$与其一同出现，即为$[x_1,x_1],[0,x_2]$；否则还是跟着前面那个一起出来就行。
Code：
为了拓展大家的视野，提供了两种编码习惯的代码，大家可以自行参考。
参考1
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
const int L = 5e5 + 5;
int t, n, k, x, y, z, ans, cnt, a[L], flag[L];
signed main() {
cin >> T;
while (T--) {
int sum = 0;
cin >> n;
vector<int> po;
memset(flag, 0, sizeof(flag));
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
if (sum % 2) {
cout << "-1" << endl;
continue;
}
sum /= 2;
for (int i = 2; i <= n; i++) {
if (a[i] == 1 && sum > 0 && !flag[i - 1]) {
flag[i] = true;
po.push_back(i);
sum--;
}
if (a[i] == -1 && sum < 0 && !flag[i - 1]) {
flag[i] = true;
po.push_back(i);
sum++;
}
if (sum == 0) {
break;
}
}
if (sum != 0) {
cout << "-1" << endl;
break;
}
ans = 0;
for (int i = 1; i <= n; i++) {
if (flag[i + 1]) {
continue;
}
ans++;
}
if (sum == 0) {
cout << ans << endl;
for (int i = 1; i <= n; i++) {
if (flag[i + 1]) {
continue;
}
if (flag[i]) {
cout << i - 1 << " " << i << endl;
} else {
cout << i << " " << i << endl;
}
}
}
}
return 0;
}参考代码2
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e6 + 10;
int n,num,x,t,flag;
int a[N],b[N],last;
int main()
{
cin >> t;
while(t--)
{
cin >> n;
x=0; num=0; last=0;
for(int i=1;i<=n;i++)
{
b[i]=0;
cin >> a[i];
if(a[i]==0)
{
x++;
b[i]=1;
continue;
}
num++;
if(last != 0)
{
if(last!=a[i])
{
b[i] = 1;
x++;
}
last=0;
}
else
{
last=a[i];
b[i]=1;
x++;
}
}
if(num % 2 == 1)
printf("-1\n");
else
{
flag = 0;
printf("%d\n",x);
for(int i=1;i<=n;i++)
{
if(b[i])
{
if(flag)
printf("%d\n%d ",i-1,i);
else
{
printf("%d ",i);
flag = 1;
}
}
}
printf("%d\n",n);
}
}
return 0;
}