《算法竞赛进阶指南》 0x42 ~ 0x43 代码 + 杂谈
树状数组
楼兰图腾
逆序对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2*1e5+10;
int c[maxn];
int n;
int lowbit(int x) {
return x&(-x);
}
int ask(int x) {
int res=0;
for(; x; x-=x&(-x)) res+=c[x];
return res;
}
void add(int x,int y) {
for(; x<=n; x+=x&(-x)) {
c[x]+=y;
}
}
int a[maxn];
int L[maxn],R[maxn];
int l[maxn],r[maxn];
signed main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
add(a[1],1);
for(int i=2;i<n;i++){
add(a[i],1);
l[i]=ask(n)-ask(a[i]);
L[i]=ask(a[i]-1);
}
memset(c,0,sizeof c);
add(a[n],1);
for(int i=n-1;i>1;i--){
add(a[i],1);
R[i]=ask(a[i]-1);
r[i]=ask(n)-ask(a[i]);
}
ll rs=0,res=0;
for(int i=2;i<n;i++){
rs+=1ll*l[i]*r[i];
res+=1ll*L[i]*R[i];
}
cout<<rs<<" "<<res<<endl;
return 0;
}
区间改 单点查
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;
int c[maxn];
int n;
int lowbit(int x) {
return x&(-x);
}
int ask(int x) {
int res=0;
for(; x; x-=x&(-x)) res+=c[x];
return res;
}
void add(int x,int y) {
for(; x<=n; x+=x&(-x)) {
c[x]+=y;
}
}
int a[maxn];
signed main() {
int m;
cin>>n>>m;
string cmd;
int l,r,d;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>cmd;
if(cmd[0]=='Q'){
cin>>l;
cout<<ask(l)+a[l]<<endl;
}else{
cin>>l>>r>>d;
add(l,d);
add(r+1,-d);
}
}
return 0;
}
区间改 区间查
建立2割数组维护
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn], n, m;
ll c[2][maxn], sum[maxn];
ll ask(int k, int x){
ll res = 0;
for(; x; x -=(-x&x)) res += c[k][x];
return res;
}
void add(int k, int x, int y){
for(; x <= n; x += (-x&x)) c[k][x] += y;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
for(int i = 1; i <= m; i ++) {
string cmd;
int l, r, d;
cin >> cmd >> l >> r;
if(cmd[0] == 'C'){
cin >> d;
add(0, l, d);
add(0, r + 1, -d);
add(1, l, l * d);
add(1, r + 1, -(r + 1) * d);
}else{
ll ans = sum[r] + (r + 1) * ask(0, r) - ask(1, r);
ans -= sum[l - 1] + l * ask(0, l - 1) - ask(1, l - 1);
cout << ans << endl;
}
}
return 0;
}
lost cow
找第K大 我之前写的 链接https://www.acwing.com/solution/AcWing/content/2166/
二分 树状数组
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int c[maxn];
int n;
int query(int x){
int res = 0;
for(; x; x -= x&(-x)) res += c[x];
return res;
}
void add(int x, int y){
for(;x <= n; x += x & (-x)) c[x] += y;
}
int a[maxn];
int ans[maxn];
int main(){
cin >> n;
add(1, 1);
a[1] ++;
for(int i = 2; i <= n ; i ++ ) {
cin >> a[i]; a[i] ++;
add(i, 1);
}
for(int i = n; i >= 1; i -- ) {
int l = 1, r = n + 1;
while(r - l >= 1){
int mid = l + r >> 1;
if(query(mid) >= a[i]) r = mid;
else l = mid + 1;
}
ans[i] = l;
add(l, -1);
}
for(int i = 1; i <= n; i ++ ) {
cout << ans[i] << endl;
}
return 0;
}
线段树
can you answer on these queries III
区间最大子段和
pushup 函数修改 以及每一次上传的这次修改区间之后 整体的信息 而不是单独区间和的改变
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 5e5+10;
int n, m;
int sum[maxn << 2], lmax[maxn << 2], rmax[maxn << 2], lrmax[maxn << 2];
void push_up(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
lmax[rt] = max(lmax[rt << 1], sum[rt << 1] + lmax[rt << 1 | 1]);
rmax[rt] = max(rmax[rt << 1 | 1], sum[rt << 1 | 1] + rmax[rt << 1]);
lrmax[rt] = max( max(lrmax[rt << 1], lrmax[rt << 1 | 1]), rmax[rt << 1] + lmax[rt << 1 | 1]);
}
void update(int L, int l, int r, int rt, int c) {
if(l == r) {
lrmax[rt] = lmax[rt] = rmax[rt] = sum[rt] = c;
return ;
}
int mid = l + r >> 1;
if(L <= mid) update(L, l, mid, rt << 1, c);
else update(L, mid + 1, r, rt << 1 | 1, c);
push_up(rt);
}
struct node {
int sum;
int lmax, rmax, lrmax;
};
node query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
}
int mid = l + r >> 1;
if (R <= mid) return query(L, R, l, mid, rt << 1);
else if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
else {
node res;
node re1 = query (L, R, l, mid, rt << 1);
node re2 = query (L, R, mid + 1, r, rt << 1 | 1);
res.sum = re1.sum + re2.sum;
res.lmax = max(re1.lmax, re1.sum + re2.lmax);
res.rmax = max(re2.rmax, re2.sum + re1.rmax);
res.lrmax = max( max(re1.lrmax, re2.lrmax), re1.rmax + re2.lmax);
return res;
}
}
int main() {
fastio;
cin >> n >> m;
int k;
for(int i = 1; i <= n; i ++) {
cin >> k;
update(i, 1, n, 1, k);
}
while(m--) {
int cmd, x ,y;
cin >> cmd >> x >> y;
if(cmd == 1) {
if(x > y) swap (x, y);
cout << query(x, y, 1, n, 1).lrmax << endl;
} else {
update(x, 1, n, 1, y);
}
}
return 0;
}
区间最大公约数
差分 后 GCD 不变 注意越界问题
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 5e5+10;
int n, m;
int a[maxn],b[maxn],c[maxn];
struct node {
int val;
} tree[maxn << 2];
int gcd(int a, int b) {
return b == 0 ? a : gcd (b, a%b);
}
void push_up(int rt) {
tree[rt].val = gcd(tree[rt << 1].val, tree[rt << 1 | 1].val);
}
void build(int l, int r, int rt) {
if(l == r) {
tree[rt].val = b[l];
return ;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
push_up(rt);
}
void update(int L, int l, int r, int rt, int c) {
if(L > n) return ; // wc 这里什么鬼啊 越界到什么一个位置了
// 这里 L > n 的话 最后一个点 差分 被 暴力改掉了 导致gcd错误
// 这bug真实难找orz
if(l == r) {
tree[rt].val += c;
return ;
}
int mid = l + r >> 1;
if(L <= mid) update(L, l, mid, rt << 1, c);
else update(L, mid + 1, r, rt << 1 | 1, c);
push_up(rt);
}
int query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return abs(tree[rt].val);
}
int mid = l + r >> 1;
int x = 0, y = 0;
if(L <= mid) x=query(L, R, l, mid, rt << 1);
if(R > mid) y=query(L, R, mid + 1, r, rt << 1 | 1);
return gcd(x, y);
}
int ask(int x) {
int res=0;
for(; x; x -= (-x) & x) {
res += c[x];
}
return res;
}
int add(int x, int y) {
for(; x <= n; x += (-x) & x ) {
c[x] += y;
}
}
signed main() {
fastio;
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
b[i] = a[i] - a[i - 1];
}
build(1, n, 1);
string cmd;
int l, r, d;
for(int i = 1; i <= m ; i ++ ) {
cin >> cmd >> l >> r;
if(cmd[0] == 'C') {
cin >> d;
update(l, 1, n, 1, d);
update(r + 1, 1, n, 1, -d);
add(l, d);
add(r + 1, -d);
} else {
cout << gcd(a[l] + ask(l), query(l + 1, r, 1, n, 1)) << endl;
}
}
return 0;
}
扫描线
题集 链接 https://blog.csdn.net/qq_40831340/article/details/90698827
言特兰蒂斯
此时线段树 每个节点都有意义 都代表一些线段的组合
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define db double
const int maxn = 2005;
struct node {
double lx,rx,y;
int s;
node() {}
node(db _lx, db _rx, db _y, int _s) {
lx=_lx, rx=_rx, y=_y, s=_s;
}
bool operator < (const node &S) const {
return y<S.y;
}
} lines[maxn];
db X[maxn];
db sum[maxn<<2],flag[maxn<<2];
void push_up(int rt, int l, int r) {
if(flag[rt])
sum[rt] = X [ r+1] - X[ l];
else if(l == r)
sum[rt] = 0;
else
sum[rt] = sum[rt << 1] + sum[rt << 1|1];
}
void update(int L, int R, int l, int r, int rt, int c) {
if(L <= l && r <= R) {
flag[rt]+=c;
push_up(rt, l, r);
return ;
}
int mid = (l + r) >> 1;
if(L <= mid) update(L, R, l, mid, rt << 1, c);
if(R > mid) update(L, R, mid + 1, r, rt << 1|1, c);
push_up(rt, l, r);
}
int main() {
int cas=1;
int n;
while(cin >> n, n) {
int cnt = 0;
memset(sum, 0, sizeof sum);
memset(flag, 0, sizeof flag);
for(int i = 1; i <= n; i ++ ) {
double x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
X[ ++cnt ] = x1;
lines[ cnt ] = node(x1, x2, y1, 1);
X[ ++cnt ]= x2;
lines[ cnt ] = node(x1, x2, y2, -1);
}
sort(X + 1, X + 1 + cnt);
sort(lines + 1, lines + 1 + cnt);
int pos = unique(X + 1, X + 1 + cnt) - X;
db ans = 0;
for(int i = 1; i < cnt; i ++ ) {
int l = lower_bound(X + 1, X + pos, lines[ i ].lx) - X;
int r = lower_bound(X + 1, X + pos, lines[ i ].rx) - X - 1;
update(l, r, 1, cnt , 1, lines[i].s);
ans += sum[ 1 ] * (lines[ i+1 ].y - lines[ i ].y);
}
cout << "Test case #" << cas++ << endl;
cout << "Total explored area: ";
printf("%.2lf\n\n",ans);
}
return 0;
}
投递蚂蚁集团等公司10个岗位 >
字节跳动公司氛围 560人发布