当前位置：首页 > news >正文

3-26 备赛

news 来源：原创 2024/5/20 10:02:37

今天复习了树状数组、RMQ区间最大值问题、01背包问题
天梯赛补题目、校赛补题

树状数组
https://blog.csdn.net/weixin_44777363/article/details/107254870
讲的比较清楚的csdn博客。
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
ll a[N], b[N];
int n, q;
// 计算lowbit的
int lowbit(int x)
{return x & (-x);
}
void add(int p, int x)
{while (p <= n){b[p] += x;p += lowbit(p);}
}
ll count(int p)
{ll result = 0;while (p){result += b[p];p -= lowbit(p);}return result;
}
int main()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){add(i, a[i]);}while (q--){int k, l, r;cin >> k >> l >> r;if (k == 0){ll res = count(r) - count(l - 1);cout << res << endl;}else{add(l, r);}}
}

树状数组的题目:
https://www.acwing.com/problem/content/1217/
蓝桥杯真题:

交换小朋友的位置，对应的区间需要加上一个数字
最后是需要查询所有的数字。

n是1e5次方，如何解决呢？

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
long long a[N],tr[N],b[N]={0};int lowbit(int x){return x&-x;
}void add(int x,int y){for(int i=x;i<N;i+=lowbit(i)) tr[i]+=y;
}int query(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=tr[i];return ans;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i]++; //避免0}for(int i=1;i<=n;i++){add(a[i],1);b[i]=(i)-query(a[i]); //比这个数大的个数}// cout<<endl;memset(tr,0,sizeof tr); //该逆序算了，所以维护树状数组不一样，所以算完大的要清0.for(int i=n;i>=1;i--){add(a[i],1);b[i]+=query(a[i]-1);  //比这个数小}long long res=0;// for(int i=1;i<=n;i++){//     cout<<b[i]<<endl;// }for(int i=1;i<=n;i++){res+=(1+b[i])*b[i]/2;}cout<<res<<endl;return 0;
}

RMQ问题

#include <bits/stdc++.h>
using namespace std;
int n, t, q;
const int N = 2e5 + 10;
const int M = 25;
int a[N], Log[N];
int f[N][M];
void GetLog()
{int i;Log[1] = 0;for (i = 2; i <= n + 1; ++i)Log[i] = Log[i / 2] + 1;
}
void RMQ()
{int i, j;for (i = 1; i <= n; ++i)f[i][0] = a[i];for (j = 1; (1 << j) <= n; ++j)for (i = 1; i + (1 << (j - 1)) <= n; ++i)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int main()
{cin >> n >> t >> q;for (int i = 1; i <= n; ++i)cin >> a[i];GetLog();RMQ();for (int i = 1; i <= t; ++i){int l, r;scanf("%d%d", &l, &r);int k = Log[r - l + 1];int ans = max(f[l][k], f[r - (1 << k) + 1][k]);if (ans >= q){cout << ans << ' ' << "YES" << endl;}else{cout << ans << ' ' << "NO" << endl;}}return 0;
}